상향식 관점에서 본 Elasticsearch, 제1부

서문

동기는 Elasticsearch, Lucene 및 어느 정도까지는 일반적으로 검색 엔진이 실제로 어떻게 작동하는지 더 잘 이해하기 위한 것입니다. 바퀴가 돌아가게 하고 페달을 밟음으로써 자동차를 운전할 수 있지만, 매우 유능한 운전자들은 일반적으로 최소한 차량의 역학을 이해합니다. 검색 엔진도 마찬가지입니다. Elasticsearch는 매우 사용하기 쉬운 API를 제공하며, 그다지 노력을 들이지 않고 시작해서 많은 작업을 진행할 수 있습니다. 그러나 이를 최대한 활용하려면 기본 알고리즘과 데이터 구조에 대한 지식을 갖추는 것이 좋습니다. 이러한 이해를 통해 사용자 검색 경험을 개선하는 동시에 시스템의 성능, 신뢰성 및 업데이트를 (거의) 실시간으로 유지할 수 있도록 상당한 기능을 최대한 활용할 수 있습니다.

기본 인덱스 구조인 역 인덱스부터 시작하겠습니다. 이것은 매우 다용도의 데이터 구조입니다. 동시에 역시 사용하기도 쉽고 이해하기도 쉽습니다. 즉, Lucene의 구현은 매우 최적화되어 있으며, 놀라운 엔지니어링의 위업입니다. 우리는 Lucene의 구현 세부 사항에 대해 모험적으로 살펴보는 대신, 역 인덱스가 어떻게 사용되고 구축되는지에 대해서만 알아볼 것입니다. 이는 우리가 검색하고 색인할 수 있는 방법에 영향을 미치는 것입니다.

역 인덱스를 추상화 레벨의 "맨 아래"로 소개하며, 다음을 살펴보겠습니다.

• 단순 검색 수행 방법.
• 어떤 유형의 검색을 효과적으로 수행할 수 있는지 (그리고 수행할 수 없는지), 그리고 역 인덱스를 사용하여 문제가 스트링 접두사 문제처럼 보일 때까지 문제를 변환하는 이유.
• 텍스트 처리가 중요한 이유.
• 인덱스가 "세그먼트"에 구축되는 방식과 이것이 검색 및 업데이트에 영향을 미치는 방식.
• Lucene 인덱스를 구성하는 것.
• Elasticsearch 샤드 및 인덱스.

이 시점에서, 검색 및 색인 시 단일한 Elasticsearch 노드 내에서 어떤 일이 일어나는지에 대해 자세히 알게 됩니다. 이 시리즈의 두 번째 게시물에서는 Elasticsearch의 분산적인 측면을 다룰 것입니다.

역 인덱스 및 인덱스 단어

"Winter is coming.", "Ours is the fury.", "The choice is yours." 이렇게 세 개의 간단한 문서를 가지고 있다고 해봅시다. 간단한 텍스트 처리(소문자로 설정, 구두점 제거 및 단어 분할) 후 그림에 표시된 "역 인덱스"를 구성할 수 있습니다.

역 인덱스는 단어를 포함하는 문서(또는 어쩌면 문서의 위치)에 단어를 매핑합니다. 사전의 단어들이 정렬되어 있으므로, 단어를 빠르게 찾을 수 있으며, 그에 따라 게시물 구조에서 단어가 출현한 횟수도 빠르게 찾을 수 있습니다. 이는 특정 문서와 관련된 단어들을 나열하는 "일반 인덱스"와 반대입니다.

그런 다음, 모든 단어와 그 출현 횟수를 찾아 여러 단어가 포함된 단순 검색을 수행하고, 일련의 출현 횟수 집합의 교집합(AND 검색의 경우)이나 합집합(OR 검색의 경우)을 선택하여 결과적인 문서 목록을 얻습니다. 더 복잡한 유형의 쿼리는 분명히 더 정교하지만, 접근 방식은 동일합니다. 먼저 사전을 운영하여 후보 단어들을 찾은 다음 해당되는 출현 횟수, 위치 등을 찾습니다.

따라서 인덱스 단어는 검색 단위입니다. 우리가 생성하는 단어들은 효율적으로 수행할 수 있는(수행할 수 없는) 검색 유형을 지정합니다. 예를 들어, 위 그림의 사전을 사용하면 "c"로 시작하는 모든 단어를 효율적으로 찾을 수 있습니다. 그러나 "ours"가 포함되는 모든 것에 대해 효율적으로 검색을 수행할 수는 없습니다. 그러려면, "yours"에도 하위 스트링이 포함되어 있다는 것을 알기 위해 모든 단어들을 통과해야 합니다. 이것은 인덱스가 아주 작은 경우가 아니라면 엄청나게 비용이 많이 듭니다. 복잡도 면에서, 접두사로 단어들을 찾는 것은 \(\mathcal{O}\left(\mathrm{log}\left(n\right)\right)\)인 반면, 임의의 하위 스트링으로 단어들을 찾는 것은 \(\mathcal{O}\left(n\right)\)입니다.

다시 말해서, 우리는 단어 접두사가 주어진 것들을 효율적으로 찾을 수 있습니다. 우리가 가진 모든 것이 역 인덱스일 때, 모든 것이 스트링 접두사 문제처럼 보이면 좋겠다는 생각을 하게 됩니다. 다음은 이러한 변형의 몇 가지 예입니다. 어떤 것들은 단순합니다. 마지막 것은 마법에 가깝습니다.

• "tastic"으로 끝나는 모든 것을 찾기 위해, 역으로 색인하고(예: "fantastic" → "citsatnaf") "citsat"로 시작하는 모든 것을 검색할 수 있습니다.
• 하위 스트링을 찾는 것은 종종 단어들을 "n-그램"이라고 불리는 더 작은 단어들로 나누는 것을 포함합니다. 예를 들어, "yours"를 "^yo", "you", "our", "urs", "rs$"로 나눌 수 있습니다. 즉, "ours"와 "urs"를 검색하면 "ours"의 출현 횟수를 얻게 된다는 의미입니다.
• 노르웨이어와 독일어 같이 복합 단어가 있는 언어의 경우, "Donaudampfschiff"와 같은 단어를 {"donau", "dampf", "schiff"}(예: "shiff")로 "해체"해야 "schiff"를 검색할 때 이를 찾을 수 있습니다.
• (60.6384, 6.5017)과 같은 지리적 좌표점은 "geo hash(공간 데이터)"로 변환될 수 있으며, 이 경우 "u4u8gyykk"입니다. 스트링이 길수록, 정밀도가 높아집니다.
• 예를 들어, 사람들의 이름에 매우 유용한 음성 일치가 가능하도록 하기 위해, "Smith"를 {"SM0", "XMT"}로, "Schmidt"를 {"XMT", "SMT"}로 변환하는 Metaphone과 같은 알고리즘이 있습니다.
• 숫자 데이터(및 타임스탬프)를 처리할 때, Lucene은 트라이 구조와 같은 방식으로 여러 개의 정확도가 다른 단어들을 자동으로 생성하므로 범위 검색을 효율적으로 수행할 수 있습니다¹. 단순화하면, 숫자 123은 "1"-100, "12"-10 및 "123"으로 저장할 수 있습니다. 따라서, [100, 199] 범위의 모든 것을 검색하는 것은 "1"-100-단어와 일치하는 모든 것입니다. 이는 "1"로 시작하는 모든 것을 검색하는 것과는 다릅니다. 물론 "1234" 등도 포함하게 되기 때문입니다.
• "Did you do mean?"을 입력하고 입력에 가까운 철자를 찾으려면, 사전을 효과적으로 통과하도록 "Levenshtein" 자동기계(automaton)를 만들 수 있습니다. 이것은 매우 복잡합니다. 어떻게 Lucene에 이르게 되었는지에 대한 흥미로운 이야기를 읽어보세요.

텍스트 처리에 대한 기술적 심층 연구는 앞으로 여러 게시글에서 흥미롭게 다룰 만한 주제이지만, 여기서는 인덱스 단어 생성에 대해 꼼꼼한 것이 왜 중요한지를 중점적으로 소개했습니다. 그 이유는 효율적으로 수행될 수 있는 검색을 얻기 위해서입니다.

인덱스 구축

역 인덱스를 구축할 때는 검색 속도, 인덱스 압축성, 색인 속도 및 새 변경 사항을 표시하는 데 걸리는 시간 등 몇 가지 우선 순위를 지정해야 합니다.

검색 속도와 인덱스 압축성은 관련이 있습니다. 더 작은 인덱스를 검색할 때 처리해야 할 데이터가 줄어들고 메모리에 더 많은 데이터가 저장됩니다. 두 가지 모두, 특히 압축성은 우리가 아는 바와 같이 색인 속도와 반비례합니다.

인덱스 크기를 최소화하기 위해, 다양한 압축 기술이 사용됩니다. 예를 들어, 게시물을 저장할 때(매우 커질 수 있음), Lucene은 델타 인코딩(예: [42, 100, 666]은 [42, 58, 566]으로 저장됨), 가변 바이트 수(작은 숫자를 단일 바이트로 저장할 수 있음) 사용 등과 같은 트릭을 활용합니다.

데이터 구조를 작고 조밀하게 유지한다는 것은 데이터 구조를 효율적으로 업데이트할 수 있는 가능성을 희생한다는 것을 의미합니다. 실제로 Lucene은 업데이트를 전혀 하지 않습니다. Lucene이 작성한 인덱스 파일은 변경할 수 없습니다. 즉, 업데이트되지 않습니다. 예를 들어, 이는 업데이트할 수 있는 B-트리와는 상당히 다르며 종종 채우기 비율을 지정하여 업데이트 예상량을 나타낼 수 있습니다.

삭제는 예외입니다. 색인에서 문서를 삭제하면, 문서는 특수 삭제 파일로 표시됩니다. 이 파일은 실제로 업데이트 비용이 저렴한 비트맵입니다. 인덱스 구조 자체는 업데이트되지 않습니다.

따라서 이전에 색인된 문서를 업데이트하면 삭제된 후 문서가 다시 삽입됩니다. 이것은 문서를 업데이트하는 것이 애초에 추가하는 것보다 훨씬 더 비싸다는 것을 의미합니다. 따라서 빠르게 변화하는 카운터와 같은 것을 Lucene 인덱스에 저장하는 것은 일반적으로 좋지 않습니다. 즉, 값의 내부 업데이트가 없습니다.

새 문서가 추가될 때(아마도 업데이트를 통해) 인덱스 변경 사항은 먼저 메모리에 버퍼링됩니다. 결국, 인덱스 파일 전체가 디스크로 플러시됩니다. 이것은 Lucene적인 의미에서의 "flush"라는 점에 유의하세요. Elasticsearch의 플러시 작업에는 트랜잭션 로그 섹션에서 다루는 Lucene 커밋 등이 포함됩니다.

플러시 시기는 변경 사항을 얼마나 빨리 표시해야 하는지, 버퍼링에 사용할 수 있는 메모리, I/O 포화도 등 다양한 요인에 따라 달라질 수 있습니다. 일반적으로, 색인 속도의 경우, I/O가 유지할 수 있을 정도로 크기가 작은 한, 더 큰 버퍼가 좋습니다². 다음 섹션에서 조금 더 자세히 설명하겠습니다.

작성된 파일은 인덱스 세그먼트를 구성합니다.

인덱스 세그먼트

Lucene 인덱스는 기본적으로 "미니 인덱스"인 하나 이상의 불변 인덱스 세그먼트로 구성됩니다. 검색을 수행할 때, Lucene은 모든 세그먼트에서 검색을 수행하고 삭제 내용을 필터링한 다음 모든 세그먼트의 결과를 병합합니다. 세그먼트 수가 증가함에 따라 이는 점점 더 지루하고 까다로운 작업이 됩니다. 관리 가능한 세그먼트 수를 유지하기 위해, Lucene은 새 세그먼트가 추가될 때 일부 병합 정책에 따라 세그먼트를 병합하기도 합니다. Lucene 해커 Michael McCandless는 세그먼트 병합을 설명하고 시각화하는 훌륭한 게시물을 올려 놓았습니다.³ 세그먼트가 병합되면 삭제된 것으로 표시된 문서가 최종적으로 폐기됩니다. 따라서 문서를 추가하면 인덱스 크기가 작아집니다. 즉, 병합을 트리거할 수 있습니다.

Elasticsearch와 Lucene은 일반적으로 세그먼트 병합 시기를 잘 처리합니다. 병합 설정을 구성하여 Elasticsearch의 정책을 조정할 수 있습니다. optimize API를 사용하여 강제 병합할 수도 있습니다.

세그먼트를 디스크로 플러시하기 전에, 변경 사항이 메모리에 버퍼링됩니다. 옛날(Lucene

(플러시 또는 병합으로 인해) 새 세그먼트가 생성되면, 특정 캐시가 무효화되어 검색 성능에 부정적인 영향을 미칠 수 있습니다. 필드 및 필터 캐시와 같은 캐시는 세그먼트별입니다. Elasticsearch에는 warmer-API⁵가 있으므로, 새 세그먼트를 검색에 사용하기 전에 필요한 캐시를 "웜(warmed)"할 수 있습니다.

Elasticsearch를 사용하는 플러시의 가장 일반적인 원인은 아마도 기본적으로 초당 한 번씩 발생하는 연속 인덱스 새로 고침입니다. 새 세그먼트가 플러시되면, 검색을 위해 이용할 수 있게 되어 (거의) 실시간 검색이 가능해집니다. 플러시는 (확인된 쓰기를 기다릴 필요가 없기 때문에) 커밋만큼 비싸지는 않지만, 새 세그먼트를 생성하여 일부 캐시를 무효화하고 병합을 트리거할 수 있습니다.

색인 처리량이 중요한 경우(예: 배치(재) 인덱싱), 작은 세그먼트를 플러시하고 병합하는 데 많은 시간을 소비하는 것은 생산적이지 않습니다. 따라서 이러한 경우 refresh_interval 설정을 일시적으로 늘리거나 자동 새로 고침을 모두 비활성화하는 것이 좋습니다. 항상 수동으로 새로 고칠 수 있고 색인이 완료되면 새로 고칠 수 있습니다.

Elasticsearch 인덱스

"컴퓨터 과학의 모든 문제는 다른 레벨의 간접적인 방법으로 해결할 수 있다." – David J. Wheeler

Elasticsearch 인덱스는 복제본이 0개 이상일 수 있는 하나 이상의 샤드로 구성됩니다. 이것들은 모두 개별 Lucene 인덱스입니다. 즉, Elasticsearch 인덱스는 많은 Lucene 인덱스로 구성되며, Lucene 인덱스는 인덱스 세그먼트로 구성됩니다. Elasticsearch 인덱스를 검색하면, 검색이 모든 샤드(그리고 모든 세그먼트)에서 실행되고 병합됩니다. 여러 Elasticsearch 인덱스를 검색할 때도 마찬가지입니다. 실제로 두 개의 Elasticsearch 인덱스를 각각 하나의 샤드로 검색하는 것은 하나의 인덱스를 두 개의 샤드로 검색하는 것과 거의 같습니다. 두 경우 모두, 두 개의 기본 Lucene 인덱스가 검색됩니다.

이제부터 이 글에서 "인덱스"라고 할 때는 Elasticsearch 인덱스를 의미합니다.

"샤드"는 Elasticsearch의 기본 확장 단위입니다. 문서가 인덱스에 추가되면 문서는 샤드로 라우팅됩니다. 기본적으로 문서 ID의 해시에 따라 라운드 로빈 방식으로 수행됩니다. 이 시리즈의 두 번째 부분에서는, 샤드가 어떻게 이동하는지에 대해 더 자세히 알아보겠습니다. 그러나 샤드 수는 인덱스 생성 시 지정되므로 나중에 변경할 수 없다는 것을 알아두시는 것이 중요합니다. Elasticsearch에 대한 Shay의 초기 프레젠테이션을 보면, 샤드가 사실상 완전한 Lucene 인덱스인 이유와 다른 방법에 비해 다양한 이점과 트레이드오프를 탁월하게 설명하고 있습니다.

검색 요청이 어느 Elasticsearch 인덱스와 어떤 샤드들(및 복제본들)로 전송될 것인지는 다양한 방법으로 사용자 정의할 수 있습니다. 인덱스 패턴, 인덱스 별칭, 문서 및 검색 라우팅을 결합하여, 다양한 파티셔닝 및 데이터 흐름 전략을 구현할 수 있습니다. 여기서는 자세히 다루지 않겠지만, 문서 라우팅 사용자 정의에 대한 Zachary Tong의 글과 빅데이터, 검색 및 분석에 대한 Shay Banon의 프레젠테이션을 추천해 드립니다. 간단한 아이디어를 제공해 드리기 위해, 다음과 같은 몇 가지 예를 소개합니다.

• 로그, 트윗 등과 같은 많은 데이터는 시간 기반입니다. 매일 (또는 매주, 매월 등) 인덱스를 생성하여, 특정 시간 범위로 검색을 효율적으로 제한하고 오래된 데이터를 삭제할 수 있습니다. 기존 인덱스에서 효율적으로 삭제할 수는 없지만 전체 인덱스를 삭제하는 것은 저렴하다는 점을 기억해 두세요.
• 검색이 특정 사용자로 제한되어야 하는 경우(예: "메시지 검색"), 검색해야 하는 인덱스 수를 줄이기 위해 해당 사용자에 대한 모든 문서를 동일한 샤드로 라우팅하는 것이 유용할 수 있습니다.

트랜잭션

Lucene에는 트랜잭션 개념이 있지만, Elasticsearch에는 없습니다. Elasticsearch의 모든 작업은 동일한 타임라인에 추가되며, 플러시는 타이밍에 따라 달라지므로 노드 간에 완전히 일치할 필요는 없습니다.

분산형 시스템에서 노드 전체에 걸친 인덱스 간에 서로 다른 세그먼트, 캐시 등의 분리 및 가시성을 관리하는 것은 매우 어렵습니다. 이것을 시도하는 대신에, 빠른 것을 우선시합니다.

Elasticsearch에는 색인할 문서가 추가되는 "트랜잭션 로그"가 있습니다. 로그 파일에 추가하는 것은 세그먼트를 구축하는 것보다 훨씬 저렴하므로 Elasticsearch는 작동 중단 시 손실되는 메모리 내 버퍼 외에도 내구성 있는 곳에서 문서를 색인할 수 있습니다. 색인할 때 필요한 일관성 수준을 지정할 수도 있습니다. 예를 들어, 색인 작업이 반환되기 전에 모든 복제본이 문서를 색인하도록 요구할 수 있습니다.

요약

요약하자면, Lucene이 단일 노드에서 인덱스를 구축, 업데이트 및 검색하는 방법에 대해 알아야 할 중요한 속성은 다음과 같습니다.

• 우리가 색인하는 텍스트를 처리하는 방법은 우리가 검색할 수 있는 방법을 지정합니다. 적절한 텍스트 분석이 중요합니다.
• 인덱스는 먼저 메모리 내에 구축된 다음, 세그먼트에서 디스크로 플러시됩니다.
• 인덱스 세그먼트는 변경할 수 없습니다. 삭제된 문서는 그와 같이 표시됩니다.
• 인덱스는 여러 세그먼트로 구성됩니다. 검색은 모든 세그먼트에서 수행되며 결과는 병합됩니다.
• 세그먼트는 때때로 병합됩니다.
• 필드 및 필터 캐시는 세그먼트별입니다.
• Elasticsearch에는 트랜잭션이 없습니다.

이 시리즈의 다음 글에서는 클러스터 전체에서 검색 및 색인이 수행되는 방식에 대해 살펴보겠습니다.