[1] 수십억건의 유저 데이터에서 ID 존재여부 찾기

10억건 규모의 회원데이터에서의 아이디 validation 체크는 어떻게 해야할까?

 

현재 내가 개발하고 있는 서비스에서도 천만단위의 회원 DB에서 온라인으로 존재 여부를 판단하는 일은 존재한다. 아니 흔하다. 트래픽과 DB 종류 및 구조에 따라서 인덱스만 적절히 설정해줘도 요구사항에 맞게 작동되는 시스템이 있을 수 있다.

 

하지만 글로벌서비스같은 경우, DB의 규모가 1억 10억건을 넘어갈 수 있고 트래픽도 지금 경험하는 것 보다 훨씬 많을 것이기에 인덱스만으로 DB를 최적화 하기엔 한계가 있을 수 있다. 그래서 다른 방법도 생각해봐야 한다.

 

1. DB 조회

가장 쉽고 직관적이고 기본적인 방법이다.

1.  요청이 들어오면
2.  DB를 조회하는 것

 

가장 쉽지만 여기엔 몇 가지 문제가 있다.

 

• 성능 문제: 대기 시간이 상대적으로 길어지는 문제가 발생할 수 있다. 데이터 양이 커질수록 쿼리 속도가 느려진다.
• 네트워크 지연: 애플리케이션 서버와 데이터베이스 서버 간의 네트워크 통신이 필요하기 때문에, 연결을 설정하고 쿼리를 전송한 후 응답을 받는 과정에서 추가적인 지연이 발생
• 데이터베이스 부하 증가: 자주 SELECT 쿼리가 발생하면 데이터베이스의 CPU 및 I/O 리소스를 소모하여 부담이 커짐.
• 확장성 문제: 데이터베이스는 동시 연결 및 자원 사용에 제한이 있음. 사용자가 급격히 증가하면 요청을 처리하는 데 어려움을 겪을 수 있고, 데이터베이스를 수직적으로 확장(Scale Up)하는 것은 비용이 많이 들고 한계가 있음

16 Best Resources to Crack the System Design Interview

 

2. 캐싱

DB 대신 캐싱공간(인메모리DB등)에 저장하여 DB I/O를 줄이고 조회/응답시간을 신속하게 만드는 방법이다.

이 방법 또한 당연히 문제가 있다. 10억건의 데이터를 상정하고 이야기를 하고 있는데 메모리에 이 모든 데이터를 다 올린다? 아무리 직·병렬화/압축을 한다해도 이 많은 데이터를 올리려면 엄청난 메모리가 소모될 것이다.

How to Design Twitter (X) in a System Design Interview?

 

 

3. 블룸 필터

칼럼에선 "공간 효율성이 좋은 확률적 데이터구조"로 소개하고 있다 (나도 처음 들어봤다).

내가 읽고 이해하기엔 Cache Ratio 효율화 방법인 것 같다. 간략하게 요약하자면, bit array와 해싱함수를 활용해 특정 요소가 들어왔었는지 판단하여 처음 들어왔다면 Caching하고, 전에 들어왔었다면 Caching 영역을 조회하는 방법이다. 인메모리 Caching DB 대표인 Redis에서도 이 방법을 사용할 수 있는 옵션이 있다고 한다.

 

1.  모든 bit array를 0으로 만든 적정 길이의 array를 만듦
2.  특정 x 값에 대한 조회 요청이 들어온다면 x에 해싱함수를 적용하여 그 위치를 1로 변경함. (없다면 어쩔 수 없이 DB 조회하고 캐싱영역에 저장)
3.  다음 x 값에 대한 조회 요청이 들어온다면 해싱함수를 적용한 위치가 1이기에 DB를 조회하지 않고 캐싱영역을 조회함.

(+ 글을 읽다보니 조회하고자 하는 값에 대한 존재여부가 아닌 그 값 자체를 해싱영역에 저장하는 것일수도 있겐다는 생각이 듦)

(+ 글을 더 읽다보니 오탐에 대한 가능성 때문에 존재여부(0,1)만 기록하고 존재한다면 DB에서 한번 더 조회하는 방법도 있다고 함)

 

 

이 방법에도 물론 장단이 존재한다.

 

장점

• 메모리 효율화 : 블룸 필터는 해시 값만 저장하므로, 해시 테이블 같은 데이터 구조보다 메모리 사용량이 훨씬 적음.
• 빠른 조회 : 모든 검색이 상수시간(O(1))에 이루어짐

단점

• 오탐 발생 가능 : 해싱함수를 사용하다 보니 겹치는 값이 있어 오차가 발생할 수 있음. (x의 해싱값이 1이라면 다른 y, z도 해싱값이 1이 아니란 법은 없으니..)
• 요소 삭제 불가 : 해당 요소에 의해 설정된 비트들이 다른 요소에도 영향을 미쳐 오탐 확률이 증가할 수 있어 삭제는 권하지 않는다고 한다. (이를 해결하기 위해 카운팅 블룸 필터라는 것도 있음 -> 비트(0,1) 대신 각 값에 대한 카운터를 사용하는 것)

4 Steps to Prepare for System Design Interviews in 2025? [The Ultimate Guide]

 

 

 

의견

최적화를 위해 기초 아이디어 부터 차례대로 발전한 모습을 지켜보는 것은 참 재미있다 (내가 뭔가를 생각해내서 더 최적화 시킬 여지도 있고). 항상 생각하는게, 최적화 알고리즘 +α, +β를 더하는 것은 시스템을 효율적으로 만들겠지만 코드나 로직은 더욱 복잡해진다. 실무에서는 이만한 트래픽을 다룰일도 거의 없거니와.. 유지보수와 코드의 간결함을 위해 이런 최적화 기법 적용은 가장 나중에 해야하지 않나 싶다. 시스템에 부하가 크지 않다면 최적화와 로직의 간결함 사이에서 균형을 맞추는게 좋아보인다.

 

 

 

 

출처 : https://medium.com/javarevisited/interview-how-to-check-whether-a-username-exists-among-one-billion-users-ffa0d0522998