"lucene skip list"でWeb検索した。
元記事だけだと難しくて理解できないので解説ブログもあわせて読む。
Not all search systems need to update their contents quickly. In a warehouse inventory system, for example, one daily update to its search index might be acceptable. At Twitter -- where people are constantly looking for the answer to “what’s happening” -- real-time search is a must.
Twitterの検索はリアルタイム検索が必要だった。
over half a billion tweets are sent each day
https://blog.reachsumit.com/posts/2020/07/twitter-search-redesign/
Twitterの2018年時点で、5億件/day=5,787/sec tweetとのこと。
ポイントは
- postings listのdocument IDを、timestampでsortしてから割り当てるのではなく、timestampから直接算出できるように変更→buffer/sortによるlatencyをなくすため
- postings listの実装をunrolled linked listからskip listに変更→要素の挿入時に順序が保証されなくなることに伴い、任意の位置への挿入が必要であったため
- skip listに4つの独自カスタマイズを施す→Twitterの検索パターンに最適化するため
- skip listの弱点であるキャッシュ不親和性は、データ特性により影響が小さいことがわかった
事後的ではあるが、すべての技術的決定がindexing latencyを15 secから1 secにするという大義に基づいてなされている点が非常に勉強になる。