[NAVER DEVIEW 2020] C++로 다시 쓴 ES, Ultimate Search - 컨퍼런스 내용 정리

본 게시글은 NAVER DEVIEW 2020 [C++로 다시 쓴 ES, Ultimate Search]을 보고 정리하였습니다.

 

1. Motivation

1.1 빅데이터, 그리고 GC

 - 5G : 유래 없는 속도, 초연결 시대
 - 프로세서의 진화 : NPU, GPU 그리고 점점 GPU로 변하는 CPU
 - GC : 대규모 프로세싱의 병목
 - 클라우드 : 모든 계산은 저 구름 너머에.

곧 도래할 5G 시대에 폭발적으로 증가할 데이터량과 같이 하드웨어도 진화를 하고 있다.
모든 계산이 클라우드에서 처리될 것이다.
이러한 데이터의 증가와 하드웨어의 진화를 엔진이 충분히 따라가지 못하고 있다.

1.2 더 빨라질 수 있다.

하드웨어 친화적 알고리즘 그리고 GC만 없다면 더 빨라질 수 있다.

 - GPU, NPU : 문제를 풀기 위한 하드웨어의 진화
 - 결국 성능은 소프트웨어 + 하드웨어
 - 빨라지는 RAM, DDR5 : 점점 커지는 메모리, 500G 그 너머로

진화하고 있는 하드웨어를 사용해서 폭발적인 양의 데이터를 잘 활용할 수 있지 않을까?

1.3 AI, AI, AI

모든 것이 검색 대상 : Voice, Visual(image), Video 등 미디어뿐만 아니라 감정, 상황 등 그야말로 모든 것

빠른 계산으로 AI가 눈부시게 발전을 하고 있다. AI 트렌드를 검색엔진 측면에서 바라보면, 전통적인 텍스트 검색에서 이제는 무엇이든 검색할 수 있는 시대가 왔다.

 

2. Ultimate 프로젝트

새롭게 바뀌고 있는 검색 페러다임을 위한 검색 엔진을 만드는 프로젝트

어떻게 GC없는 검색을 할 수 있을까?
어떻게 하드웨어를 잘 활용할 수 있을까?
어떻게 검색 대상을 확대 할 수 있을까?

2.1 GC없는 더 빠른 검색

엔진 전체를 C++로 재작성

 - Ultimate Lucene : 색인, 검색 핵심 로직을 C++로 재작성
 - SIMD : CPU의 SIMD 명령어 셋으로 프로세싱
 - Ultimate Search : 클러스터링, 그리고 THE WORLD NAVER STOPS

2.2 비정형 검색

모든 것은 벡터로 통한다.

 - Vector space model : 어떻게 벡터를 연관시킬 것 인가?
 - Hierarchical Navigable Small World : 벡터를 색인하고 검색하다.

AI 트렌드를 봤을 때 엔진의 위치는 뒤쪽이 될 것이다. 
어떤 것으로 부터 피쳐 벡터(feature vector)를 뽑고 모델에 태우면 벡터로 결과가 나오게 된다.
그렇기 때문에 모든 것은 벡터로 통하고 있으며 벡터 검색을 하고 벡터 색인을 할 수 있어야 한다.
또한 벡터 계산을 더 잘할 수 있도록 하드웨어가 발전하고 있다.

2.3 왜 ES를 재작성했는가?

ES는 검증된 엔진이며 동시에 많은 개발자에게 사랑받는 엔진이다.

 - 정말로 편하다
 - 확정성있는 플러그인 구조
 - 독립적인 아키텍처, 별도 의존 인프라 필요 없음
 - 우아한 코드 구조, 꼼꼼한 코딩 스타일
 - Scalable 클러스터. Raft consensus

이러한 장점은 그대로 계승하되 한 차원 더 승화시키는 것이 목표
그래서 ES를 C++로 재작성하면서 벡터 검색을 추가

 

3. Ultimate Lucene - C++로 다시 쓴 Lucene

3.1 Ultimate Lucene

엔진의 심장. 색인과 검색을 책임진다.

               검색, 색인 요청        루씬 위임                 검색, 색인 수행
클라이언트 -----------------> ES ------------> Lucene <-------------------> 루씬 세그먼트
               

ES가 거시적(쿼리를 받거나, 클러스터링을 하거나 등)인 측면을 책임진다면
Lucene은 미시적인 측면을 책임진다.

검색, 색인 로직 전체를 C++로 재작성

 - 검색 비용의 대다수를 차지한다.
 - CPU를 100% 활용하여 검색 로직 수행. SIMD
 - GC 없음, 평균 2배 성능 or More?
 - 벡터 검색 가능, 비정형 검색으로의 대상 확장

성능 크리티컬 한 부분은 어셈블리로 작성 
기반 위에 벡터 검색 기능을 확장

3.2 핵심은 CPU 활용

포스팅 리스트. 모든 것이 시작되는 출발점

 - 20배 빠르다. L1 캐시는. Menory보다.
 - 캐시 + SIMD 프로세싱
 - Encoding + Decoding

C++로 재작성한다 해서 성능이 드라마틱하게 좋아지지 않고 오히려 안 좋아지는 경우가 태반이었다.
검색엔진이라는 것은 역 색인, 전화번호부 같은 것이라 볼 수 있다.
예를 들면 사과 -----> 1 -----> 3 -----> 17        와 같이 구성되어 있다.
                   <------ 포스팅 리스트 ------>

성능을 향상 시키려면 포스팅 리스트를 처리할 때 CPU를 잘 활용을 해야 한다.
L1 캐시 접근 속도가 메모리 접근 속도보다 20배가 빠르다. 때문에 검색 로직을 C++로 작성을 했을 때 L1 캐시를 잘 활용해야 하며, 뿐만 아니라 CPU 명령어도 잘 활용해야 한다. 
그것이 SIMD이다.

SIMD는 여러 가지 데이터를 한번에 처리할 수 있는 CPU 명령어이다.
예를 들어 여러가지 데이터를 한꺼번에 더하거나 비교할 수 있다.

3.3 Documenet At A Time

포스팅 리스트를 처리하는 알고리즘은 업그레이드돼야 한다.

프로세싱 메커니즘의 확대 : 한 번에 여러개씩 비교

두 리스트의 요소를 각각 순회하며 비교해 매치하는 방식(Scalar)에서 모든 요소를 한번에 비교해 매치하는 방식(Vector)으로 업그레이드
이 방식의 장점은 CPU Branch Miss가 나지 않으며 한꺼번에 비교하는 방식이기 때문에 성능 측면에서 장점이 있다.

결과적으로 검색엔진의 성능을 높이고 싶으면 캐시와 SIMD 프로세싱을 잘 검색 로직에 녹아내서
Encoding, Decoding, 포스팅 리스트 처리 등을 모두 C++로 효율적으로 구현해야 한다.

 

4. ES + Lucene의 큰 그림 - 검색과 집계를 동시에

4.1 집계와 검색 : 포스팅 리스트

포스팅 리스트 + 프로세싱 = 대상 문서들 ID 확보 - 결국 Set operation

질의 = { t1 = 네이버, t2 = 궁극, t3 = 검색엔진 }

P1 ⋂ (P2 ⋃ P3) ⋂ (P4 ⋃ P5) ⋂ P6
where P1, P2, P3 모두 텀 매칭 포스팅 리스트
그 외 P4, P5, P6 은 확장된 포스팅 리스트

4.2 집계와 검색 : Doc value

Column oriented format + 집계 프로세싱
- Pluggable 집계 알고리즘

루씬이 연산을 통해 문서 ID를 확보하면 그때부터 집계와 검색의 로직을 수행한다.
문서 ID가 Key 역할을 하기 때문에 얻은 ID에 해당하는 랭킹 Feature 데이터를 가져와 처리를 하거나 메트릭 데이터를 가져와 집계를 하는 작업을 수행할 수 있다.
그리고 이 지점이 Lucene과 ES가 만나는 지점이다.

거기에다가 Lucene은 Doc value 포맷을 지원하는데 그 유명한 Column oriented 방식이다.
Doc value 필드들의 값을 한데 뭉쳐서 파일로 저장하는 방식이다.

카산드라나 아파치 쿠두도 똑같은 Column oriented 방식은
Row oriented 방식과 비교했을 때 접근 비용이 저렴하고 캐시 효율이 좋은 장점이 있다. 

4.3 Raft와 Primary backup model

Raft, ES 클러스터링의 백본

검색 로직 이후에 ES(거시적) 측면에서 더 중요한 것은 가용성이다. 그래서 ES는 Raft 알고리즘을 사용하고 있다.
여러 노드를 사용하여 검색도 하고 색인을 하는데 노드가 실패를 하고 다시 복구를 해도 가용성을 유지해야 한다.
그것을 분산 코디네이션이라고 한다. 그리고 이를 위한 알고리즘이 Raft이다.

Raft 알고리즘이 책임을 지는 것은 전체 클러스터가 하나의 값을 볼 수 있도록 보장을 해준다. 그 과정에서 노드가 죽었다 살아나도 최신의 갱신된 값을 볼 수 있게 해주는 것이 Raft 알고리즘이다. 

Raft위에 올려진 데이터 분산, 리커버리

Raft로 클러스터링을 해놓으면 그 기반 위에 올라가는 것이 데이터 복제 모델(Primary backup model)이다. 데이터 복제 모델은 데이터를 받아서 Replica에 잘 도달했는지 아니면 좀 레그 된 노드가 있다면 태워주는 역할을 한다.

기본적인 아이디어는 In-sync set 테이블을 관리하고 있어서 어떤 복제 군이 어디까지 싱크가 되었는지 트래킹을 하고 있다.

여기서 가장 중요한 포인트는 분산 코디네이션을 하는 것은 Raft를 사용을 하고 그 기반 위에서 데이터를 관리를 Primary backup model로 사용을 한다. 즉, 계층화돼서 두 가지 분산 알고리즘을 사용해서 구현이 되어있다.

부정확할 수 있지만 카프카와 작동 방식이 비슷할 것 같다.

4.4 전체 뷰, Ultimate Search

UTSrch는 포르쉐, UTLC는 터보 엔진

C++로 다시쓰는 ES 자료 내 이미지

Ultimate Search는 거시적으로 보면 Raft, Primary backup model로 데이터를 안전하게 복제를 하고 미시적으로 본다면 Ultimate Lucene이 검색과 색인을 수행하고 있다.

 

5. 벡터 검색

백터를 검색할 수 있다면 모든 것을 검색할 수 있다.

5.1 벡터 검색

어떤 것이든 공간에 사상시킨다.

- 딥러닝의 발달, AI의 일상화
 - 핵심 질문 : 어떻게 질의 벡터와 유사한 것을 찾을 수 있을까?

엔진 측면에서 벡터 검색이라는 것의 의미를 고려해 보면 질의를 받아서 질의와 유사한 것을 어떻게 빠르게 찾아줄 수 있는지 고민해야 한다.
예를 들어 토마토라는 질의를 받으면 토마토와 유사한 사과나 바나나를 빠르게 찾아서 리턴해 줄 수 있는지 고민을 해야 한다. 이것이 바로 Nearest neighbor search이다.

5.2 Nearest neighbor search

97% 정확도로 빠른 성능을!
검색 공간을 빠르게 줄여 나가는 것이 핵심

 - Local sensitive hashing
 - Annoy, 공간 forest
 - HNSW : 멀티 레이어 공간 그래프 (선택)

질의를 결국 벡터로 받아서 유사한 것들을 빠르게 계산해서 그 이웃들을 리턴하는 것이 Nearest neighbor search라고 볼 수 있다.
벡터가 차원이 굉장히 높은 벡터는 Nearest neighbor search를  정확하게 하면서 동시에 빠르게 하는 것은 현실적으로 어렵다. 그래서 여러 가지 방법이 있는데 여러가지 방법은 결국 근사치로 빠르게 계산하는 방식을 사용한다.
여러 방식들을 관통하는 것이 있다면 결국 검색 스페이스를 어떻게 줄여나갈지가 가장 중요하다. 그래서 벡터 색인을 만들어서 검색 스페이스를 step by step으로 확 확 줄여나가는 것이 관건이다.

5.2.1 Local sensitive hashing, LSH

유사한 벡터들의 해시값은 대체로 같도록 하자

C++로 다시쓰는 ES 자료 내 LSH 설명 이미지

보통은 해시 테이블을 설계할 때 최대한 해시값이 어긋나도록 설계를 하는데 LSH는 이것과 살짝 반대이다.
유사한 원소들이 있다면 해시값이 일정 확률로 같도록 설계를 한다. 그러면 가까운 원소들은 확률적으로 같은 버킷에 있을 확률이 높다.

이런 원리를 Nearest neighbor search에 어떻게 적용했냐면
질의 벡터를 받아서 해시 펑션을 태우면 버킷이 결정이 되는데 그 버킷에 있는 원소들이 질의 벡터의 이웃이 된다. 그 후 2차적으로 계산을 하여 반환한다. 확률적으로 동작하기 때문에 근사적으로 동작을 하고 놓치는 것도 있을 수 있다.

5.2.2 공간 forest, Annoy

랜덤 분할한 공간 트리가 N개 = 공간 Forest

C++로 다시쓰는 ES 자료 내 Annoy tree 설명 이미지1

 Annoy는 트리를 사용하여 공간을 랜덤으로 계속해서 나눠줍니다. 이때 아주 가까운 두 개의 벡터 중간으로 공간이 나눠지면서 다른 플레인에 속할 수 있다. 직선으로 공간을 나누다 보니깐 발생하는 문제이다. 직선으로 나누는 방식에 대한 한계라고 판단하여 트리를 여러 개 만들어서 해결했고 그것을 Forest라고 한다..

C++로 다시쓰는 ES 자료 내 Annoy tree 설명 이미지1

 질의 벡터가 들어왔을 때 Forest를 순회하여 질의 벡터와 유사한 벡터를 반환한다.

5.2.2 HNSW

멀티 레이어 그래프 + 여러 휴리스틱

 - 확률 자료구조 : Layer level
 - 검색 휴리스틱
 - 매우 빠르다 : 빠르게 목적지에 도달한다.
 - 병렬 색인 구조

Annoy랑 비슷하게 그래프를 여러 개 사용한다. 하지만 계층구조로 이루어져 있으며 계층이 깊어질수록 조밀하다. 기본적인 아이디어는 그래프에서 그리디 검색을 하는 것이다. 이때 어디서 시작하는지가 중요하다. 검색은 상위 계층부터 시작하며 하위 레이어로 내려올수록 정보가 많아진다. 예를 들어 주소를 찾을 때 나라를 선택하고 그다음 시, 구, 동을 선택하는 것과 같다. 가장 하위(Layer = 0)까지 내려오면 그리디 검색을 시작한다. 상위부터 하위 레이어까지 내려오는 과정에서 그리디 시작점이 가깝게 조정이 되어있어 검색이 빠르다. 이 뿐만 아니라 계층 높이나 휴리스틱을 커스텀할 수 있다.

5.3 UTLC와의 통합

HNSW를 UTLC Codec에 추가

 - Sub milliseconds 검색 성능. 빠르다(600 차원, 300만건, Consine similarity)
 - 루씬 증분 병합 구조의 문제 : GPU가 답인가?
 - 목표 : CPU + GPU 하이브리드 모델

 HNSW가 검색 속도가 굉장히 빠르지만, 멀티 레이어 그래프를 빌딩 하는 것이 굉장히 어렵다. 멀티코어나 GPU를 사용해야 한다. 하지만 루씬의 구조적인 한계가 있다. 루씬은 세그먼트를 빌딩 할 때 싱글코어로 돌린다. 거기에다가 여러 가지 세그먼트를 병합하면서 키워가는 구조인데 병합한 세그먼트를 만드는 것도 싱글코어이다. 결과적으로 멀티 레이어 그래프를 싱글코어로만 만들게 된다. 그래서 속도가 느리다. 

 이 문제를 루씬의 구조적인 문제로 보고 있고 이것을 어떻게 하면 잘 해결할 수 있을지 고민하고 있다. 궁극적인 목표는 구조적인 문제를 잘 해결하는 것, 아키텍처를 바꾸고 CPU + GPU 하이브리드 모델로 해결할 수 있지 않을까 연구를 하고 있다.

 하이브리드 모델이 도입하고 아키텍처를 바꾸면 포스팅 리스트 계산이나 벡터 계산 등 다양한 곳에서 수혜를 볼 수 있지 않을까 생각하고 있다.

5.4 벡터 검색엔진

벡터를 색인하고 벡터를 검색한다.

C++로 다시쓰는 ES 자료 내 벡터 검색엔진 설명 이미지

 Ultimate Search가 단순히 ES를 C++로 포팅했다가 아닌 ES의 기능과 구조를 그대로 계승하면서 한층 더 확장을 한 검색 엔진이라고 볼 수 있다.

6. 검벡집, 삼위일체

텍스트 검색 + 벡터 검색 + 집계

6.1 삼위일체, Ultimate Search

텍스트 검색 & 집계

 - 풍부한 Query
 - No GC, 빠른 성능
 - 다양한 Analyzer와 Similarity는 과제

벡터 검색 : 벡터를 던져요 벡터를 줄게요

 - 모델러는 좋은 벡터 생성 모델에 집중
 - 낮은 허들, ES와 동일한 메커니즘
 - 다양한 플러그인은 과제

 텍스트 검색과 집계 쪽은 Ultimate Lucene으로 포팅을 해서 C++로 구현되어 있고, 하드웨어 잘 사용하고 있고, GC가 없고, 빠르고, 이런 것들은 이미 어느 정도 테스트가 된 것 같다. 아무래도 엔진이 신생아다 보니깐 애널라이져라던가 시뮬레 같은 이쪽 부분은 시간을 두고 태워야 되는 부분 같다.

 그리고 그 기반 위에 벡터 검색을 올렸다. 그래서 ES의 뛰어난 사용성, 기능을 그대로 가져오되 벡터 검색을 수행할 수 있다. 모델러분들은 좋은 모델 생성의 집중하고 벡터 검색은 Ultimate Search가 위임하는 형식으로 아키텍처를 짠다면 AI검색 아키텍쳐 구조가 훨씬 더 간결해지지 않을까? 이렇게 기대를 하고 있다.

하지만 앞서 말한 구조적인 문제라던가 플러그인 등 환경 포인트 같은 경우는 시간을 두고 해결해야 하는 문제인 것 같다.

마무리를 지어보면 전통적인 텍스트 검색에 있어서 집계가 훨씬 빠르고 GC가 없어서 운영이 편하다. 그리고 여기에 딥러닝 모델을 거친 벡터가 색인되고 검색이 된다.

 

7. 성능평가

성능 분석은 아직까지 진행 중이고 성능 평가라는 것이 고려를 해야 할 것이 많아 일반화하기 어렵다. 보수적으로 2개 평가만 공유드립니다.

7.1 Conjunction 평가

리얼 데이터 2,000만건, 메모리 128G, 32 Cores : Query = T1 and T2 and ... and Tn

C++로 다시쓰는 ES 자료 내 Conjunction 평가 그래프

7.2 Disjunction 평가

리얼데이터 2,000만건, 메모리 128G, 32 Cores : Query = T1 and T2 and ... and Tn

C++로 다시쓰는 ES 자료 내 Disjunction 평가 그래프

 

 좀 더 엄밀하게 분석이 필요하여 내년쯤 성능을 분석하여 공유가 가능할 것으로 보인다.

 

8. 로드맵

안정성과 채널(?)을 고민하고 있다.

8.1 테스트 테스트 테스트

어떻게 테스트를 해야 할까?
어떻게 메모리 Leak을 점검할까?
어떻게 프로파일링 할 수 있을까?
어떻게 연속성 있게 버전업을 할 수 있을까?
어떻게 통합 테스트를 해야 할까?
 ...

 어떻게 테스트를 잘할 수 있을까 고민을 하고 있다. 개발하는 것만큼 어려운 주제 같다. C++이라는 것이 테스트가 많이 필요한 언어이다 보니깐 매일매일 치열하게 어떻게 테스트를 해야 할지 고민하고 있다.

8.2 플러그인

 

 

 여러 가지 플러그인들, 여러가지 생태계가 있어야 할 것 같은데 그러기 위해서는 문서도 잘 작성이 되어있어야 하고 채널 선택 포인트, 협업 등 고민을 하고 있고 이것도 굉장히 쉽지는 않은 문제인 것 같다.

 하지만 아직까지는 안정성 위주로 보고 있다.

세상은 더 이상 멈추지 않는다 GC 없는 더 빠른 검색
이제, 무엇이든 검색할 것이다. 벡터 검색