並行キャッシュライブラリーの開発で得られた知見

Rust.Tokyo 2023カンファレンスの発表スライドです。

The slides for my talk at Rust.Tokyo 2023 conference.

Written in English and Japanese.

Transcript

1. @tatsuya6502 開発で得られた知⾒ a concurrent cache library the development of Insights gained from 並⾏キャッシュライブラリーの Rust.Tokyo 2023
2. Who am I? Freelance software engineer. Developing web services with Rust at Fairy Devices, Inc. 12-year of experience in developing distributed storage. (Erlang, Java) フリーランスのソフトウェアエンジニア。 フェアリーデバイセズ株式会社にてRustを使ったWebサービスの開発に携わっている。 12年間におよぶ分散ストレージの開発経験を持つ。（Erlang、Java） Tatsuya Kawano @tatsuya6502
3. Who am I? Grew up in Tokyo, Japan. Lived in New York, USA for 7 years. (Graphic design major at a school) Lives in Shanghai, China since 2013. 東京育ち。 ニューヨークに7年間在住。（⼤学でグラフィックデザインを専攻） 2013年より上海に在住。 Tatsuya Kawano @tatsuya6502
4. Coauthor, published in 2019 Coauthor, published in 2012
5. Free stock photos | kaboompics.com iStock | Licensed to @tatsuya6502 Cache basics キャッシュの基本 並⾏プログラミングと パフォーマンス Concurrent prog. and performance 開発で遭遇した課題 Challenges 1 2 3
6. What are caches? A cache stores a portion of the data retrieved from a slower media on a faster media. Many kinds: CPU caches (data, instructions), OS caches (pages), in-application 
 in-memory cache, shared/distributed caching server… Moka cache is an in-memory cache. It is like a HashMap with a capacity limit. 低速のメディアから取得したデータの⼀部を、⾼速のメディアに保存するためのしくみ。 いろいろな種類がある：CPUキャッシュ、OSのページキャッシュ、アプリ内の インメモリキャッシュ、共有／分散キャッシングサーバー、など。 Mokaキャッシュはインメモリキャッシュの⼀種。容量制限付きのHashMapのようなもの。 Time and space trade-o ff to improve performance.
7. Example Web API service Webサービスの例 指定したGitHubリポジトリーのスター数を取得するREST APIを提供する。 A web service with REST API to get GitHub stars for given repository. Axum / Tokio Octocrab rust-lang / rust API $ curl ⭐ 86,200 rust-lang / rust ⭐ 86,200 Our Wed API Service
11. Took about 0.9 seconds Let’s cache the data returned from GitHub API. GitHubが返したデータをキャッシュしよう。 約0.9秒かかった
12. Avoid to access GitHub when possible Keep the results in memory with the repository names as the keys. リポジトリー名をキーにして、過去の結果をメモリー上に置いておく。 Let’s add an in-memory cache. Our Cache rust-lang / rust API $ curl Repository ⭐ rust-lang / rust 86,200 tokio-rs / axum 12,800 moka-rs / moka 1,024 ⭐ 86,200 Our Wed API Service
13. Introducing Moka cache Inspired by the Ca ff eine cache library for Java. 1,000+ GitHub stars. 840,000+ downloads in last 90 days. (Oct 2023) JavaのCa ff eineキャッシュライブラリーを参考にしている。 GitHubスターは1,000個以上。 過去90⽇間のダウンロード回数は84万回以上。 （2023年10⽉調べ） moka-rs / moka A fast and concurrent cache library for Rust iStock Licensed to @tatsuya6502
14. Introducing Moka cache Used in backend services of Crates.io and Sentry.io. Some people use it in home routers. (Arm, MIPS, etc.) MIT、および、Apache-2ライセンスの下、オープンソース。 Crates.ioやSentry.ioのバックエンドサービスで使⽤されている。 Ոఉ༻ϧʔλʔ಺Ͱ࢖ͬͯΔਓ΋ʢArmɺMIPSͳͲʣ Named after the moka pot, a stove-top co ff ee maker. Open sourced under MIT and Apache-2 licenses iStock Licensed to @tatsuya6502 moka-rs / moka
15. Use Moka’s Cache implementation moka::future::Cache or moka::sync::Cache
17. Much faster 🚀 Before ~0.9 secs (929,062 μs) → After 20 μs ~46,400 times faster.
18. Benchmark Ca ff eine simulator. Ran cache trace collected from a production search engine. (ARC-S3) ~58% ~35% B A TinyLFU 
 (Moka) LRU theoretical 
 upper bound ~75% ~42% ~13% ~60% ben-manes / caffeine https://github.com/moka-rs/moka/wiki
19. TinyLFU Policy (used by Moka) Deny admission to infrequently used entries. LRUキューの⼿前にLFUフィルターを設置し、使⽤頻度の低いエントリーの⼊場を拒否する。 A LFU (Least Frequently Used) fi lter in front of the LRU queue. https://github.com/moka-rs/moka/wiki
20. Concurrent programming
 and performance 並⾏プログラミングとパフォーマンス Free stock photos | kaboompics.com moka-rs / moka
21. When lock contentions occur, thread utilizations will be reduced, leading to performance degradation. ロック競合が起こるとスレッドの稼働率が下がり、パフォーマンスの低下につながる。 Lock contentions T1 T2 T3 r t1 t3 t4 t5 t6 t7 t2 acquire the lock release the lock blocked
22. Avoid lock contentions by batch applications Instead of making each thread to apply their changes to the shared resource r, use a channel ch to store recordings of cache accesses, and only apply them together after a certain amount of items has accumulated. 各スレッドが共有リソース r に変更を適⽤する代わりに、チャネル ch を使ってキャッシュアクセスの 
 記録を保存し、ある程度、溜まってから⼀括して適⽤する。 T1 T2 T3 ch t1 t3 t4 t5 t6 t7 t2 send receive r update
23. Lock-free Lock-free is a class of data structures and algorithms that performs operations with using exclusive locks. Updates are made atomically using instructions such as Compare and Swap. 排他ロックを⽤いずに処理を⾏うデータ構造とアルゴリズム。 Compare and Swap処理などを⽤いてアトミックにデータ更新を⾏う。
24. Lock-free The concurrent hash table inside Moka employs it. (It is a fork of cht crate) cht and channel: lock-free → short, predictable latency other data structures: mutex with batch application → high throughputs Moka内部の並⾏ハッシュテーブルで採⽤されている（chtクレートのフォーク） chtとチャネル: ロックフリー → レイテンシ（応答時間）が短く、予測可能 他のデータ構造: mutexと⼀括適⽤ → ⾼スループット
25. Async runtime and traditional locks There are two kind of lock implementations: traditional non-futures-aware locks, and futures-aware locks. Avoid to use traditional locks when: Acquiring the lock may take long time. → Will block the async executor. Or, hold the lock across an .await. → Can deadlock the async executor. ロック実装には、伝統的なfuture未対応ロックと、future対応ロックの2種類がある。 以下のような場合は、伝統的なロックの使⽤を避けるべき。 ロックの取得に時間がかかる。→ ⾮同期エクゼキュータをブロックしてしまう。 または、.awaitにまたがってロックを保持する。→ ⾮同期エクゼキュータがデッドロックする可能性がある。
26. Challenges moka-rs / moka Free stock photos | kaboompics.com 開発で遭遇した課題
27. Pitfalls in pass-in-value in async fn
28. Resolved by using Box::pin(fut)
29. For more details See @Swatinem’s blog post, and/or his presentation at EuroRust 2023
 about Rust compiler. https://swatinem.de/blog/future-size/
30. Async cancellations are hard! Future can be canceled at an .await point. https://blog.yoshuawuyts.com/async-cancellation-1
31. Handling async cancels Clean up resources using the Drop::drop. Spawn the future as a separate async task. (tokio::task::spawn, etc.) Drop::dropΛ࢖ͬͯϦιʔεͷޙย෇͚Λ͢Δɻ Futureを独⽴した⾮同期タスクとしてspawnする。（tokio::task::spawn、など）
32. Moka cannot spawn a Future In Moka, cleaning up does not work in some cases. But it cannot spawn a Future as it has no dependency to any async runtime. Used future_util::future::Shared, and make drop method to save it to an unbound channel, so that it can retry later.
 Mokaでは後⽚付けではうまく処理できないケースがある。 しかし、⾮同期ランタイムに依存していないので、Futureをspawnできない。 future_util::future::Sharedを使い、dropメソッドでサイズ制限なしのチャネルに保存す る。あとでリトライする。
35. Be aware that retrying can be cancelled to! リトライ⾃体がキャンセルされるこ ともあるので注意！
36. Looking ahead 今後の展望 moka-rs / moka Free stock photos | kaboompics.com
37. Roadmap and_compute API. Restore from a snapshot. Upgrade TinyLFU to Window TinyLFU. Wasm support? Reduce the memory overhead.
38. Give Moka a try! https://github.com/moka-rs/moka Ask questions at GitHub Discussions. ぜひMokaを使ってみてください。 ⽇本語による質問は、Rust Jp 
 コミュニティーのチャットまで。 
 https://rust-lang-jp.zulipchat.com Free stock photos | kaboompics.com