In Elasticsearch 6.0 we’re introducing a new feature called Index Sorting. Users can now optimize Elasticsearch indexes to store documents on disk in a specific order. We’re very excited for Index Sorting, as it’s another useful tool in optimizing Elasticsearch performance!
Elasticsearch 6.0 에서 Index Sorting 이라 불리는 새로운 기능을 도입하였다. 이제 사용자는 document를 disk에 특정 순서로 저장하여 Elasticsearch index를 최적화할 수 있다. Elasticsearch 성능을 최적화하는 또 다른 유용한 tool로서, Index Sorting에 대해 매우 기쁘게 생각한다.
Through this article, we’ll dive into a number of areas:
이 게시물을 통해, 다음과 같은 부분에 대해 자세히 알아보겠다.
- Lucene’s Index Sorting functionality
Lucene의 Index Sorting 기능 - Examples where Index Sorting will improve query performance
Index Sorting이 query 성능을 향상시키는 예제 - Caveats to consider in using Index Sorting for time series data
시계열(time series) data에 대한 Index Sorting 사용 시 고려해야 할 사항 - Performance considerations
성능 고려 사항
Index Sorting in Lucene
Lucene’s IndexSorter
Many years ago, Lucene introduced an offline tool known as the IndexSorter. The IndexSorter copied a source index to a new destination index, and ordered the documents on disk based on a user specified order. At that time, because it was not possible to update the destination index directly, users of this feature had to re-build a sorted view every time new documents were added to the source index. The IndexSorter was the first attempt to provide a way to sort documents on disk, not at search time, but at index time.
몇 년전, Lucene은 IndexSorter 라는 offline tool을 소개했다. IndexSorter는 source index를 새로운 대상 index에 복사하고, 사용자가 지정한 순서에 따라 document를 disk에 정렬했다. 이 때, 대상 index를 직접 update할 수 없었기 때문에, 이 기능의 사용자들은 새로운 document가 source index에 추가될 때마다 정랼된 보기를 다시 생성해야 했다. IndexSorter는 search 시점이 아닌 index 시점에 disk에 document를 정렬하는 방법을 제공하는 첫번째 시도이다.
With index sorting, a new concept called “early termination” was introduced. Suppose for instance that you want to retrieve N documents sorted by date (date being a field in the index). If the index is sorted on disk by this date field it would be possible to “stop” the request after visiting the first N documents that match the query (since they are already in the order the user specified). This is what we call “early termination”. Early termination of a query can bring significant improvement to search response times, especially for sort-based queries, and led to the increased popularity of the IndexSorter tool among Lucene users. The static nature of the tool prevented its usage for indices with a lot of updates, which is why it was eventually replaced with a solution that allows incremental updates. Instead of doing a one-time sort of a static index, a new solution was proposed to sort documents at merge time.
index soring에는 "early termination" 이라는 새로운 개념이 도입되었다. 예를 들어, date(date는 index의 field)로 정렬된 N개의 document를 가져오려 한다고 가정해 보자. index가 이 date field로 disk에 정렬된다면, query에 일치하는 첫번째 N개의 document를 찾은 후, request를 "stop(중지)"할 수 있다 (이미 사용자가 지정한 순서대로 되어 있기 때문에). 이것을 "early termination" 라 한다. query의 early termination은, 특히 정렬 기반의 query에 대해, search response 시간을 크게 향상시킬 수 있어, Lucene 사용사들에게 IndexSorter tool의 인기가 높아졌다. tool의 정적인 특성으로 인해, update가 많은 index에 사용할 수 없었고, 결국 증분 update가 가능한 tool로 대체되었다. 정적 index를 한번 정렬하는 대신, merge 시에 document를 정렬하는 새로운 solution이 제안되었다.
Lucene improvements
Originally, Lucene indexed documents in the order they were received, and assigned each document an incremental (and internal) document id (assigned on a per segment basis). The first document indexed in a segment had a document id of 0, and so on. At search time, each segment is visited in document id order, to retrieve documents that match a user query. In order to retrieve the best N documents for a query, Lucene needs to visit every document matching the query across all segments. If the query matches millions of documents, retrieving only the best N would still require millions of documents to be visited.
원래, Lucene은 받은 순서대로 document를 index하고, 각 document에 증분(그리고 내부적인) document id(segment 별로 할당)를 할당한다. segment에 index된 첫번째 document는 document id 0을 가진다. search시에, 사용자 query에 일치하는 document를 가져오기 위하여, document id 순으로 각 segment를 찾아간다. query에 가장 적합한 N개의 document를 가져오기 위해서는, Lucent은 모든 segment에 걸쳐 query에 일치하는 모든 document를 찾아가야 한다. query가 수만개의 document와 일치한다면, 고작 N개의 document를 가져오기 위해, 수만개의 document를 찾아가야 한다.
A Lucene index creates a new segment whenever a refresh is triggered. This new segment contains all the documents that were added after the last refresh. When the segment is flushed it becomes visible to the searcher and new documents can appear in search results. Because refreshes occur constantly, the number of segments can easily explode in an index. Segment merges happen in the background to limit the number of segments from growing too large. Merges are triggered based on a policy that selects segments eligible for merging, the selected segments are then merged in a new segment that replaces the old segments. By default, the segment merge process copies documents from different segments to a new segment based on their internal document ids. In order to replace the static tool (the IndexSorter mentioned above), a new merge policy was introduced to allow index sorting for dynamic indices that reorders documents during the merge process based on a configurable order (the value of a field for instance). This new design was a huge step in the right direction, and allowed an index to be sorted on the fly and to use this information on a per-segment basis. Some segments are sorted (segments created by a merge) and some are not (the newly flushed segments). At merge time, the unsorted segments are first “sorted” and then merged with other sorted segments.
Lucene index는 refresh가 일어날 때 마다 새로운 segment를 생성한다. 새로운 segment는 마지막 refresh 후에 추가된 모든 document를 가지고 있다. segment가 flush되면, search에 보이게 되어, 새로운 document는 search 결과에 나타날 수 있다. refresh는 지속적으로 발생하기 때문에, segment의 수는 index에서 쉽게 증가할 수 잇다. segment merge는 background에서 발생하여, segment 수가 너무 증가하지 않도록 제한한다. merge는 merge에 적합한 segment를 선택하는 정책에 따라 발생하고, 선택된 segment는 기존의 segment를 대신하는 새로운 segment로 merge된다. 기본적으로, segment merge process는 내부 document id에 기반하여 다른 segment의 document를 새로운 segment로 복사한다. 정적 tool(위에서 언급한 IndexSorter)을 대체하기 위하여 새로운 merge 정책이 소개 되었는데, 이는 설정 가능한 순서(예를 들어 field의 값)에 따라 merge process 를 진행하는 중에 document를 다시 정렬하는 동적 index를 index sorting을 허용한다. 이 새로운 설계는 올바른 방향으로의 커다란 진전이었고, index를 즉시 정렬할 수 있고, segment별로 이 정보를 사용할 수 있다. 일부 segment(merge에 의해 생성된 segment)는 정렬되고, 일부(새로 flush된 segment)는 그렇지 않다. merge 시점에 정렬되지 않은 segment는 먼저 "정렬"된 다음에 다른 정렬된 segment와 merge된다.
This merge policy that lived in a module was then moved to a top-level option on the IndexWriterConfig to make index sorting a first class citizen in Lucene.
module에 있던 merge 정책은 Lucene에서 index sorting을 first class citizen 로 만들기 위하여, IndexWriterConfig 의 top-level option으로 이동되었다.
Though some benchmarks showed that the cost of sorting at merge time can divide the total throughput of indexation by a factor of 2:
일부 test에서는 merge 시점에서의 정렬 비용이 index 총 처리량을 절반으로 떨어질 수 있음을 보여준다.
https://home.apache.org/~mikemccand/lucenebench/sp...
The reason for the reduction in indexing performance is simple: re-sorting segments has a cost, causing merge time and memory consumption for these indices to increase by a large factor.
index 성능이 감소하는 이유는 간단하다. segment를 다시 정렬하면 비용이 발생하기 때문에, 이들 index에 대한 merge 시간과 memory 소비가 크게 증가한다.
Since re-sorting multiple segments at a time is costly, we decided to sort documents earlier in the indexation process. Instead of waiting for merge times to sort multiple segments, we’ve moved the sorting to flush time (when the segments are first created): LUCENE-7579. If all segments are already sorted, merging can occur using a simple merge-sort strategy, which is much faster. This new strategy was first introduced in Lucene 6.5 and increased the throughput benchmarks by almost 65% (see annotation V).
한번에 여러 segment를 다시 정렬하는 데는 많이 비용이 소모되므로, index process 초가에 document를 정렬하기로 했다. merge 시점에 여러 segment를 정렬하는 것을 기다리는 대신, flush 시점으로 정렬을 이동했다 (segment가 처음 생성될 때): LUCENE-7579. 모든 segment가 이미 정렬되어 있다면, merge는 단순한 merge-sort 전략을 사용하여 수행할 수 있다. 이것이 훨씬 더 빠르다. 이 새로운 전략은 Lucene 6.5에 처음 도입되었고, test시애 처리량을 거의 65% 증가시켰다
As you can see in this story index sorting had a lot of history in Lucene but until now it was not available in Elasticsearch. Thanks to all these optimizations, we’ve decided to unlock this feature in Elasticsearch 6.0 and we’re really excited to show how this feature can help you to optimize your use case with this new release!
여기에서 볼 수 있듯이, Lucene의 index sorting에는 많은 hidtory가 있었으나, Elasticsearch에서는 이용할 수 없었다. 이들 모든 최적화때문에, Elasticsearch 6.0 에서 이 기능을 열기로 결정했고, 이 기능이 이번 새로운 release를 통해 여러분에게 어떤 도움이 될 수 있는지를 보여주게 되어 매우 기쁘게 생각한다.
Index Sorting in Action
Early termination of search queries
It’s very common in applications to query for the top X results, sorted by value Y (top player scores, new users, latest events, etc.). In most cases, Elasticsearch will not have enough information to quickly gather the first X results and sort them until the entire data set has been examined. Doc values make this process more efficient, however, in the cases where the dataset is extremely large, a lot more values will be examined and compared than are needed by the user.
응용 프로그램에서 값 Y(상위 player의 점수, 새로운 사용자, 최근 이벤트 등)를 기준으로 정렬된 상위 X개의 결과를 query하는 것은 일반적이다. 대부분의 경우, Elasticsearch는 처음 X개의 결돠를 빠르게 수집하고, 전체 data 집합을 검사할 때까지 그들을 정렬하기에 충분한 정보를 가지고 있지 않다. doc values는 이 process를 더 효과적으로 만든다. 그러나, data 집합이 매우 큰 경우에는 사용자가 필요로 하는 것보다 훨씬 많은 값을 검사하고 비교해야 한다.
With the introduction of index sorting in Elasticsearch 6.0, we can now specify the ordering of documents on disk, allowing Elasticsearch to short circuit and return queries more efficiently. For instance, if we’re creating a leaderboard for a video game company to track the top 3 player scores (and we have a very large number of players!), we can instruct Elasticsearch to store documents in the order of their player score, allowing us to compute the leaderboard much more efficiently.
Elasticsearch 6.0 에서 index sorting이 도입되어, 이제 disk상에서 document의 순서를 지정할 수 있다. 따라서, ELasticsearch는 query를 보다 효율적으로 중단하고 return할 수 있다. 예를 들어, video game 회사가 상위 3명의 palyer의 점수를 추적하는 leaderboard를 만든다고 하면 (그리고 매우 많은 player가 있다), Elasticsearch는 player의 점수 순으로 document를 저장할 수 있고, leaderboard를 보다 효율적으로 계산할 수 있다.
// Get the top 3 player scores (based on the number of points) GET scores/score/_search { "size": 3, "sort": [ { "points": "desc" } ] }
Depending on the version of Elasticsearch, and on usage of index sorting, we can store the documents on disk very efficiently for the query above:
Elasticsearch의 version과 index sorting 사용 여부에 따라, 위의 query를 위해 document를 보다 효율적으로 disk에 저장할 수 있다.
The query above will still need to return a count for the number of results (and requires a little extra work). We can remove this requirement with the new option "track_total_hits" set to false:
위의 query는 결과 수에 대한 count를 반환해야 한다 (그리고 약간의 추가 작업이 필요하다). 새로운 option "track_total_hits"를 false로 설정함으로써 이 요구 사항을 제거할 수 있다.
// Get the top 3 player scores (based on the number of points) GET scores/score/_search { "size": 3, "track_total_hits" : false, "sort": [ { "points": "desc" } ] }
We now have a very efficient leaderboard query for top player scores, using a sorted index.
정렬된 index를 사용하여 상위 player 점수를 위한 매우 효율적인 leaderboard query를 사용할 수 있다.
Specifying an index sorting order in Elasticsearch 6.0
To continue with our example above (creating a leaderboard of top player scores), we will need to tell Elasticsearch how to order the documents on disk. We can do this by providing a definition in the settings for the index:
위의 예제를 계속하기 위해서는 (상위 player 점수의 leaderboard 생성), Elasticsearch에 disk상에서의 document의 순서를 설정해야 한다. index setting에 정의해야 한다.
PUT scores { "settings" : { "index" : { "sort.field" : "points", "sort.order" : "desc" } }, "mappings": { "score": { "properties": { "points": { "type": "long" }, "playerid": { "type": "keyword" }, "game" : { "type" : "keyword" } } } } }
The example above will sort documents on disk by the points field (in descending order). This is helpful for the simple query above (for top 3 player scores).
위의 예에서는 points field(내림차순)로 document를 disk상에 정렬한다. 이는 위의 단순한 query(상위 3명의 player 점수)에 유용하다.
Grouping documents within an index by similar structure
There are many advantages to storing documents sorted by a similar type. For instance, if there is an index named “scores”, some scores may come from the game “Joust”, and include specific fields such as “top-speed” and “farthest-jump”, a score for a different game, such as “Dragon’s Lair” may include fields for “sword-fight-score” and “goblins-killed”:
유사한 type으로 정렬하여 document를 저장하면 많은 이점이 있다. 예를 들어, "scores" 라는 index가 있다고 가정하면, 일부 score는 "Joust" game에서 가져온 "top-speed", "farthest-jump" 같은 특정 field를 포함하고, "Dragon's Lair" 같은 다른 game에서 가져온 "sword-fight-score", "goblins-killed" 같은 field도 포함할 수 있다.
// Score for the game "Joust" { "game" : "joust", "playerid" : "1234", "top-speed" : 212, "farthest-jump" : 49 }
// Score for the game "Dragon’s Lair" { "game" : "dragons-lair", "playerid" : "5678", "sword-fight-score" : 89, "goblins-killed" : 3 }
Storing the documents on disk sorted by game will help place similar documents (with similar field names) together. The advantages to this are query speed (although it’s important to remember this really depends on the query) and compression. Storing similar fields closer together may lead to better compression, and Elasticsearch (and in turn Lucene) is able to store the deltas more efficiently:
disk상에 game으로 정렬된 document를 저장하면, 유사한 document(유사한 field name을 가진)를 함께 배치하는데 도움이 된다. 이렇게 하면 query speed(실제로는 query에 의존한다는 점을 기억하는 것이 중요하지만)와 압축에 도움이 된다. 유사한 field를 더 가까이 함께 저장하면 압축이 향상될 수 있으며, Elasticseach(그리고 결국 Lucene)는 deltas를 보다 효율적으로 저장할 수 있다.
PUT scores { "settings" : { "index" : { "sort.field" : "game", "sort.order" : "desc" } } }
More efficient AND conjunctions
Using index sorting to locate documents on disk in a specific order can also improve AND conjunctions, complex queries with many conditions.
특정한 순서로 disk상에 document를 두기 위해 index sorting을 사용하면 많은 조건을 가진 AND conjunctions와 복잡한 query를 개선할 수 있다.
Let’s continue with our video game example, when a player joins a game, they must be paired up with another player in the same region, skill level, and course. A sample query to find similar players for starting a new match may look similar to the following (get 10 players within the "EU" region, playing "Dragon’s Lair", with a skill rating of 9, and at the "Castle" map):
video game 예제를 계속해 보자. player가 game에 들어오면, 동일한 지역, skill level, course의 다른 player와 쌍을 이루어야 한다. 새 경기를 시작하기 위해 유사한 player를 찾는 간단한 query는 다음과 같다 ("EU 지역, "Dragon's Lair"를 paly, 9의 skill rate 그리고 "Castle" map 에서)
GET players/player/_search { "size": 3, "track_total_hits" : false, "query" : { "bool" : { "filter" : [ { "term" : { "region" : "eu" } }, { "term" : { "game" : "dragons-lair" } }, { "term" : { "skill-rating" : 9 } }, { "term" : { "map" : "castle" } } ] } } }
Let's look at how the Elasticsearch may gather the results needed for the query:
Elasticsearch가 query에 대해 필요한 결과를 수집하는 방법을 살펴보자.
Now, let's specify the ordering of the documents on disk to improve our query above:
이제, 위의 query를 개선하기 위해, disk상에 document의 순서를 지정해 보자.
PUT players { "settings" : { "index" : { "sort.field" : ["region", "game", "skill-rating", "map"], "sort.order" : ["asc", "asc", "asc", "asc"] } }, "mappings": { "player": { "properties": { "playerid": { "type": "keyword" }, "region": { "type": "keyword" }, "skill-rating" : { "type" : "integer" }, "game" : { "type" : "keyword" }, "map" : { "type" : "keyword" } } } } }
We can now see the documents are placed closer together:
document가 더 가까운 곳에 함께 있는 것을 볼 수 있다.
By using a sorted index, we can locate the documents with similar field values closer together, making our query to find players for a given match more efficient.
정렬된 index를 사용함으로써, 유사한 field 값을 가진 document를 더 가까이 함께 위치하게 해, 지정된 경기의 player를 찾는 query가 보다 효율적이 되었다.
When index sorting isn't a good fit
Storing sorted values on disk requires a lot more work at index time from Elasticsearch than storing unsorted values. In some cases the performance overhead of index sorting can decrease write performance by as much as 40-50%. For this reason it is very important to determine if the application should be optimized for query performance or write performance. Optimizing an application for write performance (and taking the hit on query performance) will most likely mean index sorting is not a good option.
disk에 정렬된 값을 저장하려면 정렬되지 않은 값을 저장하는 것보다 Elasticsearch의 index 시점에서 훨신 더 많은 작업이 필요하다. 어떤 경우에는 index sorting의 overhead가 쓰기 성능을 40-50%까지 저하시킬 수 있다. 이런 이유로, 응용프로그램이 query 성능 또는 쓰기 성능 중 어느 것을 최적할지를 결정하는 것이 매우 중요하다. 쓰기 성능에 대한 응용프로그램의 최적화(그리고 query 성능에 영향을 미치는)는 index sorting이 좋은 option이 아닐 수 있다.
You can check the throughput for indexation with and without index sorting. As mentioned above, the performance hit will vary widely and depend on your use case. For example, the geonames Elasticsearch benchmark shows a very small performance hit for Index Sorting (the blue line labeled “Append Sorted”):
index sorting 여부와 관계없이 index 처리량을 확인할 수 있다. 위에서 언급했듯이, 성능 저하는 사용 사례에 따라 크게 달라진다. 예를 들어, geonames Elasticsearch 테스트에서는 Index Sorting에서 매우 적은 성능 저하를 보여준다.
https://elasticsearch-benchmarks.elastic.co/index....
Alternatively, the “NYC Taxis” benchmark shows a large drop in indexing performance with index sorting:
반면에, "NVC Taxis" 테스트는index sorting을 사용한 index 성능이 크게 저하되었다.
https://elasticsearch-benchmarks.elastic.co/index....
In system design, there are tradeoffs at almost every level, with index sorting, the tradeoff we’re considering is less efficient writes (as the document must be sorted) for faster queries (in specific scenarios) vs more efficient writes and slower queries (as the results must be sorted at query time).
시스템 설계시에는, 거의 모든 단계에서 tradeoff가 있는데, index sorting를 사용하면, 보다 빠른 query(특정 시나리오에서)에 대한 덜 효율적인 쓰기(document가 정렬되어야 하므로) vs 더 효울적인 쓰기와 더 느린 query(결과는 query 시점에 정렬되어야 하므로)가 고려해야 할 tradeoff이다.
Similar to any new feature, it is very important to test index sorting with your specific use case and dataset.
다른 새로운 기능과 마찬가지로, 여러분의 사용 사례와 data에 index sorting을 test하는 것은 매우 중요하다.
We’re not finished
This is only the beginning, we’ll continue to improve index sorting for a larger range of use cases!
이것은 시작일 뿐이다. 우리는 광범위한 사용 사례에 대해 index sorting을 개선해 나갈 것이다.
Hopefully this article gives you a good overview of index sorting as a great new tool to consider in your Elasticsearch 6.0 toolbox. In addition to this blog post, the documentation on Index Sorting can be a great resource to bookmark. If you want to try out the new index sorting functionality, download 6.0.0-beta1 and become a pioneer!
이 게시물은 Elasticsearch 6.0 에서 고려할 훌륭한 새 tool인 index sorting에 대한 개요을 제공한다. 이 게시물 이외에도 documentation on Index Sorting 가 좋은 참고가 될 것이다. 새로운 index sorting 기능을 사용해 보고 싶다면, 6.0.0-beta1 을 다운로드해 보자.