수십억 명의 사용자 서비스는 어떻게 0.1초 만에 유저명 중복을 확인할까?

주간SaaS 오늘의 소개 글

안녕하세요, 주간 SaaS입니다.

새로운 서비스에 가입할 때, 내가 쓰려던 아이디가 이미 존재한다는 메시지를 종종 만나게 됩니다. 으레 '데이터베이스에서 중복 값을 확인하나 보다' 하고 넘겼지만, 사용자 수가 폭발적으로 늘어난다면 이 간단한 기능조차 지연 시간 없이 제공하기란 쉽지 않은 과제입니다.

오늘 소개할 글은 바로 이 단순한 기능을 어떻게 저지연(low-latency), 그리고 확장성 있는 소프트웨어 아키텍처로 구현하는지 그 방법을 쉽고 명쾌하게 소개합니다.

Instagram 같은 플랫폼에서 회원가입을 할 때, 사용하고 싶은 유저명을 입력하면 시스템은 거의 즉시 사용 가능 여부를 알려줍니다. 만약 이미 사용 중인 이름이라면, 그 자리에서 바로 대안 유저명을 추천해주기까지 하죠.

수천 명 규모의 작은 스타트업이라면 간단한 database query 한 번으로 충분할 겁니다. 하지만 Instagram, Google, 혹은 X(구 Twitter)처럼 수십억 명의 사용자를 보유한 플랫폼에게는 훨씬 더 어려운 문제입니다. 누군가 가입을 시도할 때마다 수십억 개의 데이터를 전부 스캔할 수는 없는 노릇이니까요.

그렇다면 이들은 어떻게 눈 깜짝할 사이에 이 작업을 해내는 걸까요?

이 글에서는 가장 기본적인 접근법부터 빅테크 기업에서 사용하는 정교한 아키텍처까지, 이러한 시스템이 어떻게 만들어지는지 그 여정을 단계별로 살펴보겠습니다.

## Level 1: 데이터베이스에 직접 쿼리하기

유저명 중복을 확인하는 가장 간단한 방법은 데이터베이스에 직접 물어보는 것입니다.

SELECT COUNT(1) 
FROM users 
WHERE username = ‘new_user’;

만약 count가 0보다 크면 이미 사용 중인 유저명이고, 0이라면 사용 가능한 이름입니다. 간단하죠?

수천, 수백만 명 규모의 시스템에서는 이 방법으로도 충분합니다. 인덱싱이 잘 된 관계형 데이터베이스는 수 밀리초(milliseconds) 안에 결과를 반환할 수 있으니까요.

하지만 수억, 수십억 명의 사용자가 여러 서버와 데이터 센터에 분산된 환경으로 확장되면 상황은 완전히 달라집니다.

요컨대, 직접 쿼리는 정확하고 구현하기 쉽지만 빅테크 규모의 트래픽을 감당할 만큼 확장성이 좋지는 않습니다. 수십억 개의 데이터 앞에서는 이 방식은 금방 멈춰버릴 것입니다.

## Level 2: Cache 추가하기

그다음으로 자연스러운 최적화 단계는 Caching입니다.

사용자가 새로운 유저명을 시도할 때마다 데이터베이스를 호출하는 대신, 자주 확인되는 유저명의 임시 복사본을 메모리(Redis나 Memcached 같은 도구 사용)에 보관하는 것입니다.

흐름은 다음과 같습니다.

이 방식은 자주 조회되는 유저명에 대해 아주 효과적입니다. 예를 들어 수천 명의 사용자가 john, alex, princess 같은 이름을 계속 시도한다면, Cache는 데이터베이스를 전혀 거치지 않고도 해당 요청들을 즉시 처리할 수 있습니다.

하지만 Caching은 새로운 고민거리를 안겨줍니다.

## Level 3: Bloom Filters 사용하기

이제부터 정말 흥미로워집니다.

모든 유저명을 메모리에 직접 저장하거나 매번 데이터베이스에 쿼리하는 대신, 어떤 유저명이 존재할 수도 있다는 사실을 알려주는 아주 작은 "지문(fingerprint)"을 저장하면 어떨까요?

이것이 바로 Bloom Filters가 설계된 목적입니다.

Bloom Filter란?

Bloom filter는 "이 유저명이 시스템에 존재할 가능성이 있는가?"라는 질문에 아주 빠르게 답할 수 있는 확률적 자료구조입니다.

Bloom filter는 아주 약간의 false positives(오탐) 확률을 감수하는 대신, 극단적인 속도와 메모리 효율성을 얻는 전략입니다.

Bloom Filter가 강력한 이유

Bloom Filter의 동작 방식

모든 것을 종합하면

여러분이 my_cool_username을 입력하고 엔터를 누를 때, 대규모 시스템의 뒷단에서는 다음과 같은 일이 일어납니다.

이러한 계층적 접근 방식은 각 단계가 수많은 요청을 걸러내는 깔때기처럼 작동하여, 오직 극소수의 요청만이 "비싼" 작업인 메인 데이터베이스까지 도달하도록 보장합니다.

## Level 4: 단순한 조회를 넘어서

지금까지 우리는 단순히 "이 유저명이 존재하는가?"라는 yes/no 확인에 대해서만 이야기했습니다.

하지만 Instagram과 같은 실제 플랫폼은 한 걸음 더 나아갑니다. 만약 당신이 선택한 이름이 이미 사용 중이라면 대신해 사용할만 한 유저명을 제안해주죠.

예를 들어 daniel이라는 유저명이 이미 사용 중이라면, Instagram은 다음과 같은 이름을 제안할 수 있습니다.

이런 기능은 Cache나 Bloom filter보다 더 똑똑한 무언가를 필요로 합니다. 바로 접두사 기반 조회(prefix-based lookups)를 위해 특별히 제작된 자료구조, Trie (Prefix Tree)입니다.

Trie란?

Trie는 문자열을 그들의 공통된 접두사를 기준으로 정리하는 트리 형태의 구조입니다. 유저명을 통째로 저장하는 대신, 한 글자씩 분해하여 공통된 경로를 재사용합니다.

예를 들어:

Trie는 데이터베이스나 Cache가 힘들어하는 다음과 같은 기능들을 가능하게 합니다.

물론 Trie에도 단점은 있습니다.

메모리 사용량을 줄이기 위해, 종종 compressed tries (radix trees)가 사용됩니다. 자식 노드가 하나뿐인 체인을 하나의 엣지(edge)로 압축하여 공간과 조회 단계를 모두 절약함으로써, 이 구조를 대규모 환경에서 더 실용적으로 만들어줍니다.