1-11-1. Making Text Searchable

The first challenge that had to be solved was how to make text searchable. Traditional databases store a single value per field, but this is insufficient for full-text search. Every word in a text field needs to be searchable, which means that the database needs to be able to index multiple values—words, in this case—in a single field.

해결해야 할 첫 번째 과제는, 텍스트를 검색 가능하도록 만드는 방법이다. 전통적인 데이터베이스는 field당 하나의 값을 저장한다. 그러나, 이것은 full-text 검색에는 불충분하다. 텍스트 field에 있는 모든 단어는 검색이 가능해야 한다. 즉, 데이터베이스가 단일 field에 있는 다중 값(이 경우에는 단어들)을 색인할 수 있어야 있다.

The data structure that best supports the multiple-values-per-field requirement is the inverted index, which we introduced in Inverted Index. The inverted index contains a sorted list of all of the unique values, or terms, that occur in any document and, for each term, a list of all the documents that contain it.

multiple-values-per-field 라는 요구사항을, 가장 잘 지원하는 데이터 구조는 Inverted Index에서 소개한 inverted index 이다. inverted index는 특정 document에 있는, 모든 유일한 값이나 단어(terms) 의 정렬된 목록과, 각 단어에 대해, 그것을 포함하고 있는 모든 document의 목록을 가지고 있다.

Term  | Doc 1 | Doc 2 | Doc 3 | ...
------------------------------------
brown |   X   |       |  X    | ...
fox   |   X   |   X   |  X    | ...
quick |   X   |   X   |       | ...
the   |   X   |       |  X    | ...

When discussing inverted indices, we talk about indexing documents because, historically, an inverted index was used to index whole unstructured text documents. A document in Elasticsearch is a structured JSON document with fields and values. In reality, every indexed field in a JSON document has its own inverted index.

inverted indices에 대해 이야기하는 것은, document 를 색인 하는 것에 대해 이야기하는 것이다. 왜냐하면, 역사적으로, inverted index는 구조화되지 않은 텍스트 document를 모두 색인하는데 사용되었기 때문이다. Elasticsearch에서, document 는 field와 value를 가진, 구조적인 JSON document이다. 실제로, JSON document의 모든 색인된 field는, 자신의 inverted index를 가지고 있다.

The inverted index may hold a lot more information than the list of documents that contain a particular term. It may store a count of the number of documents that contain each term, the number of times a term appears in a particular document, the order of terms in each document, the length of each document, the average length of all documents, and more. These statistics allow Elasticsearch to determine which terms are more important than others, and which documents are more important than others, as described in What Is Relevance?.

inverted index는 특정 단어를 포함하는 document의 목록보다, 훨씬 더 많은 정보를 가지고 있다. 각 단어를 포함하는 document의 수, 특정 document에 나타나는 특정 단어의 횟수, 각 document에서 단어의 순서, 각 document의 길이, 모든 document의 평균 길이 등을 저장하고 있다. 이런 통계는 What Is Relevance?에서 언급했듯이, 어떤 단어가 다른 단어보다 더 중요한지, 어떤 document가 다른 것보다 더 중요한지를, Elasticsearch가 판단하는 근거가 된다.

The important thing to realize is that the inverted index needs to know about all documents in the collection in order for it to function as intended.

가정 중요한 것은, inverted index가 의도한대로 동작하기 위해서는, collection에 있는 모든 document에 대해 알아야 한다는 것이다.

In the early days of full-text search, one big inverted index was built for the entire document collection and written to disk. As soon as the new index was ready, it replaced the old index, and recent changes became searchable.

full-text 검색의 초기에는, 전체 document collection을 위해, 하나의 큰 inverted index가 만들어지고, 디스크에 기록되었다. 새로운 index가 준비되자마자, 그것은 기존 index를 대체했다. 그리고, 최근 변경 사항은 검색 가능하게 되었다.

Immutabilityedit

The inverted index that is written to disk is immutable: it doesn’t change. Ever. This immutability has important benefits:

디스크에 기록된 inverted index는 결코 변경할 수 없는, 불변(immutable)이다. 이런 불변성은 중요한 장점이다.

• There is no need for locking. If you never have to update the index, you never have to worry about multiple processes trying to make changes at the same time.

  잠글(lock) 필요가 없다. 절대로 index를 업데이트하지 않는다면, 동시에 변경하려는, 다중 프로세스에 대해 걱정할 필요가 없다.

• Once the index has been read into the kernel’s filesystem cache, it stays there, because it never changes. As long as there is enough space in the filesystem cache, most reads will come from memory instead of having to hit disk. This provides a big performance boost.

  index가 kernel의 file-system cache로 읽혀진다면, 절대로 변경되지 않기 때문에, 그대로 유지된다. file-system cache에 충분한 공간이 있는 한, 대부분의 읽기는 디스크가 아닌 메모리에서 일어난다. 이것은 큰 성능 향상을 가져온다.

• Any other caches (like the filter cache) remain valid for the life of the index. They don’t need to be rebuilt every time the data changes, because the data doesn’t change.

  filter cache 같은 다른 cache는, index가 살아 있는 한 유효한 채로 남는다. 데이터가 변경되지 않기 때문에, 데이터가 변경될 때마다 다시 만들 필요가 없다.

• Writing a single large inverted index allows the data to be compressed, reducing costly disk I/O and the amount of RAM needed to cache the index.

  하나의 큰 inverted index에 쓰는 것은, 데이터를 압축할 수 있도록 만들어, 디스크 I/O의 비용과 index를 cache하는데 필요한 RAM의 양을 줄이게 된다.

Of course, an immutable index has its downsides too, primarily the fact that it is immutable! You can’t change it. If you want to make new documents searchable, you have to rebuild the entire index. This places a significant limitation either on the amount of data that an index can contain, or the frequency with which the index can be updated.

물론, 불변의 index는 단점도 가지고 있지만, 중요한 것은, 그것이 불변이라는 사실이다. 그것을 변경할 수 없다. 새로운 document를 검색 가능하도록 만들기 위해서는, 전체 index를 다시 만들어야 한다. 이것은 index가 포함할 수 있는 데이터의 양이나 index가 업데이트되는 빈도에 따라, 상당한 제한이 있다.