If you have no idea what questions you will want to ask your data when you start ingesting it, columnar storage is probably a good option for you: it helps in two areas that are often close to the heart of users who deal with large amounts of data:
data를 index하기 시작할 때, 어떤 query를 해야하는지 잘 모를 경우, 아마도 column 저장소가 좋은 선택일 수 있다. 이는 방대한 양의 data를 처리하는 사용자의 의도와 가까운 2가지 영역에 도움이 된다.
- Storage efficiency: Since data that belongs to the same field is stored together, it can be expected to be quite homogeneous, which is something that can be leveraged to make compression more efficient.
동일한 field에 속하는 data는 함께 저장되므로, 상당히 비슷한 종류의 data라고 생각된다. 이것은 더 효율적인 압축에 활용될 수 있다. - "Fast" queries/aggregations: The fact that data for the same field is stored together also helps make better use of the file-system cache since you will not have to load data for fields that are not needed by the query. In addition, by splitting the data into blocks and adding some meta-data about the range or set of unique values in the header of the block, some queries may be able to skip some blocks entirely at query time. There are also some techniques that allow to query the data without decompressing it first.
동일한 field에 data가 함께 저장된다는 사실은, file-system cache를 더 효율적으로 사용할 수 있다.왜냐하면, query에 필요하지 않은 field의 data는 load할 필요가 없기 때문이다. 또한, data를 block으로 나누고, block의 header에 유일한 값의 범위나 집합에 대한 어떤 meta-data를 추가하여, 일부 query는 query시에 일부 block 전체를 건너뛸 수 있다. 먼저 data의 압축을 풀지 않고 data를 query할 수 있는 몇 가지 기법도 있다.
You might have noticed the quotes around Fast in the above paragraph. The reason is that however fast a linear scan is, it is still a linear scan and performs in linear time with the amount of queried data. Elasticsearch takes a different approach that consists in indexing all fields by default and only exposing queries that can leverage these indices so that identifying the matching documents does not need to visit all the data. Well, almost only, there is one query that might run a linear scan in order to identify matching documents, the script query. The purpose of this query is to not require you to reindex for once-in-a-while questions that you had not thought you would need to ask your data when you indexed it, such as finding all documents whose value for field X is less than the value of field Y. But other than this one, all queries make use of some form of index in order to quickly identify matching documents.
위의 문장에서 Fast 주위에 인용 부호를 보았을 것이다. linear scan이 아무이 빨라도 여전히 linear scan이고, query된 data의 양에 따라 linear time 내에 수행되기 때문이다. Elasticsearch는 기본적으로 모든 field를 index하고 이들 index를 활용할 수 있는 query만 노출되므로, 일치하는 document를 확인하기 위하여 모든 data를 검색해야 할 필요가 없는 독특한 방식을 가진다. 거의 유일한데, 일치하는 document를 확인하기 위해야 linear scan을 사용하는 하나의 query가 있는데, script query 이다. 이 query의 목적은, field X의 값이 field Y보다 작은 모든 document를 찾는 것 같은, data를 index할 때 data를 요청할 필요가 없을 거라 생각하는, 가끔씩 하는 질문을 위한 reindex가 불필요한 경우이다. 그러나, 이 외의 모든 query는 빠르게 일치하는 document를 확인하기 위하여, 특정한 형태의 index를 사용한다.
While Elasticsearch does not use a column-oriented view of the data for searching, it still needs one for workloads that work best with columnar data such as sorting and aggregations. In the next sections, we will do a quick survey of the history of columnar data in Lucene and Elasticsearch.
Elasticsearch는 search를 위하여 data의 column 중심의 view를 사용하지 않지만, 정렬, aggregation 같은 column data와 가장 잘 동작하는 작업에서는 여전히 필요하다. 아래에서는, Lucene과 Elasticsearch에서 column data의 역사에 대해 간략하게 설명하겠다.
First, there was fielddata
Lucene was originally designed as a search library, allowing users to get the most relevant documents for a particular query. But soon users wanted to do more: they wanted to be able to sort by arbitrary fields, aggregate information about all matching documents, etc. To cover these needs, Lucene added a feature called FieldCache, which would "uninvert" the inverted index in order to build a column-oriented view of the data in memory. The initial release of Elasticsearch back in 2010 used the same mechanism with what it called fielddata, which was similar to FieldCache, but with more flexible caching management.
Lucene은 원래 search library로 설계되어, 사용자는 특정 query에 대해 가장 관련있는 document를 얻을 수 있다. 그러나, 사용자 곧 더 많은 것을 원했다. 임의의 field를 기준으로 정렬하고 모든 일치하는 document에 대한 aggregation 정보를 원했다. 이런 요구 사항을 해결하기 위하여, Lucene은 memory에 data의 column 중심의 view를 만들기 위해 inverted index를 "uninvert" 하는 FieldCache 라는 기능을 추가했다. 2010년 Elasticsearch의 초기 버전은 FieldCache 와 유사하지만 cache 관리가 더욱 유연한 fielddata 라는 동일한 메커니즘을 사용했다.
Then doc values
The growing use of FieldCache was embarassing: it required an amount of memory that was linear with the amount of indexed data, and made reopening the index slower since FieldCache entries had to be reloaded on all new segments, some of which being potentially very large due to merging. So on the one hand you had an efficient inverted index structure that allowed to find matching documents, but most collectors then had to rely on this inefficient memory-intensive data-structure in order to compute interesting things about the data. This is what lead Lucene to introduce doc values in Lucene 4.0, which was released in the end of 2012. Just like FieldCache, doc values provide a column-oriented view of the data, except that they are computed at index time and stored in the index. Their memory footprint is very low and getting doc values ready to use on a new segment is a matter of opening a file.
FieldCache 의 사용 증가는 당황스러웠다. index된 data의 양에 따라 선형적(linear)인 메모리가 필요하고, FieldCache 항목은 모든 새로운 segment에 대해 다시 load되어야 하고, segment 중 일부는 merge 때문에 잠재적으로 매우 클 수 있어, index를 다시 open하는 것이 더욱 느려졌다. 그래서, 한편으로는, 일치하는 document를 찾을 수 있는 효율적인 inverted index를 가질 수 있었으나, data에 대해 흥미로운 무엇인가를 계산하기 위해, 비효율적인 memory 집약적인 data 구조에 의존해야 했다. 이것이 Lucene이 2012년 말 Lucene 4.0 에서 doc values 를 도입한 배경이다. doc values는 index시에 계산되어 index에 저장된다는 점을 제외하면, FieldCache 와 마찬가지로, data의 column 중심 view를 제공한다. 사용하는 memory 공간은 매우 적으며, 새로운 segment에서 사용할 준비가 된 doc values를 얻는 것은 file을 여는 것과 비슷하다.
The fact that doc values are computed at index time also gives more opportunities for compression. The longer it takes to uninvert fielddata, the longer users have to wait before changes to the index becomes visible, which is undesirable. On the other hand doc values are either computed asynchronously at merge or on small datasets at flush time, so it is fine to spend more time doing interesting compression. Here is a non exhaustive list of some compressions techniques that doc values use that fielddata doesn't:
doc values가 index 시에 계산된다는 사실은 압축에 대해서도 더 많은 기회를 제공한다. fielddata를 uninvert하는데 시간이 오래 걸릴수록, 사용자에게 index의 변경사항이 표시되기 전에 더 오래 기다려야 하므로 바람직하지 않다. 반면에, doc values는 merge시에 비동기적으로 혹은 flush시에 작은 data 집합에서 계산되므로, 압축을 하는데 더 많은 시간을 할애할 수 있다. 다음이 fielddata는 사용하지 않고 doc values를 사용하는 일부 압축 기술의 전체 목록은 아니다.
- Since doc values can afford to perform two passes on the data, they do a first pass on numeric fields to compute the required number of bits per value and a second one to do the encoding. This way they can use a fine-grained list of numbers of bits per value for the encoding. On the other hand fielddata only used 8, 16, 32 or 64 since changing the number of bits on the fly would incur a costly resize.
doc values는 data에 대해 2번 수행할 수 있으므로, 먼저 numeric field에 대해 값별로 필요한 bit의 수를 계산하고, 2번째에서는 encode를 한다. 이렇게 하면, encode에 대해, 값 별로 필요한 bit 수의 목록을 세밀하게 분류할 수 있다. 반면에 fielddata는 8, 16, 32, 62 만을 사용했기 때문에, bit 수의 변경은 즉시 비용이 많이 소모되는 크기 조정이 발생한다. - The (sorted) terms dictionary for string fields is split into blocks and each block is compressed based on shared prefixes between consecutive terms.
string field에 대한 (정렬된) terms dictionary은 block으로 분할되고, 각 block은 연속된 terms 사이의 공유된 prefix를 기준으로 압축된다. - Numeric doc values compute the greatest common divisor between all values and only encode the non-common part. This is typically useful for dates that only have a second or day granularity.
numeric doc values는 모든 값 사이의 최대 공약수를 계산하고, 비 공통적인 부분만 encode한다. 이것은, date에 대해서는, 일반적으로 초나 날짜를 가진 경우에만 유용하다.
Elasticsearch integration
Doc values became available in Elasticsearch in version 1.0 (February 2014) as an opt-in. However at that time, the performance did not quite match that of fielddata yet: Elasticsearch was hiding doc values behind its existing fielddata API, introducing overhead, and it took Lucene some time before introducing a dedicated type for multi-valued numerics and a random-access API for index inputs that helped performance significantly. Both these concerns got fixed in Elasticsearch 1.4, which was the first release to have matching performance of fielddata and doc values. We then enabled doc values by default in Elasticsearch 2.0 and the next major release of Elasticsearch (5.0) will not support fielddata anymore, leaving doc values as the only option for having a columnar representation of the data.
doc values는 Elasticsearch 1.0 (2014.02)에 opt-in으로 제공되었다. 그러나, 그 당시 그 성능은 fileddata에 아직 미치지 못했다. Elasticsearch는 doc values를 기존의 fielddata API 뒤에 숨기고, overhead를 도입했으며, Lucene은 multi-value numeric을 위한 전용 type 과 성능에 크게 도움이 되는 index input을 위한 random-access 도입하는데 얼마간의 시간이 걸렸다. 이 두 가지 문제는 fielddata와 doc values의 성능을 같게 하는 첫 번째 release인 Elasticsearch 1.4 에서 수정되었다. 그 다음에 Elasticsearch 2.0 에서 기본적으로 doc values를 사용하도록 했고, 다음 major release인 Elasticsearch 5.0 에서는, 더 이상 fielddata를 지원하지 않도록 해, data의 column 표현을 위한 유일한 option으로 doc values를 남겨두었다.
Specifics of Elasticsearch's column store
Does it make Elasticsearch a good general-purpose replacement for column-stores? No. As usual, it is better to do one thing and do it well. But the Elasticsearch column store has one key characteristic that makes it interesting: values are indexed by the doc id of the document that they belong to. What does it mean? Doc ids are transient identifiers of documents that live in a segment. A Lucene index is made of several components: an inverted index, a bkd tree, a column store (doc values), a document store (stored fields) and term vectors, and these components can communicate thanks to these doc ids. For instance, the inverted index is able to return an iterator over matching doc ids, and these doc ids can then be used to look up the value of a field thanks to doc values: this is how aggregations work.
이것이 Elasticsearch에서 colimn 저장소의 좋은 범용 대체제가 될 수 있을까? 아니다. 일반적으로, 하나만 잘 하는 것이 더 낫다. 그러나, Elasticsearch column 저장소에는 흥미로운 한가지 주요 특성이 있다. 값(value)은 그들이 속한 document의 doc id로 index된다. 어떤 의미일까? doc id는 segment에 있는 document의 임시 식별자이다. Lucene index는 여러 가지 요소(inverted index, bkd tree, column 저장소-doc values, document 저장소-stored fields, term vectors)로 구성되어 있다. 이들 요소는 doc id를 이용하여 통신할 수 있다. 예를 들어, inverted index는 일치하는 doc id에 대한 반복자(iterator)를 return할 수 있고, 이들 doc id는 doc values를 이용하여 그 값을 검토하는데 사용된다. 이것이 aggregation이 동작하는 방법이다.
This makes Elasticsearch particularly good at running analytics on small subsets of an index, since you will only pay the price for documents that match the query. This is how user interfaces to Elasticsearch like Kibana make it easy to slice and dice the data, by recursively filtering subsets that seem to have some interesting properties and running analytics on them.
이렇게 하면, Elasticsearch는 query에 일치하는 document에 대한 비용만 지불하므로, 특히 index의 작은 하위 집합에서 분석을 하는데 특히 유용하다. 이것이 kibana 같은 Elasticsearch에 대한 UI를 통해, 몇 가지 흥미로은 특성을 가진 것으로 보이는 하위 집합을 재귀적으로 filtering하고, 분석을 실행함으로써, data를 다루는 방법이다.
Moreover, Lucene is geared towards making search operations fast. Thus doc values do not store the raw bytes for each document in case of a string field. Instead it writes separately a terms dictionary containing all unique values in sorted order and writes the indexes of string values in the column store. This helps since small integers make better keys than strings and allow to run eg. terms aggregations more efficiently by keying on the term index rather than the term bytes and using an array rather than a hash table as a data structure for storing per-term counts.
또한, Lucene은 search 연산을 빠르게 하도록 설계되었다. 따라서, doc values는 string field의 경우, 각 document의 원래 byte를 저장하지 않는다. 대신, 모든 고유한 값을 정렬된 순서대로 가지는 term dictionary를 별도로 작성하고, string 값의 index를 column 저장소에 작성한다. 이것은 작은 정수가 string보다 더 좋은 key를 만드는데 도움이 되고, 실행하도록 한다. 예를 들자면, term aggregation은 term byte보다는 term index로 key를 잡는 것이, 그리고 term별 count를 저장하기 위한 data 구조로서 hash table보다는 array를 사용하는 것이 더 효율적이다.
What's next?
Given that doc values need to be indexed by the doc id of the document they belong to, the current approach that Lucene takes is to reserve a fixed amount of space per document. While this makes doc values lookups very efficient, this has the undesired side-effect of not being space-efficient for sparse fields, since documents that do not have a value would still require the same amount of storage as documents that have values. This is why Elasticsearch works best when all documents in an index have a very similar set of fields.
doc values가 포함된 document의 doc id로 index되어야 하는 경우, Lucene이 사용하는 접근 방식은 document별로 고정된 크기의 공간을 예약하는 것이다. 이렇게 하면 doc values 조회는 매우 효율이지만, 값을 가지지 않는 document와 가지는 document가 동일한 양의 저장소를 필요로 하기 때문에, 드물게 나타나는 field의 경우 효율적인 공간 사용이 되지 않는, 원치 않는 부작용이 있다. 이것이 모든 document가 매우 유사한 field 집합을 가질 경우, Elasticsearch가 가장 잘 동작하는 이유이다.
However, there are ongoing developments that are exploring switching doc values to an iterator API rather than a random-access API so that these sparse cases could be handled more efficiently and that compression could be more efficient using techniques like run-length encoding.
그러나, 드물게 나타나는 경우에 더 효율적으로 처리하고 run-length encoding 같은 기술을 사용하여 더 효율적으로 압축할 수 있도록 하기 위하여, random-access API 대신 doc values를 iterator API로 전환하는 방법을 모색하는 개발을 진행 중이다.