[Review] 시스템 디자인 스터디 6주차 후기

안녕하세요!

K-DEVCON (이하 “데브콘”) 그로스 매니저 박종훈입니다.

 

이 글에서는 10/23 (목)에 진행된 스터디에서 나눈 이야기를 정리합니다.

 

이번 시간에는 “검색어 자동완성 시스템 설계”에 대한 이야기를 나눴습니다.

 

---

 

검색은 일상생활에서 많이 사용하는 서비스입니다. 하지만 그 기술을 깊게 다룰 기회는 많지 않습니다. 오늘 스터디에서는 단순 설계에서 더 나아가 실제로 사용되고 있는 기술들을 좀 더 깊게 다뤄보고 싶었지만, 알아야 하는 배경지식이 많아 쉽지만은 않았습니다. 그래서 최대한 이 글을 작성해보며 내용을 정리하고 넘어가고자 합니다.

 

[1] 기본적인 시스템 설계

일반적으로 시스템 디자인 설계 면접관련 자료들에서는 검색어 자동완성을 설계 할 때 트라이(Trie) 자료구조 사용하여 설계를 진행합니다.

 

트라이 자료구조는 접두어 트리(Prefix Tree) 라고도 불리며, 문자열을 효율적으로 저장/검색 할 수 있는 자료구조 입니다. 

이 자료구조를 이용하여 다음과 같은 시스템을 만들어 볼 수 있습니다.

 

출처: 가상 면접 사례로 배우는 대규모 시스템 설계 기초

 

조금 더 발전시킨다면, 검색 횟수나 내부 우선순위에 따른 가중치 트라이를 만들수도 있을 것입니다.

 

출처: 시스템 설계 면접 완벽 가이드

 

하지만 실제 서비스를 구현한다면 트라이 구조를 직접적으로 구현해서 사용하지는 않을 것 같고, 이미 기능이 구현되어 있는 ElasticSearch를 사용하는 경우가 많을 것 같습니다.

그래서 ElasticSearch의 기초가 되는 Lucene의 구조에 대해서도 간단하게 이야기를 나눠보았습니다.

 

[2] 기초지식

다음 이야기할 내용들을 이해할 수 있도록 기초 지식을 정리해보면 다음과 같습니다.

<1> Directed graph, DAG

유향 그래프(Directed Graph) 는 정점(vertex)과 방향성이 있는 간선(edge)으로 이루어진 구조로, 각 간선은 한 정점에서 다른 정점으로 향하는 방향을 가집니다.

DAG(Directed Acyclic Graph) 는 사이클(cycle)이 존재하지 않는 유향 그래프로, 어떤 정점에서도 자기 자신으로 돌아오는 경로가 없습니다.

<2> Transition system (전이 시스템)

전이 시스템은 시스템의 가능한 상태(state)들과, 한 상태에서 다른 상태로 이동할 수 있는 전이(transition) 들로 구성된 수학적 모델입니다. 프로그램 실행, 프로세스 동작, 논리적 추론 과정 등을 기술하는 데 사용됩니다.

<3> State machine (상태 기계)

상태 기계(State Machine) 는 시스템이 가질 수 있는 여러 상태와, 입력이나 조건에 따라 한 상태에서 다른 상태로 전이하는 동작을 정의한 모델입니다. 시스템의 동작을 상태 변화의 흐름으로 표현함으로써, 복잡한 제어 구조를 단순하고 명확하게 기술할 수 있습니다.

<4> FSM (finite-state machine, 유한 상태 기계)

유한 상태 기계(FSM) 는 상태의 수가 유한한 상태 기계입니다. machine 이라는 표현 대신 automaton 이라는 표현을 쓰기도 합니다.

<5> FST (finite-state transducer, 유한 상태 변환기)

유한 상태 변환기(FST) 는 FSM의 확장 형태로, 입력에 대응하는 출력을 함께 생성하는 모델입니다.

 

[3] Lucene 설계 사례

Apache Lucene 은 고성능 오픈소스 검색엔진입니다.

 

Lucene 은 빠른 검색을 위해 FST 를 사용합니다.

FST는 Trie 기반 구조를 압축하고 상태 전이를 공유함으로써, 대규모 단어 사전을 효율적으로 표현합니다.

 

이미지 출처: Text Tagging with Finite State Transducers

 

위 이미지의 map, moth, pop, slop, sloth, stop, top 이라는 단어로 FST를 구성하였을 때의 예시 모습입니다.

 

Trie와 비슷하지만, prefix를 공유한다는 점에서 차이가 있습니다.

 

FST로 블록 위치를 빠르게 찾은 뒤, 해당 블록에서 term과 관련된 메타데이터를 읽어옵니다.

 

[4] Fuzzy Search

Fuzzy Search 는 검색어에 오타, 철자 오류 또는 약간의 변형이 포함되어 있더라도 정확한 문자열이 아닌 유사한 문자열을 찾아 검색어와 일치하는 항목을 찾는 기술입니다. Levenshtein distance 를 기반으로 합니다. 

 

Levenshtein distance 은 단순합니다. 두 문자열 간의 차이를 측정하는 지표입니다.

다음과 같은 기준으로 측정됩니다.

 

출처: Levenshtein distance - wiki

 

말로 풀어서 정리해본다면 다음과 같이 설명해볼 수 있습니다.

 

1. |b| = 0인 경우 (b가 빈 문자열)

결과는 |a| (a의 길이)

 

2. |a| = 0인 경우 (a가 빈 문자열)

결과는 |b| (b의 길이)

 

3. head(a) = head(b)인 경우 (첫 문자가 같음)

결과는 lev(tail(a), tail(b))

의미: 첫 문자는 같으므로 비용 없이 나머지 부분만 비교

 

4. 그 외의 경우 (첫 문자가 다름)

다음 세 가지 연산 중 최소값을 선택하고 1을 더함:

• lev(tail(a), b): a의 첫 문자 삭제
• lev(a, tail(b)): b의 첫 문자 삽입
• lev(tail(a), tail(b)): a의 첫 문자를 b의 첫 문자로 치환

 

예를들어 “kitten” 과 “sitting” 의 거리는 3 입니다.

• kitten → sitten (substitution of "s" for "k"),
• sitten → sittin (substitution of "i" for "e"),
• sittin → sitting (insertion of "g" at the end).

 

또 다른 예를 들어보면 "uninformed" 과 "uniformed" 의 거리는 1 입니다.

• uninformed → uniformed (deletion of "n").

 

그럼 여기서 생각이 드는 것은 ‘그러면 사용자가 입력을 할 때, 단어 사전에 등록된 모든 단어와 레벤슈타인 거리를 측정해야 할까?’ 에 대한 부분이였습니다.

 

이에 대한 답을 찾기 위해 Fast approximate search in large dictionaries(Stoyan Mihov, Klaus U. Schulz) 논문의 내용을 조금 읽어보았습니다.

먼저 사용자는 몇 개의 오차까지 고려할지에 대한 k 값을 설정합니다.
(실제 lucene 에서는 k 의 값을 2 까지로 제한합니다. 2보다 클 경우 성능에 영향을 크게 미치기 때문이라고 합니다.)

그러면 사용자의 입력값과 K 값에 따라 비결정적 오토마타(Nondeterministic automaton) 이 생성됩니다.

아래 이미지는 k가 2일 때 chold 라는 입력값에 따라 생성될 수 있는 오토마타를 나타낸 것입니다. 이 상태에서 t 와 h 라는 값을 입력하였을 때 오토마타를 통해 거쳐가는 상태들이 회색 영역으로 나타내졌습니다.

 

출처: Fast approximate search in large dictionaries(Stoyan Mihov, Klaus U. Schulz)

 

각 화살표는 다음을 의미합니다

• 수평 화살표 (→) : 패턴의 다음 문자가 정확히 일치
• 대각선 화살표 (↗) : 치환 또는 삭제를 의미
• 수직 화살표 (↑) : 삽입(insertion) 을 의미

각 상태에 적혀있는 숫자는 (현재 위치)^(사용한 오류 횟수)를 의미합니다. (지수는 승을 의미하는게 아님에 주의.)

 

첫 시작은 0^0 에서 시작합니다.
t 가 입력되면, 갈 수 있는 상태는  { 0^1, 1^1 } 이 됩니다.
그 다음 h 가 입력되면, 갈 수 있는 상태는 { 0^2, 1^2, 2^1, 2^2 } 가 됩니다.
만약 2^1 로 갔을 경우, 아직 남아있는 오류 횟수 1회가 남아 있으므로 { 3^2 } 까지도 도달할 수 있습니다.

 

Lucene에서는 이 Levenstein automaton 과 단어사전(FST)를 함께 탐색해 나갑니다. 이를 통해 탐색 공간을 빠르게 줄입니다.

FST에서 허용되지 않는 경로일 경우 시작 단계에서 탐색을 중단합니다.

 

---

 

오늘은 위와같은 이야기를 함께 나누어보았습니다.

 

평소에 깊게 생각해보지 않았던 검색 도메인에 대해 고민해 볼 수 있었어서 좋았습니다.

우리 스터디에서는 이러한 문제들을 실제 사례에서 어떻게 해결해 나갔을까 많은 고민을 해보고 이야기를 나눠보고 있습니다. 이번주도 다들 열심히 참여해주셔서 더 풍성한 스터디가 될 수 있었습니다.

 

 

스터디에서 더 많은 이야기를 나눴지만, 오늘은 여기서 마쳐보겠습니다.

 

✅ 직접 스터디를 개설해보고 싶은 분이 계시다면, K-DEVCON에서 운영을  도와드리겠습니다. 데브콘의 '랩짱'에 도전하여 커뮤니티 성장을 함께 이끌어주세요! 슬랙을 통해 운영진에게 DM 부탁드리겠습니다😉