Elasticsearch

Internal

Deep-Dive

Index

0. Elasticsearch ?

1. 검색엔진?

2. Clustering, Serving

3. Elasticsearch 코드들여다보기

4. 직접 구현해보겠습니다.

Elasticsearch ?

Elasticsearch

Elasticsearch

• 오픈소스 분산 검색엔진
• 일종의 NoSQL (CAP 중 CP)
• LADM 포함 수많은 성공 사례들

Elasticsearch - use case 1

Elasticsearch - use case 2

Elasticsearch

HTTP

- 인덱스 생성

- 데이터 인덱싱

- 검색요청

요청 처리 결과

Elasticsearch

Elasticsearch

차근차근 알아가봅시다.

검색엔진?

검색엔진

검색엔진

단어

문서를 저장해놓고

특정 키워드를 포함하는

문서를 찾는 문제.

Document Storage

검색엔진

Q. LIKE ‘%%’ 하곤 다릅니까?

검색엔진

LIKE는 단순 TEXT 비교

검색엔진

Q. MySQL Fulltext index?

검색엔진

가장 간단히 구현할 수 있는 검색 (Text Matching)

​

Before 5.6: MeCab 기준 index

After 5.7: + n-gram

검색엔진

MeCab 기준 parse:

MeCab 이라는 tokenizer의 형태소 사전 및 공백 기반으로 문장을 쪼갠다.

Ex) “データベース管理” (“Database Management”) -> �“データベース” (“Database”), “管理” (“Management”)

​

n-gram parse:

ngram_token_size 설정값 기반으로 문장을 쪼갠다.

Ex) abcd ->

n=1: 'a', 'b', 'c', 'd'�n=2: 'ab', 'bc', 'cd'�n=3: 'abc', 'bcd'�n=4: 'abcd'

검색엔진

검색엔진

정제

Tokenizing

색인

Indexing

검색

Querying

서빙

Serving

검색엔진 – Token Analyzer

Token 생성기

​

• Mecab
• n-gram
• Standard tokenizer
• 은전한닢
• Nori plugin
• Kakao khaiii
• 그 외 여러 analyzer

“データベース管理” (“Database Management”) -> �“データベース” (“Database”), “管理” (“Management”)

abcd ->

n=1: 'a', 'b', 'c', 'd'�n=2: 'ab', 'bc', 'cd'�n=3: 'abc', 'bcd'�n=4: 'abcd'

Token을 기반으로 인덱싱

(Inverted index)

검색엔진 – Inverted Index

MySQL등 일반적 RDB의 경우

테이블에 저장

검색엔진 – Inverted Index

Lucene Analyzer 같은 indexer는 직접

디스크에 저장

• Log Structured Merge Tree (data structure)
• RoaringBitmap (compress)

검색할 Token에 해당하는

Document 리스트를 뽑아온다.

검색엔진 – Query

그런데, 어느게 가장 내가 찾고 싶은 정보인가?

검색엔진 – Query

Rank Algorithm

​

Ex) TF-IDF

​

전제:

관사(a, the)의 경우 여러 문장에 많이 등장한다.

몇몇 단어는 특정 문서에만 존재할 것이다.

​

-> 여러 문서에서 자주 등장하면 중요도가 낮고,

특정 문서에만 자주 등장할 경우 중요도가 높다.

검색엔진 – Query

TF-IDF

​

TF: Term Frequency, 단어 빈도

DF: Document Frequency, 문서 빈도

IDF: DF의 역수 (log)

​

Rank-score: TF * IDF

검색엔진 – Query

검색엔진 – Query

검색엔진 – Query

랭킹 알고리즘

​

• TF-IDF (Elasticsearch Before 5.0)
• BM25 (Elasticsearch After 5.0)
• Multi Similarity

검색엔진

MeCab 기준 parse:

MeCab 이라는 tokenizer의 형태소 사전 및 공백 기반으로 문장을 쪼갠다.

Ex) “データベース管理” (“Database Management”) -> �“データベース” (“Database”), “管理” (“Management”)

​

n-gram parse:

ngram_token_size 설정값 기반으로 문장을 쪼갠다.

Ex) abcd ->

n=1: 'a', 'b', 'c', 'd'�n=2: 'ab', 'bc', 'cd'�n=3: 'abc', 'bcd'�n=4: 'abcd'

Elasticsearch - Clustering, Serving

검색엔진

정제

Tokenizing

색인

Indexing

검색

Querying

검색엔진

서빙

Serving

검색엔진

Q. 서빙 그거 그냥

http api 로 제공하는 거 뿐인거 아닙니까?

​

A. 단일 노드로만 보면 그렇습니다만,,

검색엔진 – Clustering, Serving

HA를 위한 Scalable

​

Elasticsearch – NoSQL, Stateful Cluster

​

어떤 데이터를 어느 노드가 저장할지

“합의” 해야한다.

​

• 클러스터를 어떻게 형성할까
• 데이터를 어떻게 분산해 저장할까

분산시스템

Fully-connected mesh network 

�

분산시스템

분산시스템

With Zookeeper

Without Zookeeper

Pros

• 구현이 편하다
• 각 노드 입장에선 zookeeper 서버 ip만 알면 된다.

​

Cons

• Zookeeper 노드를 별도로 관리해야한다.
• Zookeeper가 SPoF가 될 수 있다.�

Pros

• Zookeeper등 다른 리소스를 관리할 필요가 없다.

​

​

Cons

• 구현이 조금 복잡하다.�

분산시스템

분산시스템

• elasticsearch.yml

분산시스템

분산시스템

분산시스템

분산시스템

https://raft.github.io/raftscope/index.html

분산시스템

왜 RAFT 인가?

​

그냥 첫 시작한 노드를 Leader로 삼으면 되지 않겠느냐?

분산시스템

Split Brain Problem

분산시스템

왜 RAFT 인가.

​

네트워크가 단절되었을때

Leader가 여러개가 되는 것을 막아야한다.

​

(Quorum based : Voting 시 과반수 이상의 표를 받아야 Leader가 될 수 있음

=>

Master-Eligible 노드는 홀수개로 구성되어야한다. (권장사항))

분산시스템

Leader node

Data node

Data node

Data node

Shards

Shards

Partitioning

Shard 0

Shard 1

Shard 2

Id = abe1f125dd

->

Murmur3 hash result = 123322

->

Modulo 3 (% 3) result = 1

Scatter-Gather

Replica

• HA를 위한 복제본
• Primary는 모두 다른 노드에 배치되야하지만�Replica는 같은 노드에 배치될 수 있음

​

​

• 복제에 지연시간이 있을 수 있으므로�insert 직후 search 시 검색이 안될 수 있음

​

Elasticsearch의 샤드배치

클러스터에 샤드가 어떻게 배치되나

​

​

1. docs.count가 작은 순

2. store.size_in_bytes가 작은 순

(외 여러가지 조건들)�등으로 각 노드를 순회하면서, 할당할 수 있으면 할당.

​

�자세한 바는 AllocationDecider라는 클래스에 있습니다.

Elasticsearch의 노드분류

• Master-eligible node
• Voting-only master-eligible node
• Data node
• Coordinating only node

​

node.roles: [data, master, voting_only]

​

와 같이 각 노드에 여러 역할을 지정할 수 있다.

자세한 사항은 elastic 공식 document에 잘 설명되어 있습니다.

​

https://www.elastic.co/guide/en/elasticsearch/reference/master/modules-discovery.html

분산시스템

Elasticsearch 코드들여다보기

(7.8.x 기준)

Entrypoint: class Node

Guice – DI 도구

​

Spring과는 다르게

Context Scan을 하지않고

클래스 객체를 일일히 넣는다.

http serving은 Netty 로 구현

​

​

Url Path Router는 trie 자료구조로 구현

/ -> RestMainAction

/_search -> RestSearchAction

/{index}

/{index}/_doc/123

클러스터 leader 선출:

클러스터 상태정보: class ClusterState

인덱스 등 data 정보: class Metadata

Elasticsearch 몇가지 FAQ

Q. Lucene의 인덱스는 Log-Structured Merge Tree 인데 그러면 데이터는 immutable이지 않습니까?

Q. Lucene의 인덱스는 Log-Structured Merge Tree 인데 그러면 데이터는 immutable이지 않습니까?

​

​

A. 그래서 가능하면 삭제는 파일 시스템 기반으로 삭제하도록 인덱스 단위로 삭제해아하고, �인덱스 단위 삭제가 용이하도록 인덱스를 날짜 기반으로 만드는 게 좋습니다. (물론 상황에 따라 다름)

인덱스를 날짜 기반으로 구성하는 것이 샤드 분산에 좋습니다.

Q. TF-IDF는 해당 인덱스 샤드의 모든 문서에 해당 단어가 많아질 수록 점수가 달라지는데, 어느 샤드에 따라 순위가 달라지지 않나요?

Q. TF-IDF는 해당 인덱스 샤드의 모든 문서에 해당 단어가 많아질 수록 점수가 달라지는데, 어느 샤드에 따라 순위가 달라지지 않나요?

​

​

A. 넵. 검색 성능이 중요한 경우 별도의 튜닝이 필요해집니다.

직접 구현해보겠습니다.

https://github.com/actumn/searchgoose

사실 이거 자랑하려고…

Peer-find, Raft, Partitioning, scatter-gather, �TF-IDF 구현

감사합니다