[1권 - 13장] 검색어 자동완성 시스템

[KimH4nKyul]

[1부 - 테크루타*]
-> 여러분은 책만(또는 이북) 가지고 계시면 되며, 모두 함께 모여 1시간 동안 읽어 나갑니다.
-> 이 시간에는 책을 읽으며, 궁금한 것을 리서치하는 시간입니다.
-> 리서치는 짝꿍과 Pair(최소 2인/최대 3명) 로 진행됩니다. (Pair간 질문이 허용됩니다. 그러나 산만해지는 것을 방지하기 위해 4인 이상의 Group으로 진행하지 않습니다.)
-> 이 과정에서 AI 활용과 검색을 허용합니다.
-> 1시간 내에 정해진 진도를 100% 못나가도 괜찮습니다. 이어지는 2부에서 최대한 배워가길 바랍니다.

테크루타?
나이, 성별, 계급 등에 관계없이 두 명이 짝을 지어 서로 질문하고 답하며 논쟁을 통해 진리를 찾는 학습법인 유대인의 전통적인 토론 교육 방법인 하부루타와 Tech의 합성어

[2부 - 아고라]
-> 1시간 동안 진행됩니다.
-> 1부에서 공부한 내용을 바탕으로 전체 인원과 토론하는 시간을 갖습니다. (필요에 따라 Group을 지을 수도 있습니다.)
-> 누군가 (무엇이든) 모르는 내용이 있다고 하면 친절하게 알려주시길 바랍니다!

[3부 - 정리]
-> 15분 동안 진행됩니다.
-> https://github.com/noanswer-system-design-study/noanswer/discussions
-> 노앤써 레포지토리의 Discussion에 오늘 배운 내용을 모두 정리하는 시간을 갖습니다.
-> 3부에 몰아서 정리하는 것보단 자발적으로 1부, 2부에 걸쳐 수시로 작성해두는 것을 권장합니다.

[KimH4nKyul]

데이터가 많이 흐르는 시스템에서 실시간은 바람직하지 않다고 소개 되어있음

바람직하지 않은 이유와 바람직하지 않지만 실시간이 필요한 경우는 뭐가 있을까요?

[KimH4nKyul]

최종적 일관성은 즉각적인 상태 보장을 못함

[KimH4nKyul]

실시간 처리가 필요할 때

• 데이터를 안전하게 전달 해야 함 -> 수집 시 메시지 큐
• Flink, Storm, Spark Streaming -> 이벤트를 실시간을 집계, 변환/분석해 넘김
• 실시간 처리 결과를 인메모리 저장소에 반영해야 함 -> Redis에 자주 조회되는 데이터나 계산 결과 저장
• 트래픽 부하에 따른 스케일링 -> Nginx, HAProxy 또는 클라우드 로드밸런서

flowchart TD
  %% Ingestion Layer
  subgraph "Ingestion Layer"
    A[사용자 요청] -->|HTTP| LB["로드 밸런서 (Nginx/HAProxy)"]
    LB --> API[API Gateway]
    API --> MQ["메시지 큐 (Kafka/Kinesis)"]
  end

  %% Processing Layer
  subgraph "실시간 스트림 처리"
    MQ --> SP["스트림 프로세싱 (Flink/Storm/Spark Streaming)"]
  end

  %% Storage & Cache
  subgraph "저장소 및 캐싱"
    SP --> IM["인메모리 캐시 (Redis/Memcached)"]
    SP --> DB["NoSQL 데이터베이스 (Cassandra/DynamoDB)"]
  end

  %% Monitoring & Logging
  subgraph "모니터링 및 로깅"
    LB --> MON["모니터링 (Prometheus/Grafana)"]
    API --> LOG["로깅 (ELK Stack)"]
  end

  %% API와 캐시/데이터베이스의 상호작용
  API <--> IM
  API <--> DB

Loading

[KimH4nKyul]

Siemens 에너지 관리 솔루션/빌딩 관리 솔루션 등
넷플릭스, 쿠팡 같은 영상 스트리밍 등
치지직같은 실시간 스트리밍 등

[KimH4nKyul]

@renechoi

• 데이터를 영속화하는 상황에서는 실시간은 적합하지 않음
• 스트리밍 프로세싱에 대한 고려완 다름

[KimH4nKyul]

#23 (comment)

[KimH4nKyul]

트라이 자료구조에서 검색어와 함께 빈도를 저장하는데, 이를 시스템 관점에서 본다면 어떻게 설계되며 어떤 기술을 활용할 수 있을까?

[hyojin202406]

Kafka로 로그 수집하고 Redis에 검색어 저장 및 빈도 증가 후 주기적으로 MySQL에 저장하는 방식은 어떨까요?

[KimH4nKyul]

236p.

Worker -> 비동기 잡, 트라이 자료구조 만듬
Cache -> 트라이 데이터를 캐시(트라이 데이베이스 스냅샷)
Database -> 몽고디비, 레디스 등 도큐먼트 DB나 KV Store

[hyojin202406]

질의당 바이트 단위로 계산하는 이유는 메모리 사용량, 네트워크 전송량, 저장소 크기 등을 예측하기 위함으로 알고 있는데, 실제 현업에서 바이트 기준으로 설계 계획을 한 적이 있는지 경험 공유 요청드립니다.

[KimH4nKyul]

저희가 시스템에서 가용할 수 있는 메모리량이 있잖아요.그렇기 때문에 이 한도를 다 사용하지 않는 선에서 보통은 chunk 단위로 짤라서
예를 들어서, 하나에 48MB 짜리가 있고, 내 시스템에서 가용할 수 있는 게 50~60MB 라고 한다면 한 번에 처리하지 않도 1.2MB 짤라서 처리하는거죠.
"둘 다 상관없고, 애플리케이션 내에서 48MB 되면 터진다."

Node.js에서 처리용량이 높은 요청으로 다음 요청이 죽는ㄴ다.........................

---

@renechoi
DB 스펙을 결정할 때, 기존 데이터를 샘플링해서 가용 수준을 예측함
-> 이 경우에 한글도 바이트를 계산해서 처리함

[Cheondongmin]

트라이 구조에서 검색어 빈도를 저장할 때, 단순 정수값으로 누적 카운팅하는 방식과 최신 검색어에 더 높은 가중치를 부여하는 방식 중에서,
대량의 데이터를 처리하는 시스템에서 성능과 정확도 측면에서 어떤 차이가 발생할까..

또한, 최신 검색어 가중치를 부여하는 방식으로 구현할 경우 주기적인 데이터 정리를 어떤 방식으로 처리하는 것이 효율적일까?

[Cheondongmin]

트라이 갱신 방식

1. 완전 새로 구축 (Full Rebuild)

• 기존 트라이를 전부 삭제하고, 지난 일주일 동안 수집된 검색 데이터를 기반으로 새롭게 트라이를 구성.
• 단점: 트라이가 완전히 새로 만들어지므로, 일부 검색어가 사라질 수 있음.

2.점진적 갱신 (Incremental Update)

• 기존 트라이를 유지하면서, 새로운 데이터를 추가하거나 오래된 데이터를 감쇠하여 업데이트.
• 시간 감쇠 기법을 적용하여, 오래된 검색어의 중요도를 낮추고 일정 빈도 이하의 검색어를 제거.
• 예: weight = (이전 빈도 * 감쇠율) + (최근 검색 빈도) 형태로 업데이트.

3. 이중 트라이 활용 (Double Buffering)

• 새로운 트라이를 주기적으로 생성한 뒤, 기존 트라이와 비교하여 스위칭.
• 일정 주기(예: 1주일)마다 새로운 트라이를 생성한 뒤, 기존 트라이와 비교하여 중요한 검색어는 유지하고, 최신 검색어를 추가.
• 시스템 중단 없이 새로운 데이터를 적용 가능.

[KimH4nKyul]

@김동하
로그성 데이터? 통계성 데이터? -> 235p
어떤 검색어가 언제 검색 되어있는 지 저장하는 테이블과 취합된 결과 데이터 테이블(언제 몇 번 검색 되었는데, 누적 횟수로 되어있었음)

[KimH4nKyul]

@고려진
더 높은 가중치를 부여하는게 뭔가요?
-> 과거 데이터에 비하여 중요한 데이터에서 더 높은 우선순위를 부여하기 위해 사용되는 값

[cruellaDev]

평균적인 상황 가정 외에 국가적 이슈나 외부적 사건으로 인해 검색어가 폭발적으로 증가하는 스파이크(traffic spike) 상황에 대해서는 어떻게 대비해야 할까?
예) 계엄령

[cruellaDev]

임시 데이터 저장소 구성

클라이언트
    │
    ├──→ 긴급 Trie(Hot 키워드 전용)
    │
    ├──→ Redis 임시 캐시 레이어 (급증 검색어 저장)
    │
    └──→ 기존 API서버 → Elasticsearch (기존 데이터)

[renechoi]

검색어 자동 시스템에서 실제 검색 요청이 작동하는 방식

• 문자열을 끊어서 보내게 됨: e.g. dinner -> d, di, din, dinn, dinne, dinner

1. 검색어 자동완성 시스템은 단어를 모두 입력하기 전에도 부분 문자열에 대한 연관 검색어를 즉각적으로 제시한다.
2. 예를 들어 "dinner"를 입력하면, 'd', 'di', 'din' 등 각 입력마다 새로운 연관 검색어 요청이 발생한다.
3. 이를 통해 사용자는 빠르게 원하는 검색어를 찾을 수 있고, 입력 중 방향 전환이나 오타 수정을 하기도 쉽다.
4. 모든 글자를 다 입력한 뒤 한 번만 요청하면 실시간 피드백이 떨어져 사용자 경험이 저하된다.
5. 결국 "dinner"라는 단어를 입력할 때는 각 글자마다 총 6번의 요청이 순차적으로 발생한다.

---

tw 로 시작하는 단어가 여러개 저장해둔 rdb 테이블이 있다고 했을 때 like + orderby 검색으로 5개 limit 걸어서 요청했을 때의 시간 복잡도는 어떻게 될까? 그리고 이 방식은 왜 데이터베이스 병목을 잠재적으로 갖고 있을까?

1) LIKE + ORDER BY + LIMIT 쿼리의 시간 복잡도

• 인덱스가 적절히 구성된 경우

  • word 컬럼에 대해 B-Tree 형태로 정렬된 인덱스가 있고, WHERE word LIKE 'tw%'가 “tw”로 시작하는 범위 스캔(Range Scan)으로 처리될 수 있다면,
    • 인덱스 트리를 찾는 데 O(log N), 실제로 필요한 상위 5개만 가져오므로 추가 조회 비용은 상대적으로 작습니다.
    • 정렬(ORDER BY) 기준이 word 그대로이거나 인덱스 컬럼과 동일하면, 별도 정렬 과정 없이 인덱스 순서대로 상위 5개를 추출할 수 있습니다.
    • 이 경우 대략 O(log N + 5) 정도로 볼 수 있으며(5 대신 일반화하면 K), 이는 꽤 효율적입니다.

• 인덱스가 없거나 인덱스를 효율적으로 사용 못하는 경우

  • WHERE word LIKE '%tw%'처럼 접두어가 아닌 형태이거나, ORDER BY가 전혀 다른 컬럼에 걸려 있어 인덱스를 못 쓰는 상황이라면,
  • 테이블 혹은 인덱스 전부를 스캔(Full Table Scan 혹은 Full Index Scan)하고, 그 결과를 정렬 + 상위 5개만 취해야 할 수 있습니다.
  • 이 경우 최악으로는 O(N log N)(정렬 비용 포함) 수준까지 갈 수도 있습니다.

즉, 인덱스가 잘 구성되어 있고 LIKE 조건이 접두어 매칭으로 인덱스 범위 스캔(Range Scan)이 가능하면, 시간 복잡도는 O(log N + K)에 가깝게 나올 수 있으나, 그렇지 않다면 O(N log N) 혹은 **O(N)**에 가까운 비용이 들 수 있습니다.

---

2) 왜 데이터베이스 병목이 발생할 수 있는가?

1. Keystroke마다 쿼리 발생: 자동완성 시나리오에서는 사용자가 한 글자 입력할 때마다(예: "t" → "tw" → "twi" …) 매번 DB에 쿼리를 날리게 됩니다. 한 글자 입력마다 짧은 시간 내에 결과를 반환해야 하므로, DB 부하가 단기간에 매우 집중될 수 있습니다.

2. 대량의 동시 요청: 대규모 서비스에서 많은 사용자가 동시에 입력 중이라면, DB는 매우 빈번한 LIKE + ORDER BY + LIMIT 쿼리를 처리해야 하고, 이는 곧 트랜잭션 처리나 커넥션 수 증가, CPU/IO 사용량 증가로 이어져 병목이 발생할 수 있습니다.

3. 정렬/스캔 비용: 인덱스를 잘 활용할 수 없는 경우(ORDER BY 컬럼 불일치, 접두어가 아닌 LIKE 검색 등) DB는 Full Scan + 정렬 과정을 거쳐야 하므로, 많은 레코드가 있을 때 CPU와 디스크 I/O가 크게 증가해 성능 저하로 이어집니다.

4. DB 자원의 한계: RDB 자체가 다른 트랜잭션 처리도 해야 하며, 데이터 정합성(ACID)을 보장하기 위한 부하도 존재하므로, 빠르게 늘어나는 검색 요청을 처리하기에는 스케일 아웃(Scale-out)이 한계가 있을 수 있습니다.

결과적으로, 간단한 LIKE + ORDER BY + LIMIT 쿼리라도, 검색 자동완성과 같은 빈번한 단건 호출이 대규모로 쏟아질 경우, DB가 병목 지점이 되어 응답 지연과 서비스 성능 저하가 발생할 수 있습니다. 이런 이유로 실제 시스템 설계에서는 Redis 등 인메모리 캐시나 트라이(Trie), 서치 엔진(ElasticSearch/Solr) 등의 전문 검색 인덱스를 활용한 구조로 확장성을 확보하는 방법을 많이 사용합니다.

---

트라이 구조로 노드 검색을 할 때, 알고리즘을 생각해보면 p가 접두어의 길이, n이 트라이 안에 있는 노드 개수, c가 주어진 노드의 자식 노드 개수라 할 때 시간 복잡도는 O(p) + O(c) ) O(clogc)가 되는데, 이 알고리즘은 직관적이지만 최악의 경우 k개의 결과를 얻으려고 전체 트라이를 다 검색해야 할 수 있습니다. 이 문제를 해결하는 방법 두가지는 ? 그리고 시간 복잡도는 어떻게 개선될까?

1. 접두어의 최대 길이 제한 => O(p)를 O(1) 로
2. 각 노드에 인기 검색어 캐싱 => O (c) + O(clogc)를 ???

=> 마찬가지로 상수가 됨
즉 둘 다 O(1), O(1) => 상수 시간 처리 가능

---

트라이 내부의 인기 검색어를 캐싱하는 방법에 대해서 설명해보자

1. 데이터 구조 설계

1. 각 노드(TrieNode)에 Top-K를 저장할 자료구조 선택

   • Min-Heap
     • 크기 K를 가지는 최소 힙(Min-Heap)으로 관리.
     • 새 검색어 혹은 인기도가 갱신될 때, 힙의 루트(가장 인기도가 낮은 검색어)와 비교 후 필요하면 대체(pop+push)하여 K개를 유지.
     • 힙에서 최대값 순으로 바로 나열하려면 추가 작업이 필요하지만, K가 작을 경우 비용이 크지 않음.
     • 삽입 및 삭제 연산이 O(log K).
   • 정렬된 배열/리스트
     • K가 매우 작다면, 삽입 시 이진 탐색으로 적절한 위치를 찾아 O(log K + K) 정도(배열 shifting 비용 고려)로 업데이트 가능.
     • Top-K를 이미 정렬 상태로 유지하기에 반환 시 O(K)로 바로 사용 가능.
   • 균형 트리(예: Balanced BST, Red-Black Tree)
     • 삽입/삭제/탐색 모두 O(log K).
     • 구현 복잡도가 다소 높을 수 있음.

   일반적으로 Min-Heap이 단순하면서도 삽입/삭제 비용이 예측 가능하므로 많이 사용됩니다.

2. Top-K에 저장되는 요소

   • 전체 단어(검색어) 문자열: “twice”, “twitter”, “twitch” 등.
   • 인기도(검색 빈도, 조회수 등): 정수 혹은 가중치.
   • (선택) 추가 메타데이터: 예를 들어 최근 검색 시간, 특정 카테고리 등.

2. 갱신(업데이트) 알고리즘

트라이를 이용할 때, 보통 단어 삽입 혹은 인기도 업데이트는 “Root → 해당 단어의 마지막 노드(leaf)”까지 경로를 따라가며 처리됩니다. 이 과정을 응용하여 경로상의 모든 노드의 Top-K도 함께 갱신합니다.

1. 새로운 단어(검색어) 삽입

   • 예: 사용자가 처음으로 "twitter"라는 검색어를 이용하거나, 혹은 데이터에 새롭게 추가.
   • 트라이 루트에서 시작해 각 문자를 따라 노드를 탐색(“t”→“w”→“i”→“t”→“t”→“e”→“r”).
   • 각 노드에서 다음을 수행:
     1. 현재 노드의 Top-K 구조(힙 또는 정렬 리스트 등)를 확인한다.
     2. 아직 K개 미만이면 그냥 삽입하고, K개 이상이면 최솟값(또는 필요 시점)과 비교해 인기도가 더 크면 교체한다.
   • 삽입 연산이 완료되면, 각 노드의 Top-K는 “twitter”를 반영한 상태가 된다.

2. 인기도(검색 빈도) 갱신

   • 예: “twitter”가 기존에 존재하는 검색어인데, 추가로 검색되어 인기도 +1.
   • 마찬가지로 루트에서 해당 단어를 찾아 내려가면서, 각 노드에서 Top-K를 갱신한다.
   • 이 때, 이미 Top-K에 있는 항목이면 인기도만 갱신하고 재정렬 혹은 힙에서 재구성.
   • 만약 Top-K 바깥에 있던 검색어가 갱신 후 인기도가 높아져서 Top-K로 진입해야 한다면, 최솟값(힙 루트)과 비교하여 교체한다.

3. 삭제(선택 사항)

   • 검색어가 더 이상 유효하지 않거나(예: 제거), 인기도를 감소시켜야 하는 경우에도 비슷한 로직으로 처리.
   • 트라이 경로를 따라가며 기존 Top-K에서 제거하거나, 인기도가 낮아져 순위권 밖으로 밀려나면 교체한다.

**경로 길이가 p(접두어 길이)**라면, 각 노드마다 Top-K 구조 갱신에 드는 시간은 O(log K) (Min-Heap 기준) 정도이므로, **총 O(p log K)**가 소요됩니다.

그렇다면 트라이를 구성하는 삽입 삭제 연산에서 캐싱을 할때와 하지 않을 때 시간 복잡도 차이는 ?

1. 캐싱하지 않는 경우

삽입/삭제/인기도 변경 시

• 단순히 “해당 단어를 트라이에 삽입/삭제” 혹은 “인기도 카운트를 갱신”하는 작업은,
  • 접두어 길이 p만큼 내려가면서 노드를 만들거나 카운트를 갱신하면 끝입니다.
  • 즉, 갱신 작업 자체는 O(p) 정도로 처리 가능.
• 캐싱을 안 쓰므로, 노드별 Top-K 갱신은 별도로 하지 않습니다(= “필요할 때마다 서브트리를 뒤져서 구한다”는 방식).

정리:

• 업데이트(삽입/삭제/인기도 변경): O(p)

---

2. 캐싱을 사용하는 경우

삽입/삭제/인기도 변경 시

• 새로운 검색어(단어) 삽입·삭제·인기도 변경 시, 루트부터 해당 단어의 말단 노드까지(p 길이) 내려가면서, 각 노드가 자신의 Top-K를 갱신해야 합니다.
• 노드별 Top-K는 흔히 Min-Heap(크기 K)으로 관리하므로, 한 노드 갱신에 O(log K),
• 경로상 p개 노드에 대해 수행하므로, **총 O(p log K)**가 됩니다.

정리:

• 업데이트(삽입/삭제/인기도 변경): O(p log K)

---

3. 요약 비교

구분	캐싱 없이	캐싱 사용 시
조회(Top-K 검색)	O(p + c log c) (c: 서브트리 노드 수)	O(p + K)
업데이트(삽입/삭제 등)	O(p)	O(p log K)

• 캐싱 없음:

  • 조회할 때마다 트라이 서브트리를 전수 검색 + 정렬해야 하므로, 사용자가 많고 c가 큰 경우 실시간 자동완성에서 큰 지연이 발생.
  • 대신 삽입/삭제는 빠름(O(p)).

• 캐싱 있음:

  • 조회(자동완성) 속도는 매우 빨라짐(O(p + K)).
  • 반면, 삽입/삭제나 인기도 변경 때마다 경로상의 모든 노드에 대해 “Top-K 구조(힙/정렬 리스트)”를 갱신해야 하므로 O(p log K) 시간이 듦.
  • 메모리도 더 많이 사용하고, 동시성 처리(lock 관리 등)도 고려해야 함.

동시성 처리가 필요한 이유는 무엇 때문일까 ?

검색어 자동완성 기능은 동시에 많은 사용자가 검색 창에 문자를 입력하고, 검색어 데이터를 갱신(인기도 업데이트 등)할 수 있기 때문에 **“여러 명이 동시에 해당 자료구조(트라이, 캐시 등)에 접근”**하는 상황이 빈번합니다. 이때 동시성 처리를 고려하지 않으면 아래와 같은 문제가 생길 수 있습니다.

1. 데이터 무결성(Consistency) 손상

   • 여러 스레드(또는 프로세스)가 같은 노드를 동시에 업데이트하면, Top-K 캐시에 서로 다른 상태가 덮어씌워지거나 인기도 카운트가 잘못 계산될 수 있습니다.
   • 예컨대 A 사용자와 B 사용자가 거의 동시에 “twitter”를 검색했는데, 인기도가 1만 증가한 상태로 반영될 수도 있습니다(원래는 +2가 되어야 함).

2. 레이스 컨디션(Race Condition)

   • 한 요청이 해당 노드의 Top-K 리스트를 갱신하려고 하는 순간, 다른 요청도 같은 노드를 갱신하면 갱신 순서에 따라 최종 결과가 달라집니다.
   • 동시성 제어가 없으면 최종 결과가 예측 불가능해져, 비정상적인 상태가 됩니다.

3. 잘못된 캐시 상태(오류 전파)

   • 어떤 노드에서 Cache Miss나 잘못된 Top-K가 발생하면, 이를 재사용하는 상위 혹은 하위 노드에서도 영향을 받아 전체 검색 결과가 왜곡될 수 있습니다.

4. 장애나 성능 문제

   • 잠금(lock)이나 동시성 제어가 제대로 되어 있지 않으면, 데이터 정합성을 맞추기 위해 낮은 수준에서 매우 많은 락 충돌이 발생하거나, 서비스가 불안정해질 수 있습니다.
   • 잘못된 접근 순서 때문에 데드락(Deadlock)이나 무한 대기 등의 문제가 생길 수도 있습니다.

결국, 많은 사용자가 동시에 조회(검색)와 갱신(인기도 변경, 새로운 검색어 등록)을 요청하는 대규모 환경에서, 트라이나 노드별 Top-K 캐시 같은 자료구조를 안전하게 다루기 위해서는 동시성 제어가 필수입니다. 이를 통해 데이터 무결성과 일관성을 유지하면서, 정상적인 검색 결과를 빠르게 제공할 수 있게 됩니다.

트라이를 저장할 DB 중 도큐먼트 DB를 사용한다면 어떻게 ?

1. 기본 아이디어와 고려사항

1. 트라이 노드 = 하나의 도큐먼트

   • 각 노드는 prefix, children, topK, 그밖에 메타데이터를 하나의 문서(document) 로 저장.
   • [예시] "prefix": "tw", "children": ["twi", "two", "twe"...], "topK": [{word: "twitter", freq: 120}, ...]

2. 계층 구조(중첩 vs. 참조) 결정

   • 중첩(Embedded) 방식: 트라이 깊이가 얕다면, 한 문서 안에 children 노드들을 중첩 배열로 넣을 수도 있음.
   • 참조(Reference) 방식: 노드가 많거나 트라이가 깊다면, children을 ID(혹은 prefix)를 통해 참조(링크)만 가지고, 실제 자식 노드는 별개의 문서로 저장.

3. 문서(노드) 업데이트 방법

   • 트라이 노드에 삽입·삭제·인기도 변경이 있을 때, 해당 prefix를 가진 문서를 찾아가 children 배열/Top-K를 수정하고, DB에 문서 단위로 갱신(partial update).
   • 만약 중첩 구조가 깊다면, 부분 업데이트(예: MongoDB의 $set, $push 등)로 특정 필드만 업데이트.
   • 동시성이 많은 경우, Document DB에서 제공하는 원자적 갱신(Atomic Update), Optimistic Locking 등을 고려해야 함.

4. 데이터 분할(Sharding) 전략

   • 대규모 데이터에서 수평 확장(Sharding)이 필요하다면, “prefix”를 샤딩 키로 삼거나, “문서 ID(해시)”를 기준으로 자동 분산.
   • 하지만 “접두어별로 특정 샤드에 몰리는 핫스팟”이 생길 수 있으므로 주의해야 함. 예: “t”로 시작하는 단어가 압도적으로 많다면 특정 샤드에 부하 집중.

2. 예시 스키마 설계

예를 들어, MongoDB를 사용한다고 가정합시다. trieNodes 라는 컬렉션(테이블 개념에 해당)을 만들고, 각 노드(접두어)를 다음과 같이 저장합니다:

{
  "_id": "tw",               // 문서 고유 ID, 보통 prefix나 ObjectId 사용
  "prefix": "tw",            // 이 노드가 담당하는 접두어
  "children": [
    "twi", "two", "tws"      // 자식 노드들의 식별자(= prefix)
  ],
  "topK": [                  // 상위 K개 인기 검색어(캐싱)
    { "word": "twitter", "freq": 120 },
    { "word": "twitch", "freq": 90 },
    { "word": "twice", "freq": 80 }
    // ...
  ],
  "updatedAt": ISODate("...")  // 최근 갱신 시각 등 메타필드
}

• prefix: "tw"라는 접두어를 표현.
• children: "tw" 노드 아래, "twi", "two", "tws" 등으로 이어지는 자식 접두어가 있을 수 있음.
• topK: "tw"로 시작하는 실제 단어 중 “인기가 높은 K개”를 캐싱.
  • 예: "twitter", "twitch", "twice" 등.
  • freq는 인기도(검색 카운트) 등 가중치.

중첩 구조 vs. 참조 구조

• 참조(Reference) 구조: 위 예시처럼 자식들의 prefix를 배열로 들고, 실제 자식 노드 정보는 별도 문서에 저장. (각 노드가 컬렉션 내에서 _id = prefix로 식별 가능)
• 중첩(Embedded) 구조: 아래처럼 하나의 문서에 자식 노드까지 전부 중첩해서 넣으면, 노드 수가 많아질 경우 문서가 너무 커져서(예: MongoDB 16MB 제한) 한계에 부딪힐 수 있음.

3. 작동 원리 (CRUD 및 검색)

아래는 “문서 단위”로 트라이를 운용할 때의 일반적인 시나리오입니다.

3.1 검색(조회)

1. 사용자가 'tw'를 입력

   • 애플리케이션 서버(혹은 서비스 계층)에서 _id = "tw" 혹은 prefix = "tw" 로 trieNodes 컬렉션을 조회.
   • 결과 문서를 불러오면, 그 안에 topK 배열이 있으므로 즉시 상위 검색어 K개를 반환.
   • 더 세부적인 하위 검색어를 보고 싶다면 “children”에 나열된 "twi", "two", ..." 등의 노드를 재귀적으로 불러올 수도 있음. (하지만 일반적으로 자동완성은 “topK”만 바로 제공하고 끝나는 경우가 많음)

2. 만약 캐싱이 없고, 서브트리 전체에서 Top-K를 찾아야 한다면?

   • “tw” 노드뿐 아니라, “twi” / “twe” / “two” 등 자식 노드를 전부 불러와서(재귀), 실제 단어 리스트를 모은 뒤, 인기도 순으로 정렬 → 상위 K개 뽑아야 함.
   • 이는 도큐먼트 DB에서 여러 번의 find() + 애플리케이션 레벨에서 재귀 탐색이 필요하므로, 데이터가 많으면 비효율적.
   • 그렇기 때문에 각 노드에 미리 Top-K를 저장해두는 캐싱이 필수적으로 고려되는 이유임.

3.2 삽입(새로운 검색어 추가)

예: 새 단어 "twirly"가 추가되었다고 가정합시다.

1. 트라이 경로 찾기

   • 루트(prefix="") → "t" → "tw" → "twi" … 이런 식으로 DB에서 차례대로 문서를 찾으며, 해당 prefix가 없다면 문서를 새로 생성.
   • 최종적으로 “twirly”의 마지막 노드(“twirly” 자체를 prefix로 하는 노드)까지 생성 또는 업데이트.

2. 각 노드의 topK 갱신

   • “t” 노드 문서를 불러와 topK에 “twirly”를 인기도 1(혹은 0)로 삽입할지 결정.
   • 만약 topK가 K개 미만이면 삽입, 이미 K개면 최소 freq와 비교하여, 더 작으면 무시, 더 크면 교체.
   • 이를 “tw”, “twi”, “twir” 노드까지 재귀적으로 수행.
   • 각 노드에서 MongoDB의 $set, $push, $pop(또는 배열 필드 조작) 등을 이용해 문서 부분 업데이트.

3. 동시성 처리

   • 여러 사용자가 동시에 “twirly”와 “twisty” 등 다른 검색어를 추가하는 상황이 있을 수 있음.
   • 도큐먼트 DB의 원자적 수정 연산(findAndModify, $set, $push 등) 또는 Optimistic Lock(Version 필드) 기법을 이용해 경합을 조정.

3.3 인기도(freq) 변경(업데이트)

예: 기존 단어 “twitter”가 한 번 더 검색돼서 인기도가 120 → 121이 되어야 한다고 하겠습니다.

1. 경로에 해당하는 노드들: prefix="t", "tw", "twi", "twit", "twitt", "twitte", "twitter" 등.
2. 각 노드를 갱신
   • “tw” 노드 문서를 find → topK 배열에서 "twitter" 항목을 찾아 freq=121로 갱신 → 힙/정렬 기반으로 다시 정렬 → $set으로 반영.
   • 하위 노드들도 동일 과정 반복.
3. 부분 업데이트
   • MongoDB 같은 경우, $[<identifier>](arrayFilters) 문법을 사용하면, topK 배열 중 특정 조건(word=="twitter")인 요소만 업데이트하는 것도 가능.
   • 이렇게 하면 “문서 전체”를 갈아치우지 않고 필요한 부분만 원자적으로 수정 가능.

3.4 삭제

1. 어떤 검색어가 “더 이상 유효하지 않다”거나, 인기도를 0으로 리셋해야 한다면, 동일하게 경로 노드들에서 topK를 점검하여 해당 항목을 제거.
2. 실제 prefix 노드를 완전히 삭제할지, 혹은 빈 노드로 남길지는 서비스 로직에 따라 결정.

4. 성능 및 확장성 이슈

1. 문서 크기 제한

   • 한 문서(= 한 노드)에 자식 정보, topK, 메타데이터를 너무 많이 넣으면 문서 자체가 커질 수 있음(예: MongoDB 16MB 제한).
   • 이를 피하기 위해 레벨별로 자식 노드들을 “shard”하거나, “topK”만 저장하고 나머지 세부 정보는 다른 컬렉션/테이블에 분산 저장하기도 함.

2. 캐싱 vs. 업데이트 빈도

   • 트라이 노드에 topK를 캐싱하면, 조회(검색)는 빨라지지만 삽입/업데이트 시 여러 노드를 수정해야 하므로 I/O가 증가.
   • 읽기(조회) 빈도가 압도적으로 많을 때 유리한 구조.

3. 샤딩(Sharding) / 파티셔닝

   • “prefix”를 샤딩 키로 사용하면 접두어별로 데이터가 분산될 수 있음.
   • 다만 특정 알파벳/언어 등 쏠림이 심한 경우 핫스팟(Hotspot)이 발생 → “해시 기반” 파티셔닝을 고려할 수도 있음.

4. 동시성, 락

   • Document DB는 일반적으로 문서 단위(혹은 컬렉션 단위) 락/원자 연산을 제공.
   • 동시에 여러 노드(prefix)에 쓰기가 들어올 경우 락 충돌이나 갱신 순서 문제가 발생할 수 있으므로, Optmistic Locking 또는 Conflict Handling 로직이 필요.

5. 대안: 인메모리 Trie + 도큐먼트 DB 영속화

   • 실제로는 도큐먼트 DB를 “영구 저장 / 백업 / 재시작 시 로드” 용도로 활용하고,
   • 실시간 자동완성은 메모리에 띄운 Trie(혹은 서치 인덱스)에서 처리 → 쓰기(인기도 갱신 등)가 많아도 메모리에서 빠르게 처리 후, 일정 주기마다(또는 비동기) DB에 batch로 반영하는 방식을 많이 택함.

---

5. 요약

• 도큐먼트 DB로 트라이 구현 시, 가장 기본적인 패턴은 “노드마다 하나의 문서”를 저장하고, prefix, children, topK를 필드로 관리하는 것입니다.
• 검색어 조회 시 해당 prefix 노드의 문서를 빠르게 찾고, topK 배열을 곧바로 반환하여 자동완성 결과를 제공합니다.
• 새 검색어 삽입, 인기도 업데이트 등 갱신 작업 때는, 접두어 경로에 해당하는 노드 문서를 순차적으로 찾아가면서 부분 업데이트(Partial Update)를 수행합니다.
• 이 방식은 RDB보다 중첩 구조나 JSON 문서 업데이트가 편리하지만, 노드가 많아지면 문서 크기, 샤딩, 동시성 등 문제를 세심하게 관리해야 합니다.
• 결국 실시간 성능을 위해서는 인메모리에서 Trie를 운용하고, 도큐먼트 DB는 데이터 영속성, 백업, 통계 등에 활용하는 하이브리드 구조가 실무에서 더 흔하게 사용됩니다.

트라이 DB를 K-V로 한다면 어떻게?

키-값(K-V) 스토어를 사용해 트라이를 관리하려면, 보통 **“prefix를 Key”**로 두고, “해당 노드 정보(자식, Top-K, 메타데이터 등)를 Value로 직렬화”하는 방식으로 설계합니다.

1. 노드 저장 구조

   • Key: "tw" 같은 접두어(prefix).
   • Value: JSON 또는 직렬화된 구조에 children (ex. [“twi”, “two”])와 topK (ex. [ {word: “twitter”, freq: 120}, … ]) 등을 저장.
   • Redis나 Cassandra 같은 K-V 스토어에서 key=“tw”를 GET하면, 해당 노드의 전체 정보가 반환됩니다.

2. 검색(조회) 시나리오

   • 사용자가 “tw” 입력 → K-V 스토어에서 key=“tw”를 조회(GET) → value 안의 topK 목록 즉시 반환.
   • 더 깊이 탐색이 필요하다면, children 배열에 있는 prefix 키들(예: “twi”)을 재귀적으로 GET할 수도 있음.
   • 캐싱: 자주 조회되는 prefix는 애플리케이션 측에 캐싱하거나, K-V 스토어 자체의 인메모리 캐시 활용.

3. 삽입/업데이트

   • 예: “twirly” 단어 추가 → “t”, “tw”, “twi”, “twir”, “twirl”, “twirly” 노드 키들을 순차적으로 GET한 뒤, 각 노드의 topK에 새 단어와 인기도를 반영해 PUT(SET)으로 갱신.
   • Min-Heap 또는 정렬 리스트로 관리하며, 새 인기도가 기존 항목 중 최소값보다 크면 교체.
   • 여러 노드 갱신 시, 키 단위 원자 연산이 부족할 수 있으므로, 분산 락(RedLock 등)이나 Optimistic Locking(버전 필드) 기법을 쓸 수 있음.

4. 장단점

   • 장점: Key를 직접 지정해 빠르게 접근 가능, 분산/샤딩이 용이(특히 Redis Cluster, Cassandra 등). 인메모리(K-V)라면 조회가 매우 빠름.
   • 단점: 복잡한 질의나 다중조건 검색이 어렵고, 트랜잭션(ACID)이 제한적일 수 있음. 노드마다 별도의 키 갱신이 필요해, 삽입·업데이트가 빈번하면 관리가 까다로울 수 있음.

결론적으로, “Key=접두어, Value=직렬화된 노드 정보” 방식으로 트라이를 K-V 스토어에 구성하고, 검색 시에는 Key 접근만으로 O(1)에 노드 정보를 획득해 Top-K를 반환합니다. 삽입·삭제·인기도 갱신 등은 노드 경로마다 K-V 업데이트를 수행하며, 동시성 제어나 분산 처리 방식을 적절히 설계해야 합니다.

=> 트라이 구조는 대개 메모리에 유지하고, DB는 백업/재구축 및 통계 분석 용도로 쓰는 형태가 많다고 함
=> 실제 대규모 시스템은 이러한 이원화 구조로 접근해 성능(메모리 검색)과 영속성(DB 저장)을 균형 있게 달성함.

---

트라이를 분산환경에서 사용할 수 있도록 규모 확장성에 대해 논의해봅시다. 단순하게 샤딩을 생각해볼 수 있는데 영어 지원을 기준으로 생각해보면, 기본적으로는 총 26개 서버가 필요할 겁니다. 그리고 그 하위의 알파벳을 샤딩하려면 이제 계층적으로 샤딩을 할 수 있겠죠? 그런데 이 방식은 그럴듯해보이지만 c로 시작하는 단어가 x보다 많다는 점을 감안할 때, 균등하게 배분하기가 어려워집니다. 그럼 이 문제를 해결하는 방법은 무엇이 있을까요 ?

트라이(Trie)를 여러 노드(서버)로 분산(샤딩)해서 운영할 때, 가장 큰 이슈는 데이터(접두어) 분포가 불균등하다는 점입니다. 예컨대 c로 시작하는 단어가 압도적으로 많다면, “c” 노드를 담당하는 서버가 과부하(핫스팟)가 되어버릴 수 있습니다. 아래는 그 문제를 해결하기 위한 대표적인 방법들입니다.

1. 해시 기반 파티셔닝(Hash Partitioning)

1. 접두어(또는 전체 단어)에 대해 해시를 적용

   • 예: shardKey = hash(prefix)
   • 이렇게 하면 특정 알파벳(c vs. x) 쏠림 문제가 완화되어, 전체적으로 균등 분산을 기대할 수 있음.
   • 일반적으로 접두어 문자열 전체(혹은 일부)를 해시한 뒤, 샤드 수 m으로 mod 연산을 적용해 샤드 인덱스를 결정합니다.

2. 장점

   • 분포가 균등해지기 쉽고, 키 충돌이 적어지는 효과.
   • 간단한 구현(해시 함수 + mod).
   • 핫스팟을 상당 부분 방지.

3. 단점

   • “사전 순” 혹은 “가까운 prefix끼리 같은 샤드에 있어야” 하는 요구가 있을 경우, 해시로 인해 연관된 데이터가 뿔뿔이 흩어질 수 있습니다.
   • 특정 접두어 트리를 한 번에 스캔해야 하는 경우(예: “c” 노드 전체 서브트리)를 여러 샤드에 걸쳐 병렬로 요청해야 해서 조회 복잡도가 오를 수 있음.

2. 범위+해시 혼합 파티셔닝(Composite Key)

1. 일단 가장 상위 레벨(혹은 n글자)로 대범위 구분

   • 예: 알파벳 26개를 크게 2~4개 구간으로 묶는다(“a–f”, “g–p”, “q–z”)
   • 또는 접두어의 첫 2글자를 통해 “aa–az / ba–bz / …” 같은 대략적 범위로 분리.

2. 각 범위 내부에서는 해시를 사용

   • 예: “c”로 시작하는 단어가 너무 많으면, "c + hash(나머지 prefix)"를 샤딩 키로 사용.
   • 이렇게 하면 “대분류(첫 글자/두 글자)”로 1차 분할을 하되, 구간 내부에서는 해시로 고르게 분산.

3. 장점

   • 아주 빈번한 조회가 특정 알파벳에 몰려도, 해시가 2차로 분산시켜주어 서버 부하가 나눠짐.
   • 어느 정도 “접두어 인접성”을 유지할 수 있지만, 완전히 해시만 쓰는 것보다는 나름 구조를 살린 방식.

4. 단점

   • 설계가 다소 복잡하고, 어느 수준에서 범위를 끊을지 결정이 필요.
   • 일부 구간이 전체의 대부분을 차지하면(예: “c”가 40% 이상) 여전히 해당 구간 안에서 핫스팟이 생길 수 있음 → 구간을 세분화하는 동적 분할 로직이 필요할 수 있음.

3. 동적 분할(Hot Spot Detection & Split)

1. 실시간 모니터링

   • 특정 노드(예: “c”)나 특정 접두어 영역에서 질의가 급증하면, 해당 파티션(샤드)을 동적으로 분할.
   • 파티셔닝 메타데이터(Shard Metadata)에서 “c” 노드 하나만 별도로 나누어주거나, “c + 더 세분화” 기준으로 나눔.

2. 샤드 자동 분할 기법

   • HBase나 Cassandra처럼 LSM-Tree 기반 스토어는 SSTable 단위로 splits/merges를 수행하기도 함.
   • 만약 직접 구현한다면, “부하가 일정 임계치 이상”인 샤드(“c”)를 한 번 더 해시 or 범위 분할해서 두 서버로 나누는 방식을 적용.

3. 장점

   • 자주 접두어가 몰리는 영역을 유연하게 스케일 아웃 가능.
   • 초기에 알파벳마다 균등 분산이 안 되어도, 사용 패턴을 보며 점진적 재샤딩 가능.

4. 단점

   • 복잡한 구현: 샤드 재분할 시 데이터 이동이나 트라이 인덱스 재구성이 필요.
   • 순간적인 서비스 부하 또는 키 분포 변화에 따라, 재분할을 자주 해야 할 수도 있음.

4. 트라이 대신 검색 엔진(ElasticSearch/Solr) 활용

• 완전히 다른 관점으로, Elasticsearch 또는 Solr와 같은 분산 검색 엔진은 이미 인덱스 샤딩과 자동 밸런싱 메커니즘을 갖추고 있습니다.
• “접두어 검색”을 n-gram / edge n-gram 등으로 인덱싱하면, 자동완성 기능을 거의 트라이처럼 빠르게 지원.
• 이 방식은 스케일 아웃과 “불균등한 데이터 분포” 문제를 엔진이 내부적으로 해결해주므로, 자체 트라이를 분산하는 것보다 개발 노력이 훨씬 적을 수 있습니다.

5. 결론 및 권장 패턴

1. Naive(알파벳 기반) 파티셔닝은 직관적이나, 특정 알파벳에 데이터가 몰리면 심각한 핫스팟이 생깁니다.
2. 해시 기반 파티셔닝이 가장 단순하면서도 균등 분산에 효과적이며, 접두어 전체 트리 스캔이 필요한 경우만 주의하면 됩니다.
3. 범위+해시 혼합 또는 동적 분할 기법을 이용해, 실제 트래픽 패턴에 맞춰 적절히 샤드를 세분화하면서 핫스팟을 줄일 수 있습니다.
4. 때로는 분산 검색 엔진(Elasticsearch 등)을 활용해 자동완성을 구현하는 것이, 자체 트라이를 분산해서 운영하는 것보다 더 쉽고 안정적인 선택지입니다.

결국, “균등한 분산”과 “접두어 연관성”이라는 상충된 요구사항을 어디서 타협할지가 핵심인데, 해시 또는 혼합 기법을 통해 핫스팟을 완화하면서, 필요하면 동적 재분할을 적용하는 것이 일반적인 해결책입니다.

---

지금까지 작성한 방식에서 트라이 갱신 주기를 1주일이나 1일로 한다고 했을 때, 실시간 변하는 검색어 추이는 반영이 안됩니다. 그렇다면 이렇게 완전 실시간 검색어 니즈를 반영하고자 한다면 어떻게 설계를 변경 / 개선해야 할까요 ?

트라이(Trie)를 배치(batch) 방식으로 1일 혹은 1주 단위로만 갱신하면, 그 사이에 발생하는 **실시간 검색어 변화(특히 급상승 검색어)**를 반영할 수 없다는 문제가 있습니다. 이때 **“실시간(혹은 근실시간)으로 인기 검색어 변화를 반영”**해야 한다면, 보통 아래와 같은 하이브리드 구조나 스트리밍(Streaming) 업데이트 기법이 사용됩니다.

1. 인메모리(In-memory) 트라이 + 배치 DB(백엔드) 갱신

1. 실시간 트라이

   • 애플리케이션 서버(혹은 전용 캐시 서버) 메모리에 트라이를 띄워서, 사용자 검색 시 직접 갱신(검색 빈도 +1)하고, 자동완성에 바로 반영.
   • 이렇게 하면 입력한 순간 바로 인기도가 상승된 검색어가 반영될 수 있음(물론 트라이의 노드마다 Top-K를 업데이트하는 비용이 들지만, 메모리 접근이므로 매우 빠름).

2. 배치(Batch) DB 갱신

   • 1시간/1일/1주 단위(비즈니스 요건에 따라)로 메모리에 있는 검색어 인기도 데이터를 **DB(예: RDB, NoSQL, Document DB)**에 저장(스냅샷).
   • 서버 재부팅이나 장애 발생 시, 이 DB에 저장된 스냅샷을 다시 로딩하여 인메모리 트라이를 재구성.

3. 장단점

   • 장점:
     • 조회(자동완성)는 메모리에서 초저지연으로 처리.
     • 인기도 변화가 즉시 반영.
     • DB는 주기적으로만 큰 트랜잭션을 수행하므로 부하가 적음.
   • 단점:
     • 메모리 트라이가 커질 수 있으며, 서버 장애 시 (snapshot 이전 변경분) 유실 위험 → 주기적 스냅샷 + 로그(재생) 기법 필요.
     • 동시성이 매우 높을 때, 트라이 노드 업데이트를 어떻게 락(lock) 없이 처리할지 고민이 필요.

2. 스트리밍(실시간) 데이터 파이프라인 + 부분(Incremental) 업데이트

1. 검색 로그 수집
   • 사용자가 검색어를 입력할 때마다(또는 특정 주기로), 로그(검색어, 타임스탬프, 사용자 식별 등)를 Kafka나 Kinesis 같은 스트리밍 플랫폼으로 보냄.
2. 실시간 랭킹 계산
   • Spark Streaming, Flink, 또는 Kafka Streams 같은 스트림 처리 엔진에서 “최근 5분/1시간” 등 윈도우(window) 단위로 검색어 빈도를 집계.
   • 이 결과를 인기 검색어로서 별도의 저장소(예: Redis, ElasticSearch, 인메모리 DB)에 저장.
3. Trie 부분 업데이트
   • 일정 간격(몇 초 ~ 몇 분마다)으로, 스트림에서 얻은 인기도 증가분만 트라이에 반영(“twitter” +15, “twitch” +10 등).
   • 이렇게 하면 “1~5분” 정도의 지연은 있을 수 있으나, 거의 실시간 수준으로 검색어 트렌드를 반영 가능.

이 방식의 핵심은, **배치를 하루 단위가 아니라 매우 짧은 마이크로 배치(초/분 단위)**로 바꿔서 인기 검색어 변화를 빠르게 적용한다는 점입니다.

3. “콜드(Cold) 인덱스 + 핫(Hot) 인덱스” 이중 구조

1. 콜드 인덱스(배치 생성)

   • DB나 파일 시스템(HDFS 등)에 저장된 대량의 검색어·인기도 정보를 바탕으로 주기적으로(1일~1주) 트라이 인덱스를 전면 재구축.
   • 비교적 변화가 적거나 “오랫동안 축적된 인기도 데이터”를 반영해 안정적이고 방대한 검색어 인덱스를 형성.

2. 핫 인덱스(실시간/근실시간)

   • 최근 N시간~N일간 급상승한 검색어를 소규모 인덱스(또는 인메모리 Trie)로 별도 관리.
   • 사용자 검색 시, **(콜드 인덱스 결과 + 핫 인덱스 결과)**를 합쳐 상위 K개를 계산(혹은 우선순위 조정).
   • 이 핫 인덱스는 계속 실시간(혹은 몇 분 단위)으로 업데이트되어 “검색 트렌드 급변”을 빠르게 반영.

3. 장점과 활용

   • 콜드 인덱스는 대규모 데이터를 안정적으로 커버, 자주 쓰이지 않는 오래된 검색어도 갖고 있음.
   • 핫 인덱스는 작은 규모라 업데이트가 잦아도 빠르게 처리 가능, 최신 트렌드를 즉시 반영.
   • 검색 시 두 인덱스를 병합하거나, 핫 인덱스를 우선 조회 후 부족하면 콜드 인덱스를 보강.
   • Elasticsearch 등에서도 “Hot-Warm” 아키텍처가 유사 개념.

4. 완전 실시간 트라이 업데이트 시 고려 사항

1. 트라이 업데이트 부하

   • 접두어 경로 길이 p만큼 모든 노드(최대 p개)에 대해 인기도 +1, Top-K 재정렬.
   • 트래픽이 폭주하는 경우, 락 충돌 또는 CPU 사용량 급등 가능 → 다단계 캐싱(위에서 말한 “핫 인덱스” 접근) 권장.

2. 동시성 처리

   • 여러 사용자 검색이 동시에 들어오는 경우, 한 노드를 업데이트할 때 thread-safe 보장이 필요.
   • Lock-free 자료구조나 fine-grained lock, atomic CAS 기법으로 동시성 처리.

3. 장애 복구

   • 실시간 업데이트 하다가 서버 다운되면 최신 인기도가 사라질 수 있음 → WAL(Write-Ahead Log), 카프카 로그 등 재생(Replay) 방안을 두어야 함.
   • 일정 주기로 스냅샷을 떠놓고, 재시작 시 스냅샷 + 로그로 복구.

결론적으로…

• 1일/1주 단위 배치만으로는 급변하는 검색어 트렌드를 놓칠 수 있으므로, 실시간 혹은 근실시간으로 인기도를 갱신하는 방식을 추가로 도입해야 합니다.
• 가장 간단한 형태는 **“인메모리 Trie”**를 애플리케이션 서버에서 직접 갱신(검색 시 +1)하고, 일정 주기로만 DB에 동기화하는 하이브리드 방식입니다.
• 더 확장된 형태로는, 스트리밍 플랫폼(Kafka 등) + 스트림 처리(Flink/Spark Streaming) + 실시간 부분 업데이트로 구성하는 아키텍처가 있습니다.
• 대규모 서비스에서는 종종 “콜드 인덱스(주기적 빌드) + 핫 인덱스(실시간 업데이트)” 이중 구조를 운용해 성능과 신선도 모두를 만족시키는 패턴이 일반적입니다.

---

트위터 같은 경우는 꽤 실시간 검색어를 반영하는 거 같은데 어떻게 하고 있나요 ?

정확한 내부 구현은 트위터(Twitter)에서 공개하지 않았기 때문에 세부 사항을 100% 알 수는 없지만, 알려진 자료와 일반적인 대규모 실시간 검색 시스템의 패턴을 종합해 보면, 트위터의 실시간 검색/트렌드(Trending Topics 등)는 크게 다음과 같은 구조로 동작한다고 알려져 있습니다.

1. 트윗 스트림(데이터) 수집과 실시간 처리

1. 데이터 인입(Streaming Ingestion)

   • 트위터에는 전 세계적으로 엄청난 양의 트윗이 초단위로 쏟아집니다.
   • 이 트윗들을 카프카(Kafka), Kinesis 혹은 트위터 자체 솔루션(과거엔 Storm, 지금은 Heron 등)으로 실시간 스트리밍 파이프라인에 넣어 집계할 수 있도록 합니다.

2. 실시간 집계(Real-time Aggregation)

   • 트위터는 특정 키워드(해시태그, 문구, 사용자 멘션 등)의 빈도나 발생 추이(증가 속도)를 스트림 처리 엔진으로 모니터링하고, 윈도우(예: 1분, 5분, 1시간 등) 단위로 집계합니다.
   • 여기서 Count-Min Sketch, HyperLogLog, Top-K 알고리즘 같은 스트리밍 알고리즘을 사용해, **실시간으로 트래픽이 폭증하는 키워드(급상승 검색어)**를 빠르게 포착할 수 있습니다.
   • 집계 결과는 인메모리 DB(Redis, 혹은 트위터 자체의 내부 캐시 시스템)나 NoSQL 스토어에 저장되며, 초 단위 혹은 수 초 내로 업데이트됩니다.

2. 검색 인덱스 및 자동완성(Autocomplete)

1. 실시간 인덱싱

   • 트윗 본문에 포함된 단어/해시태그 등을 검색 인덱스(예: Lucene 기반, ElasticSearch 유사 구조)로 Near Real-Time(NRT) 방식으로 계속 업데이트합니다.
   • 트위터는 규모가 방대하기 때문에 자체적으로 Earlybird 라는 검색 인덱싱 시스템(오래전 공개한 바 있음)을 운영했고, 구체적으로는 Lucene 기반 + 내부 커스텀 최적화를 적용한 것으로 알려져 있습니다.
   • 이런 인덱스는 수십 초~수 분 이내에 새 트윗을 검색 가능하게 해주어, “최신성”을 확보합니다.

2. 자동완성(Autocomplete) 및 실시간 트렌드 반영

   • 사용자가 검색창에 키워드를 입력할 때마다,
     • (1) 인덱스 기반으로 “해당 접두어로 시작하는 트윗/해시태그”를 검색, 상위 랭킹 항목만 즉시 보여주거나,
     • (2) 별도의 실시간 랭킹 캐시(예: 해시태그 빈도 상위 n개)에서 “입력한 접두어로 필터링”해 즉각 반환,
     • 혹은 (1)과 (2)를 조합해서 검색어 자동완성을 구성.
   • 특히, 많이 사용되는 해시태그나 키워드는 **별도의 캐시(Trie, 혹은 Sorted Set)**를 두어 빠르게 검색하는 구조가 흔히 사용됩니다.

3. 실시간 업데이트

   • 급상승 검색어나 해시태그가 감지되면(예: 어떤 해시태그가 1분 새 10배 폭증), 이를 바로 핫(Hot) 캐시에 올리고, 자동완성이나 트렌딩 탭에 노출합니다.
   • 이 과정에서 완전히 트라이(Trie)를 통째로 재빌드하는 것이 아니라, 가장 인기 있는 항목들만 빠르게 업데이트하여 노출 순서를 바꿉니다.

3. 핫(Hot) vs 콜드(Cold) 인덱스 구조

트위터처럼 방대한 양의 트윗 데이터를 다룰 때, “Hot-Warm-Cold” 구조를 사용하는 것이 일반적입니다:

1. Hot(실시간) 인덱스/캐시

   • 최신 24시간 이내 트윗, 혹은 막 올라온 트윗들의 검색 인덱스와 인기 키워드를 다룸.
   • 빠른 메모리 기반, 빈번한 업데이트, 초~분 단위로 계속 갱신.

2. Warm/Cold 인덱스

   • 24시간 이상 지난 트윗부터 역사적인 데이터(몇 년 전까지).
   • 상대적으로 업데이트 빈도는 낮지만, 검색 요청이 들어오면 빠르게 처리해야 하므로 SSD/HDD 기반 분산 검색 클러스터로 보관.
   • 전체 트윗의 대다수를 차지하며, 주기적으로 확장/압축/머징이 일어납니다.

검색 시, “Hot 인덱스 + Warm 인덱스”를 합쳐 결과를 준 뒤, 최신 트윗이나 급상승 해시태그는 Hot 인덱스 우선으로 검색하여 실시간성을 만족시키는 구조입니다.

4. 실제 트렌드 집계와 노출 로직

트위터의 **트렌드(Trending Topics)**는 단순 빈도순이 아니라, “과거 대비 증가율 + 지역 + 사용자 관계” 등을 종합해 산출한다고 알려져 있습니다.

• 예: 특정 주제(해시태그)가 전 시간대 대비 5배 급등했다면, 전 세계/국가/도시 별로 다른 후보들과 비교해 상위권에 오르게 됩니다.
• 트위터는 이를 분산 스트림 분석으로 계산한 뒤, 각 지역별 Top-K를 인메모리 캐시에 저장하고 일정 주기로 UI에 노출합니다.

또한, 광고나 정치적 이슈를 고려해 **노출 기준(quality filter)**이 가미될 수도 있는데, 이 역시 실시간으로 조정 가능하도록 구현되어 있습니다.

5. 요약

• 트위터는 “대규모 실시간 스트리밍” 파이프라인(Storm/Heron/Kafka Streams 등)을 통해 트윗을 수집, 해시태그·키워드 빈도를 실시간 집계하여 **급상승 검색어(트렌드)**를 빠르게 감지합니다.
• 검색 인덱스(자동완성)는 Near Real-Time으로 갱신되는 **고성능 분산 검색 시스템(예: Earlybird/Lucene 기반)**을 갖추고, 상위 키워드/해시태그는 인메모리 캐시나 트라이/Sorted Set 구조로 매우 빠른 응답을 제공합니다.
• 일반적으로는 “핫(Hot) + 콜드(Cold)” 인덱스를 나누어 최신성(실시간성)과 방대한 이력 데이터 모두를 커버하고, 필요하면 “핫 인덱스”만 수분 단위로 재빌드해 실시간 트렌드를 반영합니다.

결과적으로, 이런 스트리밍 분석 + 검색 인덱싱 + 캐싱(핫/콜드)” 조합 덕분에, 트위터는 초 단위로 폭증하는 해시태그나 키워드를 빠르게 포착해 검색 자동완성과 트렌딩에 반영할 수 있는 것입니다.

[cruellaDev]

같은 단어인데도 공백을 포함한 입력과 공백을 포함하지 않고 그대로 입력한 경우 같은 단어의 빈도수를 높여야 하는데 이런 경우엔 어떻게 해야 하는가?
예) ice cream vs icecream

[cruellaDev]

검색어 정규화라는 작업을 통해 해결해야 한다는데,,,
보통 검색 자동완성에서는 **방법 2(모든 공백 제거)**를 많이 사용한다고 한다.

[renechoi]

...

[renechoi]

공백도 하나의 문자로 보면 될듯 ㅋ

[KimH4nKyul]

ice cream