[Solr] Caffeine Cache

[ Solr ] Caffeine Cache 株式会社LIFULL 社内技術勉強会 秀野 亮

前提知識 局所性 ページング ページ置換アルゴリズム キャッシュアルゴリズム 置換ポリシー

局所性（Locality） 1つのリソースに複数回アクセスする処理に関する情報工学上の概念 時間的局所性（temporal locality） • ある時点で参照されたリソースが近い将来にも再び参照される可能性が高いこ と 空間的局所性（spatial locality） • あるリソースが参照されたとき、その近傍のリソースが参照される可能性が高 いこと

ページング（Paging） OSがメモリをページと呼ばれる単位に分割して管理する方式 • • Linuxでは1ページ=4KB Hugepagesを使うと1ページ=2MB 空間的局所性を利用した仕組み • • データ集まりがち 漁業に例えると「魚はモリで突くより地引網」 ← 魚は群れがちだから

ページ置換アルゴリズム （Page replacement algorithm） 空きページがない時に既存ページを再利用する必要がある 誰を切り捨てるか？ • • • 捨てたページを再び必要とするのを避けたい よく使うページは捨てたくない リストラと同じですね？

ページ置換アルゴリズム （Page replacement algorithm） OPT（Optimal Page Replacement） • • 論理的には最適（6秒間使われないページを捨て、0.5秒間使われるページに割当て） 未来を予知できる/メモリの使われ方が完全に予測可能/実行時に分析可能ならイケる →無理ゲー LRU（Least Recently Used） • • 最近使われてないページを捨てる OPTに近い性能、実装してみるとコストがやや高い→派生あり その他 • • NRU/MRU/NFU/FIFO/セカンドチャンス/クロック/ランダム/エイジング LRUの性能悪化を検知してランダムにしたり、ループを検知してMRUに切り替えたり

キャッシュアルゴリズム キャッシュが一杯になった時の置換アルゴリズム • 置換ポリシー（Eviction Policy） • • 高いヒット率→多くの使用情報が必要 高速なアクセス→使用情報が少なく更新が速い • 最も効率的なキャッシュアルゴリズムは、今後長期に渡って必要とされない データを常に捨てていくもの→無理ゲー ヒット率とレイテンシの兼ね合いを考慮する必要がある ページングと同じ性質がある

キャッシュアルゴリズム LRU（Least Recently Used）← Solr8までのデフォルト • • • 最近使われてないデータを捨てる どのデータがどの時点で使われたかという使用情報が必要 これをまともに管理するとかなり手間がかかる PLRU（Pseudo-LRU） • • 確率的に最近使われてないデータを捨てる 厳密に管理しないので実装コストが低い LFU（Least Frequently Used）← Solr4から使える（遅い） • • 使用頻度の低いデータを捨てる 使用情報として使用頻度を保持する必要がある

キャッシュアルゴリズム ARC（Adaptive replacement cache） • • • LRUとLFUの間でバランスを取る O(1) LRU/LFU/以前LRUに入っていた /以前LFUに入っていた、の 4つのキューを利用 LIRS（Low Inter-reference Recency Set） • • • 参照間隔の長短で 2つのグループに分けて管理？（あまり理解できず …） O(1) 捨てたデータを保持するので、その 3倍のキャッシュサイズを用意しないと性能が出ない Window TinyLFU • • • Caffeine Cacheで使われている置換ポリシー O(1) （全く理解できず）

• https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/sketch/climbing/HillClimberWindowTinyLfuPolicy.java

キャッシュアルゴリズム W-TinyLfuは小さなアドミッションLRUを使用し、TinyLfuのアドミッションポリシーで受け入れられた場合は、大きなセグメント化 されたLRUに退避する。TinyLfuはエントリの過去の使用状況を確率的に推定するために、周波数スケッチに依存している。 ウィンドウを使用することで、エントリが再帰的なバーストを示した場合に、ポリシーが高いヒット率を得ることができ、それ以外 の場合は拒否される。ウィンドウとメインスペースのサイズは、ヒルクライミング最適化を用いて適応的に決定される。この構成 により、キャッシュは低いオーバーヘッドでエントリの頻度と再帰性を推定することができる。 この実装では4ビットのCountMinSketchを使用し、キャッシュエントリごとに8バイトで成長させることで正確性を確保してい る。ARCやLIRSとは異なり、このポリシーでは退避した鍵を保持しない。 W-TinyLfu は、最適（OPT）に近いヒット率を提供し、ARC や LIRS に対抗することができる。これは、シンプルで、非常駐エント リを必要とせず、メモリフットプリントが少ないという特徴を持つ。このポリシーは、さまざまなワークロードで LRUを大幅に改善 し、汎用キャッシュに適している。

Solrのキャッシュ（〜Solr8） LRUCache • • • documentCache、queryResultCacheのデフォルト Solr1から使われている古豪 java.util.Map 利用 FastLRUCache • • • • fieldValueCache、filterCacheのデフォルト Solr4から使われている fieldValueCacheはDocValuesが有効だと使われない java.util.concurrent.ConcurrentHashMap 利用（ロックフリー/1クエリーで複数回ヒット時に有効） LFUCache • • • Solr4から実験的に追加された ConcurrentLFUCache 内のコメントに This is not a terribly efficient implementation って書いてある 実用に耐えない実装のまま引退

Solrのキャッシュ（〜Solr8） CaffeineCacheにWindow TinyLFUポリシーを実装（8.3.0） • 旧キャッシュは非推奨に、CaffeineCacheが推奨になる • 9.0.0から8.4.0にバックポートされた 旧キャッシュ実装の非推奨/廃止（8.4.0） solrconfig.xmlでのキャッシュクラス指定の削除（8.8.0） • • • クラス未指定の場合、デフォルトでCaffeineCacheが利用されるようになった Solr8の場合、filedValueCacheだけFastLRUCacheのままでCaffeineCacheにならない （2021-10-01現在）HOME'SではSolr8.8.2を利用しているがCaffeineCacheは使わずLRU 系のまま Transient core cacheもLRUCacheからCaffeineCacheに（8.10.0）

Solrのキャッシュ（Solr9〜） Caffeine Cache

Solrのキャッシュ（Solr9〜） LRUCache / FastLRUCache / LFUCacheは廃止 CaffeineCache一本に

CaffeineCache Google Guava Cacheにインスパイアされたキャッシュライブラリ https://github.com/ben-manes/caffeine 特徴 • • • • • • • • • automatic loading of entries into the cache, optionally asynchronously size-based eviction when a maximum is exceeded based on frequency and recency time-based expiration of entries, measured since last access or last write asynchronously refresh when the first stale request for an entry occurs keys automatically wrapped in weak references values automatically wrapped in weak or soft references notification of evicted (or otherwise removed) entries writes propagated to an external resource accumulation of cache access statistics

• https://github.com/ben-manes/caffeine

CaffeineCache LoadingCache<Key, Graph> cache = Caffeine.newBuilder() .maximumSize(10_000) .expireAfterWrite(10, TimeUnit.MINUTES) .build(key -> createExpensiveGraph(key)); Graph graph = cache.get(key); AsyncCache<Key, Graph> cache = Caffeine.newBuilder() .expireAfterWrite(10, TimeUnit.MINUTES) .maximumSize(10_000) .buildAsync(); CompletableFuture<Graph> graph = cache.getIfPresent(key);

CaffeineCache size-based eviction when a maximum is exceeded based on frequency and recency

Solrのキャッシュ Searcher（IndexSearcher）に紐づく • • Searcherの見ているインデックスは更新されないのでキャッシュが有効になる maxIdleTimeオプションで期限切れにすることもできる インデックス更新時の動き • • 新規のSearcherがopen 現行Searcherはリクエストを処理し続け、新規Searcherはバックグラウンドで準備 • • 現行Searcherのキャッシュを見て、自分のキャッシュを用意（Warming） 準備完了後、現行Searcherに代わってリクエストを処理し始める

Solrのキャッシュ “CaffeineCache supports the async attribute, which determines whether the cache stores direct results (async=false, disabled) or whether it will store indirect references to the computation (async=true, enabled by default). If your queries include child documents or join queries, then async cache must be enabled to function properly. Disabling the async option may use slightly less memory per cache entry at the expense of increased CPU. The async cache provides most significant improvement with many concurrent queries requesting the same result set that has not yet been cached, as an alternative to larger cache sizes or increased auto-warming counts. However, the async cache will not prevent data races for time-limited queries, since those are expected to provide partial results.” https://solr.apache.org/guide/8_10/query-settings-in-solrconfig.html#cache-implementations

• https://solr.apache.org/guide/8_10/query-settings-in-solrconfig.html#cache-implementations

Solrのキャッシュ “CaffeineCache は、キャッシュが直接の結果を保存するか（async=false、無効）、計算への間接参照を保存するか （async=true、デフォルトで有効）を決定するasync 属性をサポートしています。 クエリに子文書や結合クエリが含まれている場合、正しく機能するためには asyncキャッシュを有効にする必要があります。 非同期オプションを無効にすると、キャッシュエントリあたりのメモリ使用量がわずかに少なくなりますが、その分 CPUが増加し ます。 非同期キャッシュは、まだキャッシュされていない同じ結果セットを多くのクエリが同時に要求する場合に、キャッシュサイズを 大きくしたり、自動ウォーミングカウントを増やしたりする代わりに、最も大きな改善をもたらします。 しかし、非同期キャッシュは、時間制限のあるクエリのデータ競合を防ぐことはできません。 ”

まとめ（特にEviction Policyに関して） size-based eviction when a maximum is exceeded based on frequency and recency 一般的にLRUはフルスキャンや改ページ時に性能が悪くなるのに対し、 Window TinyLfu は OPT に近いヒット率を提供し、 ARC や LIRS に対抗することができる シンプルで、非常駐エントリを必要とせず、メモリフットプリントが少ない 様々なワークロードで LRUを大幅に改善し、汎用キャッシュに適している https://github.com/ben-manes/caffeine/wiki/Efficiency

• https://github.com/ben-manes/caffeine/wiki/Efficiency