Lucene 6.0 introduced new exciting feature called multi-dimensional points. While the name of the feature puts a lot of emphasis on the fact that it supports multiple dimensions, this feature behaves more than decently in the case of a single dimension and actually better than the trie encoding that was used in previous versions of Lucene. This caused us to refactor number-based fields (byte, short, integer, long, float, double, ip and date) to use this new data-structure for indexing numbers.
Lucene 6.0은 다차원 point(multi-dimensional points) 라는 새로운 흥미로운 기능을 소개했다. 기능의 이름이 다차원을 지원한다는 사실에 중점을 두고 있지만, 이 기능은 단일 차원의 경우 훨씬 더 잘 동작하며, 이전 버전의 Licene에서 사용되었던 trie encoding 보다 실제로 더 낫다. 이로 인해, 숫자를 index하는 경우 이 새로운 data 구조를 사용하여, 숫자 기반의 field(byte, short, integer, long, float, double, ip, date)를 재작성하였다.
How does it work?
The current data-structure that underlies dimensional points is called a block KD tree, which in the case of a single dimension is a simple binary search tree that stores blocks of values on the leaves rather than individual values. Lucene currently defaults to having between 512 and 1024 values on the leaves.
차원(dimension) point를 기반으로 하는 현재의 data 구조를 block KD tree 라 하는데, 단일 차원에서, 이는 tree의 leaf에 개별적인 값이 아닌 값의 block을 저장하는 단순한 binary search tree이다. 현재 Lucene은 기본적으로 leaf에 512와 1024 사이의 값을 가진다.
This is quite similar to the b-trees that are used in most regular databases in order to index data. In the case of Lucene, the fact that files are write-once makes the writing easy since we can build a perfectly balanced tree and then not worry about rebalancing since the tree will never be modified. Merging is easy too since you can get a sorted iterator over the values that are stored in a segment, then merge these iterators into a sorted iterator on the fly and build the tree of the merged segment from this sorted iterator.
이는 대부분의 일반 database에서 data를 index하기 위해 사용되는 b-trees와 매우 유사하다. Lucene의 경우, file에 한번만 쓴다는 사실은 완벽하게 균형잡힌 tree를 구성할 수 있기 때문에 쓰기가 쉽고, tree가 절대로 변경되지 않기 때문에 재조정에 대해 걱정할 필요가 없다. merge가 쉽다. segment에 저장된 값들에 대한 정렬된 iterator를 가져온 다음, 이들 iterator를 바로 정렬된 iterator에 병햡하고, 이 정렬된 iterator애서 merge된 segment의 tree를 구성할 수 있기 때문에, merge가 매우 쉽다.
Comparison with the old number implementation
While Mike already reported that 1D points prove faster to index, faster to search, more disk-efficient and more memory-efficient than the old implementation, things got even better with recent optimizations in Lucene 6.1 and the upcoming 6.2:
Mike가 1D points가 기존의 구현보다 index/search가 더 빠르고, 더 효율적인 disk/memory를 사용한다 라고 이미 보고했지만, Lucene 6.1과 향후 6.2에서 최근 최적화에서 더욱 개선되었다.
- The collector for matching doc ids got optimizations so that collecting the set of documents that match a query is now faster.
일치하는 doc id에 대한 collector가 optimizations 되어, query에 일치하는 document 집합을 수집하는 것이 이 제 더 빨라졌다. - The disk format now takes better advantage of the fact that values in a leaf block are close of each other for compression.
이제 disk format 은 압축을 위해 leaf block의 값이 서로 비슷하다는 사실을 더 잘 활용한다. - Each value in the tree is stored next to the doc ID of the document that this value belongs to. These doc IDs are now compressed based on the number of documents in the segment rather than using 4 bytes all the time.
tree의 각 값은 이 값을 가진 document의 doc ID 다음에 저장된다. 이제 이 doc ID는 항상 4 byte가 아닌 segment에 있는 document의 수를 기반으로 compress된다. - While merging 1D points is cheap since trees can be merged with a simple merge sort, flush is more costly as the tree needs to be built from an unordered set of values. But this recently got a speed up by sorting directly in the IndexWriter buffer and switching to radix sort as a sort algorithm.
tree가 단순한 merge sort로 merge될 수 있기 때문에 1D point를 merge하는 것은 비용이 적게 들지만, flush는 정렬되지 않은 값의 집합에서 구성되어야 하므로 비용이 더 많이 든다. 그러나 최근에는 IndexWriter buffer에서 바로 정렬하고, 정렬 알고리즘을 radix sort 로 변경하여, 속도 개선이 이루어졌다.
So I re-ran the same benchmark as in the original post about points to get a more up-to-date comparison in the case of a single dimension.
그래서, 단일 차원(dimension)의 경우에서 최신 비교 자료를 얻기 위해, points에 대한 원래 게시물과 동일한 test를 다시 했다.
For this particular data and set of queries, points proved 36% faster at query time, 71% faster at index time and used 66% less disk and 85% less memory. Numbers may differ based on the data and queries, but we are confident that points will perform much better on average than the current implementation, especially in the case of very high-cardinality fields.
이 특정 data와 query 집합의 경우, point는 query시에 36% 더 빠르며, index시에 71% 더 빠르며, disk 사용량은 66%, memory사용량은 85% 감소했다. numbers는 data와 query에 따라 다를 수 있지만, 특히 cardinality가 매우 높은 field의 경우, 현재 구현보다 points가 훨씬 더 잘 동작한다고 확신한다.
New number types
Beats is pushing the limits of Elasticsearch when it comes to numbers. For time series use-cases in general, users want to be able to index as fast as possible using as little disk space as possible. While integer types are easy to compress based on the number of bits that they actually use (for instance if all integers are between 2 and 200, they can be encoded on one byte), the same is not true for floating-point data. In particular, the fact that they cannot represent decimals accurately makes them use all available bits in order to be as close as possible to the value that needs to be represented. This makes compression hard since values in a given segment rarely have a pattern that can be leveraged for compression.
beat는 numbers에 대해서는 Elasticsearch를 한계까지 테스트하고 있다. 일반적으로 시간 기반 사용 사례의 경우, 가능한 한 작은 disk 공간을 사용하면서 가능한 한 빠른 index를 원한다. integer type은 실제로 사용하는 bit 수에 따라 쉽게 압축(예를 들면, 모든 integer가 2와 200 사이라면, 단일 byte로 인코드할 수 있다)할 수 있지만, floating-point data에서는 그렇지 않다. 특히, 소수를 정확하게 표시할 수 없다는 사실은 표현해야 할 값에 가능한 한 근접하게 하기 위해, 이용 가능한 모든 bit를 사용하도록 만든다. 이렇게 되면, 주어진 segment의 값에서 압축을 위해 사용될 수 있는 pattern이 거의 없기 때문에, 압축이 어려워진다.
But do you actually need the accuracy of a float or a double for your data, or would you happily trade some precision for reduced disk usage and faster queries? For those to whom this sounds like a logical trade-off, we introduced two new field types called half_float and scaled_float.
그런데, 실제로 data에 float이나 double의 정확성이 필요할까? 아니면, disk 사용량이나 더 빠른 query를 위해 정확성을 약간 줄이면 어떨까? 이를 위해, half_float 과 scaled_float 라는 새로운 field type을 도입하였다.
Half floats work the same way as floats and doubles, except that they use fewer bits for the mantissa and the exponent, allowing them to be stored on 16 bits in total, rather than 32 in the case of floats and 64 in the case of doubles. However beware that this storage reduction comes at a cost: they only have 3.3 significant decimal digits and the maximum value is 65504.
Half floats 는 가수와 지수에 대해 더 작은 bit 를 사용한다는 점을 제외하고는, float, double과 동일한 방식으로 동작하는데, float의 경우 32, double의 경우 64가 아닌 16 bit에 저장된다. 그러나, storage의 절약은 비용이 발생한다는 점에 유의하자. 이들은 유효자리수가 3.3 이고 최대값은 65504 이다.
We suspect the new scaled_float field will be even more useful in practice: it takes a scaling factor and for every value, it internally stores the long that is closest to the product of the value and the scaling factor. For instance, with a scaling factor of 100, 0.123 would internally be indexed as 12 and all queries and aggregations would behave as if the value was actually 0.12. This helps because even though values are decimal, they are internally encoded as integers, which Lucene can compress more efficiently.
실제 상황에서는 새로은 scaled_float 가 훨씬 더 유용하리라 생각된다. scaling factor를 사용하고 모든 값에 대해 내부적으로 값과 scaling factor의 곱에 가장 가까운 long을 저장한다. 예를 들어, scaling factor가 100 이라면, 0.123 은 12 로 index되고, 모든 query와 aggregation은 실제로 값이 0.12 인 것처럼 동작한다. 비록 값이 소수이지만, 내부적으로 integer로 encode되어, Lucene은 더 효율적으로 압축할 수 있다.
Conclusion
Number support improved greatly in the upcoming 5.0 release. Feel free to give a try to the alpha releases if you want to check out these improvements on your data.
향후 5.0에서는 number에 대한 지원이 크게 향상되었다. 여러분의 data에 이들 개선 사항을 적용해 보려면, alpha releases 를 사용해 보자.