並行キャッシュライブラリー「Moka」を作ったのでWebサービスを高速化するサンプルを使って説明します

これは Rust Advent Calender の23日目の記事です。私が個人開発しているMokaという並行インメモリーキャッシュライブラリーがあるのですが、これを使うと様々なRustプログラムを高速化できるはずです。この記事では簡単なプログラムを通して、Mokaの使いかたと期待される効果について説明します。具体的にはActix Webで作成したREST APIサービスにMokaを追加することで、レスポンスタイムを短縮します。

題材としてWebサービスを選びましたが、ここで説明することはそれに限らず、様々なRustプログラムに応用できるはずです。

MokaはMITライセンスとApache-2.0ライセンスの下に公開されている、オープソースソフトウェアです。

並行インメモリーキャッシュとは？

並行インメモリーキャッシュとは何でしょうか？ 3つの言葉「キャッシュ」「インメモリー」「並行性」について順に説明します。

キャッシュ

キャッシュとはアクセス数が上位のデーターを高速な記憶装置に一時的にメモしておく仕組みのことです。一般的に、短時間にアクセスするデーターには偏りがあるといわれていて、80:20の法則のようにアクセス数上位20%のものが全体の80%のアクセスを占めたりします。そのため、たとえばRDBMSにあるデーターの全部はメモリーに入らなくても、アクセス数上位のデーターをうまく選んでメモリーに載せればパフォーマンスが上がるはずです。

Mokaは容量制限のあるハッシュマップのようなものです。ハッシュマップとの違いは以下のとおりです。

• 格納する要素（エントリー）の数に上限を設定できる。限られたメモリー領域を有効に使えます
• エントリーに有効期限を設定できる。元のデーターが更新されることがあるので、メモしたデーターが古くなったら自動的に捨ててくれます

エントリーを新たに挿入するときに十分なスペースがなければ、容量を増やすのではなく、既存のエントリーを削除したり、エントリーの挿入を中止したりします。このときにどのエントリーを削除するのか、それとも挿入を中止するのか、それらの選択がパフォーマンスに直結します。

詳しくはこの記事の 最後の方 で説明しますが、Mokaは、Javaで実装されたCaffeine（カフェイン）という有名なキャッシュライブラリーの設計を大いに参考にしており、パフォーマンスを高めるためのさまざまな工夫を備えています。

インメモリー

インメモリーなキャッシュは文字どおりメモ化したデーターをメモリー内に置きます。Mokaは厳密には「ローカル」のインメモリーキャッシュなので、アプリケーションのメモリー空間に同居します。この点では標準ライブラリーのHashMapと同じです。

他の種類のキャッシュには、memcachedに代表されるリモートにあるインメモリーキャッシュや、HTTPプロキシーサーバーのようなメモリーとファイルシステムの両方を使ってメモ化するキャッシュなどもあります。

並行性

並行性（concurrency）とは、2つ以上のタスク（OSスレッド、futureなど）が同時に計算を進めている状態を表す言葉です。

キャッシュについて「並行」といったときは、（私の考えでは）以下の2つを満たすものを指します。

1. 2つ以上のタスクから同時にアクセスされてもデーターが壊れない（データー競合を防ぐ仕組みがある）
2. 同時にアクセスしているタスクの並行性を極力阻害しないための工夫がある

悪い例ですが、Rustでマルチスレッドのプログラムを書いて、スレッド間で標準ライブラリーのHashMapを共有することについて考えます。その場合、素のHashMapだとデーター競合が起こるので共有できません（コンパイルエラーになります）　そのためMutexなどのロックで包むことで、ある時点でただ1つのタスクだけがHashMapにアクセスできるようにします。

この状態では1.は満たせていますが、2.は満たせていません。

たとえばWebアプリケーションフレームワークは複数のクライアントから同時にリクエストが来たときに、それらを並行して処理します。もし全てのリクエストハンドラーが共通してアクセスするデーターをMutex<HashMap<K, V>>に入れていたらどうなるでしょうか？　2.が満たせてないためにHashMapへのアクセスがボトルネックとなり、Webサービス全体のレスポンスが悪化するでしょう。

Mokaは1.と2.の両方を満たしています。キーバリューを格納するハッシュマップにはロックフリーなデーター構造を使用しており、ほぼウェイトフリーで（待ち時間なく）読み書きできます。またエントリーのアクセス数を追跡する内部データー構造についてはMutexで守っていますが、キャッシュの読み書きの履歴をバックグラウンドのスレッドで一括して適用することで、ロックに関するオーバーヘッドを軽減しています。

これらの工夫により、Webアプリケーションなどでも並行性が阻害されることなく、安心してMokaを活用できます。

採用事例

Mokaの最初のバージョンをCrates.ioに公開したのは2020年10月でした。その後しばらく開発が中断したものの、今年2月にはそれなりに使えるようになりました。その後もユーザーの要望などを聞きながら開発を進めていたところ、その甲斐があったか、最近になって本番サービスでの利用事例が出てきました。

代表的なものを紹介します。

Crates.ioのAPIサービス

Crates.ioはRustaceanなら誰もがお世話になっているであろう公式クレートレジストリーです。そのCrates.ioのWeb APIサービスでMokaが採用されました。2021年の11月10日前後から本番環境で動いています。downloadエンドポイントという非常にアクセスの多いAPIエンドポイントの処理で、PostgreSQLの負荷を減らすために使われています。

11月13日

With rust-lang/crates.io#3999 we've started using moka for crates.io and it appears to be working very well. We're seeing cache hit rates of ~85% for the high-traffic download endpoint now.

rust-lang/crates.io#3999 により、私たちはcrates.ioでmokaを使い始めました。非常にうまくいっているように見えます。現時点では高トラフィックなdownloadエンドポイントについて約85%のキャッシュヒット率を観測しています。

Thank you for working on this! :)
（mokaに）取り組んでいただきありがとうございました！

downloadエンドポイントはCargoがクレートをダウンロードするときにアクセスされます。以下の記事によると、Crates.ioのサービス開始（2015年ごろ？）以来のクレートダウンロード回数は、現在までに100億回を越えているとのことです。

Adios Pagers: New Developments on Crates.io
ポケベルさんさようなら¹：Crates.ioにおける新規開発

その記事ではRustファウンデーションが資金を提供したことで、Crates.ioサービスに障害が起きたときの一次対応をある企業に移管できたこと。それによって、いままで当番制で障害対応にあたっていたボランティア開発者たちの時間に余裕ができ、将来に向けた改良に取り組めるようになったことなどが報告されています。

Crates.ioがMokaの利用を開始したときのGitHub PRは10月にオープンされており、この記事と時期が一致します。

aliyundrive-webdav / アリクラウドドライブ WebDAV サービス

aliyundrive-webdavはWebDAVゲートウェイと呼ばれる種類のサーバーソフトウェアです。これを使うと中国のアリババクラウド（中国名：アリクラウド / 阿里云）が提供するクラウドストレージに置かれたファイルに、WebDAVプロトコルでアクセスできるようになります。

主な用途は以下のようなものです。

• クラウドストレージに置かれたムービーファイルをテレビで視聴する。（このソフトの他にApple TVなどの機器も必要なようです）
• NASに格納しているファイルをクラウドストレージにバックアップする

Mokaはクラウド上にあるファイルのメタデータをキャッシュするために使われています。

面白いのは、このソフトウェアの主なデプロイ先がPCなどではなく、家庭用Wi-Fiルーター²やNASなどの組込みLinux機器、そして、Raspberry Piなどのシングルボードコンピューター（SBC）で制作したルーターだということです。

Buffaroなどの市販のWi-FiルーターのファームウェアをOpenWrtで書き換えると高機能なルーターに生まれ変わります（何かあっても自己責任ですが）　そこにこのソフトのOpenWrt向けパッケージをインストールし、Webベースの管理画面から設定すると、アリクラウドへのWebDAVゲートウェイ機能が追加されるわけです。またQNAPなどの家庭・小規模オフィス用NASにインストールしているユーザーもいるようです。

aliyundrive-webdavのGitHubスター数は開発開始から4ヶ月経たないうちに1000を越えました。また、ある程度のパワーがあるSBCではDockerで動かしている人も多いようで、Dockerイメージのダウンロード数は6万回を越えてます。

こういう数字を見て思ったのですが、aliyundrive-webdavは中国国内で数百台（あるいはもっと多く）のルーターやSBCで稼働しているのかもしれません。

サンプルプログラム：Webサービスの高速化

ベースとなるプログラム

ここからはサンプルプログラムを紹介していきます。

このプログラムはActix Webで書かれたWebサービスです。REST APIによるエンドポイントURLが1つだけあり、クライアントはそれを使って指定したGitHubリポジトリーのスター数を取得できます。

たとえば以下のようにすると rust-lang/rust リポジトリーのスター数などの情報がJSON形式で返されます。

$ curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq
{
  "owner": "rust-lang",                         # リポジトリーのオーナー
  "repo": "rust",                               # リポジトリー名
  "stars": 61563,                               # スター数
  "timestamp": "2021-12-20T21:48:05.458+08:00"  # スター数を取得した時刻
}

使用したクレートは以下のとおりです。

Cargo.toml

[package]
...
edition = "2021"

[dependencies]
actix-web = "=4.0.0-beta.15"  # Webアプリケーションフレームワーク
anyhow = "1.0.51"             # アドホックなエラー処理
chrono = "0.4.19"             # 現在時刻の取得と文字列へのフォーマット
octocrab = "0.15.2"           # GitHub APIクライアント
serde = "1.0.132"             # HTTPレスポンスボディのシリアライズ（JSON化）

このサービスのやることは単純です。

1. クライアントからリクエストが来たら、URLからオーナー名やリポジトリー名を取り出す
2. Octocrabを使ってGitHub APIサービスからリポジトリーの情報を取得する
3. スター数などの情報をJSON化してクライアントに返す

これだけの機能ですとWebサービスではなくて、コマンドラインツールにすればいいように思うかもしれません。たしかにそうですが、今回はWebサービスの例を示したかったことと、コードをできるだけ簡単にしたかったために、あえてこうしています。現実的なWebサービスでは、2.のところは同一LAN上にあるRDBMSに対するクエリーやマイクロサービスに対するRPCかもしれません。

ソースコードは以下のとおりです。

src/main.rs

use actix_web::{web, App, HttpRequest, HttpServer, Responder};
use chrono::{Local, SecondsFormat};
use serde::Serialize;

#[actix_web::main]
async fn main() -> std::io::Result<()> {
    // エンドポイントを定義する。HTTP GETメソッドのときにstarsハンドラーで処理する
    HttpServer::new(|| App::new().route("/{owner}/{repo_name}/stars", web::get().to(stars)))
        .bind("127.0.0.1:8080")?
        .run()
        .await
}

async fn stars(req: HttpRequest) -> actix_web::Result<impl Responder> {
    // リクエストURLからリポジトリーオーナー名とリポジトリー名を抜き出す
    let params = req.match_info();
    let owner = params.get("owner").unwrap().to_string();
    let repo_name = params.get("repo_name").unwrap().to_string();

    // GitHub APIにアクセスしてスター数を得る
    let stars = get_stars(owner, repo_name)
        .await
        .map_err(actix_web::error::ErrorInternalServerError)?;

    // JSON形式でレスポンスを返す
    Ok(web::Json(stars))
}

// レスポンスで返す情報の定義
#[derive(Serialize)]
struct Stars {
    // リポジトリーオーナー
    owner: String,
    // リポジトリー名
    repo: String,
    // スターの数
    stars: u32,
    // 情報を取得した時刻（RFC3339形式）
    timestamp: String,
}

// GitHub APIにアクセスしてスター数を得る
async fn get_stars(owner: String, repo: String) -> anyhow::Result<Stars> {
    // 指定したリポジトリーの情報を得る
    let repo_info = octocrab::instance().repos(&owner, &repo).get().await?;
    // 現在時刻をRFC3339形式で取得する
    let timestamp = Local::now().to_rfc3339_opts(SecondsFormat::Millis, true);
    Ok(Stars {
        owner,
        repo,
        // リポジトリー情報からスター数を抜き出す。Noneのときは0をセットする
        stars: repo_info.stargazers_count.unwrap_or_default(),
        timestamp,
    })
}

Mokaを使ってレスポンスタイムを短縮

ではMokaを使ってこのサービスを改良しましょう。いまは以下のようになっているのでした。

1. URLからオーナー名やリポジトリー名を取り出す
2. GitHub APIサービスからリポジトリーの情報を取得する
3. スター数などの情報をJSON化して返す

この中で時間のかかる処理は2.になります。この処理を毎回行う必要があるのかというと、そうでもなさそうです。そもそもスターの数が頻繁に増減することはあまりないでしょうし、もし情報が多少古くて現在とスター数が異なっていても多くの場合で問題にならないでしょう。

こういうときはキャッシュの出番です。GitHub APIサービスから一度取得した情報（Stars）を一定期間キャッシュすることで、2.の処理をできるだけ省略し、レスポンスタイムの高速化を目指しましょう。

またこうすることで、GitHub APIサービスの負荷も軽減できますし、API呼び出し回数の制限を回避することにもつながります。（なお、回数制限はリクエストに認証トークンを付けることで緩和できます。もちろんOctocrabはそれに対応しています）

ではプログラムを修正しましょう。依存クレートにMokaを追加します。

Cargo.toml

# Mokaのasync/awaitサポートを有効にするためにfutureフィーチャーを指定する
moka = { version = "0.6.2", features = ["future"] }

Mokaの現在のバージョンには、以下のキャッシュが定義されています。

キャッシュ	機能
future::Cache	async/awaitとマルチスレッドの両方に対応したキャッシュ
sync::Cache	マルチスレッドに対応したキャッシュ
sync::SegmentedCache	マルチスレッドでスレッド数が特に多いときに性能劣化を抑えられるキャッシュ
unsync::Cache	async/awaitとマルチスレッドのどちらにも対応していないキャッシュ

今回はasync/awaitに対応したmoka::future::Cacheを使います。

Actix Webのリクエストハンドラーからキャッシュにアクセスできるように、アプリケーションデーターとなる構造体AppDataを定義します。キャッシュのキーはオーナー名とリポジトリー名のタプル (String, String)、バリューはStars構造体にします。

src/main.rs

use moka::future::{Cache, CacheBuilder};

// アプリケーションデーター
struct AppData {
    // キーはオーナー名とリポジトリー名のタプル、バリューはStars構造体
    star_cache: Cache<(String, String), Stars>,
}

future::Cacheは並行キャッシュなので、Mutexなどで守る必要はありません。また内部可変性（interior mutability）を持つのでmutを付けずにキャッシュの内容を変更できます。

Webサービスの起動直前にキャッシュを作成します。動作を確認しやすくするために、エントリーの有効期限（Time to Live）は短めの30秒に設定しました。

src/main.rs

#[actix_web::main]
async fn main() -> std::io::Result<()> {
    // キャッシュを作成する。エントリー数の上限は1000個
    let star_cache = CacheBuilder::new(1000)
        // エントリーの有効期限は30秒
        .time_to_live(Duration::from_secs(30))
        .build();
    let data = web::Data::new(AppData { star_cache });

    HttpServer::new(move || {
        App::new()
            .app_data(data.clone())
            .route("/{owner}/{repo_name}/stars", web::get().to(stars))
    })
    .bind("127.0.0.1:8080")?
    .run()
    .await
}

data.clone()のところですが、actix_wed::web::Dataは内部でstd::sync::Arcを使用しており、cloneするとAppDataが複製されるのでなく、単に共有するポインターが作られるだけです。なお、Mokaのfuture/sync Cacheも内部でArcを使用しており、cloneするとキャッシュが複製されるのではなく、共有されます。

starsハンドラーを修正して、以下を実装します。

• キャッシュヒットしたら、そのStarsを返す
• キャッシュミスしたら、GitHub APIサービスから情報を取得してStarsを作成し、キャッシュに挿入してから返す

このとおりの動作をするget_or_try_insert_withというメソッドがありますので、これを使います。

src/main.rs

// AppDataを使うために2つ目の引数を追加する
async fn stars(req: HttpRequest, data: web::Data<AppData>) -> actix_web::Result<impl Responder> {
    let params = req.match_info();
    let owner = params.get("owner").unwrap().to_string();
    let repo_name = params.get("repo_name").unwrap().to_string();

    // Cache::get_or_try_insert_withメソッドを使う
    let stars = data
        .star_cache
        .get_or_try_insert_with(
            (owner.clone(), repo_name.clone()), // キー
            get_stars(owner, repo_name),        // バリューを得るためのfuture
        )
        .await
        .map_err(actix_web::error::ErrorInternalServerError)?;

    Ok(web::Json(stars))
}

このメソッドは引数として以下をとります。

• キー
• バリューを得るためのfuture

もしキャッシュがヒットしたら対応するバリューのcloneを返し、キャッシュミスしたらfutureを解決（実行）することでバリューを得ます。なお、キャッシュへの挿入が行われるのは、futureがOk(バリュー)を返したときだけです。Err(エラー)のときは、挿入されずErr(Arc(エラー))が返ります。

実行しましょう。

$ time (curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq)
{
  "owner": "rust-lang",
  "repo": "rust",
  "stars": 61564,
  "timestamp": "2021-12-20T21:52:45.651+08:00"
}
( curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq; )  0.04s user 0.01s system 7% cpu 0.655 total

$ time (curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq)
{
  "owner": "rust-lang",
  "repo": "rust",
  "stars": 61564,
  "timestamp": "2021-12-20T21:52:45.651+08:00"  # 前回と同じ時刻（キャッシュヒット）
}
( curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq; )  0.04s user 0.01s system 96% cpu 0.049 total

$ time (curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq) 
{
  "owner": "rust-lang",
  "repo": "rust",
  "stars": 61564,
  "timestamp": "2021-12-20T21:52:45.651+08:00"  # キャッシュヒット
}
( curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq; )  0.04s user 0.01s system 95% cpu 0.045 total

$ time (curl -s http://127.0.0.1:8080/actix/actix-web/stars | jq)
{
  "owner": "actix",
  "repo": "actix-web",                          # 別のリポジトリー
  "stars": 12735,
  "timestamp": "2021-12-20T21:52:56.692+08:00"  # キャッシュミス
}
( curl -s http://127.0.0.1:8080/actix/actix-web/stars | jq; )  0.03s user 0.01s system 7% cpu 0.576 total

$ time (curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq) 
{
  "owner": "rust-lang",                         # 元のリポジトリー
  "repo": "rust",
  "stars": 61564,
  "timestamp": "2021-12-20T21:52:45.651+08:00"  # キャッシュヒット
}
( curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq; )  0.04s user 0.01s system 95% cpu 0.046 total

$ time (curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq)
{
  "owner": "rust-lang",                         # 元のリポジトリー
  "repo": "rust",
  "stars": 61564,
  "timestamp": "2021-12-20T21:53:19.122+08:00"  # キャッシュミス（30秒の期限切れになった）
}
( curl -s http://127.0.0.1:8080/rust-lang/rust/stars | jq; )  0.04s user 0.01s system 5% cpu 0.869 total

うまく動きました。同じリポジトリーのスター数を繰り返してリクエストすると、初回から30秒経たないうちはtimestampが同じJSONが返り、30秒以上経つとtimestampが変わります。

レスポンスタイムも改善されました。

キャッシュミス/ヒット	レスポンスタイム
ミス	0.576秒から0.869秒
ヒット	0.045秒から0.049秒

アトミックな操作

get_or_try_insert_withメソッドは、内部的には最大でget、futureの解決、insertの3段階の処理を行いますが、外から見ると全体で1つのアトミックな操作になっています。

たとえば、サンプルのWebサービスが、同じリポジトリーに対する要求を2つのクライアントから同時に受信したとします。すると同じキーに対するget_or_try_insert_withが同時に並行して実行されることになります。どちらも内部のgetでキャッシュミスしますが、その後のfutureの解決とinsertはただ1度だけ行われます。そしてinsertできた直後に両方のメソッドからバリューが返ります。

この仕組みにより初期化が重いバリューでも無駄な初期化をしないですみます。

なお、複数タスクからの同時実行をデモするコードと実行結果を ドキュメントに載せています ので、興味があったら見てみてください。

その他の主要なキャッシュ操作

その他の主要なキャッシュ操作を以下に示します。

メソッド	操作
get_or_insert_with	get_or_try_insert_withのバリエーション。Futureを解決して得られた値を常に挿入する
get	キーが存在するならSome(バリューのclone)を返す。さもなければNoneを返す
insert	キーバリューを挿入する。すでに存在するなら上書きする
invalidate	キーバリューを無効化する。HashMapのremoveに似ているがバリューは返さない
invalidate_all	全てのキーバリューを無効化する。無効化はバックグラウンドで行われる
invalidate_entries_if	キャッシュ内の全エントリーをスキャンして、引数に与えた述語がtrueを返したエントリーを無効化する。述語とはキーバリューの参照をとり、booleanを返すクロージャーのこと。スキャンはバックグラウンドで行われる

ヒット率を高める工夫（Caffeineを参考に）

この記事の冒頭で述べたことについて、もう少し詳しく説明します。

Mokaは、Javaで実装されたCaffeine（カフェイン）という有名なキャッシュライブラリーの設計を大いに参考にしており、パフォーマンスを高めるためのさまざまな工夫を備えています

キャッシュは低速な記憶装置から得たデーターを高速な記憶装置に一時的にメモする仕組みです。Mokaはエントリーを新たに挿入するときに十分なスペースがなければ、容量を増やすのではなく、既存のエントリーを削除したり、エントリーの挿入を中止したりします。このときにどのエントリーを削除するのか、それとも挿入を中止するのか、それらの選択がキャッシュのヒット率に直結し、パフォーマンスに影響します。

当然ながらヒット率が高い方がアプリケーションのパフォーマンスが向上します。しかもその特性はリニア（直線）ではありません。

出典：Systems Performance: Enterprise and the Cloud, 2nd Edition (2020)、Brendan Gregg著

この図はキャッシュのヒット率（横軸）とパフォーマンス（縦軸）の関係を示したものです。

ヒット率が98%と99%の間の性能差は、10%と11%間の性能差よりもずっと大きくなっています。これはヒットとミスの速度差によるものです。そして両者の速度差が大きくなればなるほどグラフが急勾配になります。ヒット率1%の差が大きな違いを生み出す可能性があるので、キャッシュのヒット率を高めるための仕組みについては深く研究されています。

ヒット率を高めるためには、近い将来アクセスされそうなエントリーがどれになるのかを上手に予想しなければなりません。

Mokaは2つの仮定を用いてます。いずれも Caffeine の設計を参考にしています。

1. 時間局所性：最近アクセスされたエントリーは、今後、再びアクセスされる可能性が高いだろう
2. 人気度：1.よりも少し長い期間を見て、アクセス回数が多いエントリーは、今後、再びアクセスされる可能性が高いだろう

1.については、最近アクセスされたエントリーをできるだけキャッシュに残すようにします（eviction/退場ポリシー）　最も過去に使用されたエントリーを最初に退場させることから、一般的にLeast Recently Used（LRU）ポリシーと呼ばれます。

2.については、アクセス回数が少ないエントリーをできるだけキャッシュに入れないようにします（admission/入場ポリシー）　使用頻度が低いエントリーの入場を拒否することから、一般的にLeast Frequently Used（LFU）ポリシーと呼ばれます。

キャッシュ内にあるかどうかに関わらず、個々のキーのアクセス履歴を追跡することで、これらの選択を可能にしています。

Moka/Caffeine共にLRUポリシーは双方向連結リストで管理しています。このデーター構造を使いつつ並行性を高めようとすると実装が複雑になる傾向があります。他のキャッシュでは簡易的なLRUを用いているものも多くあり、たとえばランダムに選択した複数エントリーの中からLRUを探したり、ハッシュマップ内の小区画内でLRUを探したりする手法があります。しかしMokaではヒット率を少しでも上げるため、また、今後実装予定の「世代別LRU」を実現するため、双方向連結リストを採用しています。

Moka/Caffeine共にLFUポリシーは count-min sketch という確率的データー構造を用いてます。これは何億という数のキーの使用回数を、非常に小さなメモリーサイズで「見積もれる」データー構造です。なぜ見積もるのかというと、愚直にカウントしようとするとキーの数によっては膨大なメモリーが必要になるからです。

count-min sketchは個々のキーの使用回数を個別に追跡するのではなく、確率に関する数学的手法を用いることで、コンパクトなデーター構造でありながら使用回数を予測できます。Moka/Caffeineのcount-min sketchは時間軸による重み付け（最近のものを重視）するために、カウントを半減させる機能が追加されています。

現時点のキャッシュポリシー（TinyLFU）

Mokaの現時点（v0.6.2）の入退場ポリシーの構成です。これは初期のCaffeineがとっていた構成（TinyLFU/とても小さなLFU）とほぼ同じです。

評価の流れ

1. Moka内部の並行ハッシュマップに新規に挿入されたエントリーは「仮入場」としてあつかわれ、その書き込み記録（ログ）が書き込みバッファーに入る
2. 書き込みバッファー上のログは通常は0.0秒から0.3秒後に処理される。count-min sketchによるLFUフィルターにかけられ、その使用頻度が、LRUの右端のエントリー（退場候補）の使用頻度と比較される
   • 新しいエントリーの使用頻度の方が高いなら、LRUキューに「入場」する
   • そうでなければ「退場」する（キャッシュから削除される）
3. 入場に成功したエントリーはLRUキューの中を移動していきます
   • 他のエントリーが入場するたびに右に向かって動いていく
   • 使われる（getされる）とLRUの左端に戻される
4. そのエントリーはやがてLRUの右端にたどり着く。退場候補となり2.の使用頻度比較で負ければ「退場」する

2.のところ、つまり、挿入後すぐに退場する可能性があることに注意してください。

将来予定しているキャッシュポリシー（W-TinyLFU）

Mokaの将来の入退場ポリシーの構成はこうなる予定です。現在のCaffeineがとっている構成（W-TinyLFU）とほぼ同じです。

変更点

• 「仮入場」はなくなり、すぐに「入場」する。（厳密には書き込みバッファーと仮入場はなくならないが、すぐに入場するので図では省略している）
• 適応性LRUウィンドウは、キャッシュのヒット率によって自動的にサイズが変化する。初期値はキャッシュ容量の1%
  • 時間局所性が高いアクセスパターンのときはウィンドウが大きい方がヒット率が上がる
  • そうでないとき（人気度の影響が大きいアクセスパターンのとき）はウィンドウが小さい方がヒット率が上がる
• 世代別LRU
  • エントリーは、まず試用エリアの左端に入る
  • 試用エリアにあるうちに1度でもアクセスがあると昇格され、保護エリアの左端に入る
  • 保護エリアの右端から落ちたエントリーは降格され、試用エリアの左端からやり直す

適応性ウィンドウを設けることでアクセスパターンに応じてポリシーの特性が自動調整されるようになります。また、世代別LRUにより退場させるエントリーの選択が、より丁寧に行われるようになります。

アンチパターン

MokaはHashMapに似ていますが、違いもあります。使用時に注意すべき点について説明します。

Cloneが重いバリューをそのまま入れてしまう

これはREADMEにも書いていますが、future/syncキャッシュでは、getなどがバリューの参照ではなくcloneを作って返します。これは並行性を優先しているために参照を返せないからです。キャッシュのエントリーはいつ期限切れになって削除されたり、別のスレッドからの挿入によって置き換えられたりするかわかりません。そのような生存期間が予測できないバリューについては参照を返すことはできません。

バリューによってはcloneを作成するオーバーヘッドが無視できないものもあります。またCloneトレイトを実装していないものもあります。そのようなバリューをキャッシュに入れるときはstd::sync::Arcで包んでから入れてください。

キャッシュミスを想定していない

Mokaでは挿入したばかりのキーバリューがすぐ（いまのバージョンですと0.3秒以内）に削除されることがありますので注意してください。

キャッシュに挿入したバリューをプログラムのあちこちで使いたいときには、以下のどちらかを行ってください。

• get_or_insert_withメソッドなどを使って、キーバリューが存在しないときにはバリューを再度初期化する
• キャッシュから取得したバリューをプログラム内で持ち回る（関数の引数にしたり、構造体のフィールドとメソッドを使ったりする）

W-TinyLFUの導入後は起こりにくくなるはずですが、絶対に起こらないことは保証できません。

まとめ

Mokaの使いかたと期待される効果について、サンプルプログラムを使って説明しました。またキャッシュのヒット率を高める工夫についても説明しました。

もしMokaに興味を持っていただいたなら、ぜひ使ってみてください。

そして質問や要望などありましたら、Slack rust-jpグループの#moka日記チャネルなどでお知らせください（登録URL）

おまけ：名前の由来は？

名前の由来は Mokaポット という種類のコーヒーメーカーです。

出典：Signor Bialetti goes Songkhla / jfantenb

Mokaポットは1933年にイタリアで発明された器具で、ポット下部に密閉されたタンクがあり、そのすぐ上に細挽きに挽いたコーヒー豆を入れるバスケットがあります。タンクに水を入れて直火などで熱することで蒸気を発生させ、その圧力がかかったお湯をコーヒー豆に通し、一気に抽出します。

イタリアのビアレッティ社が「Moka Express」の名称で発売したのがはじまりで、その名前はコーヒ産地のイエメンの都市Mochaから来ています。それ以来、同じ仕組みのコーヒーメーカーが他社からも発売されましたが、それらを総称してMokaポットと呼ぶようになりました。

自宅で手軽にエスプレッソ「風」の濃いコーヒーが淹れられるため、イタリアの多くの家庭にMokaポットがあるといわれています。

Mokaキャッシュという名前には以下のような意味や願いを込めています。

• Java Caffeineキャッシュの系統であること
• Rustで書かれていること。（Mokaポットの多くはアルミニウム合金かステンレス合金でできてます。錆びないけど金属つながりです）
• 高速であること。（エスプレッソの意味は「高速」「急行」）
• 誰でも簡単に使えること。そして、多くの場所で使われること。（Mokaポットのように）

1. 記事のタイトルになっているポケベル（pager）は1990年代のまだ携帯電話が普及してなかった頃に流行した無線呼び出し機器です。ポケベル固有の電話番号に電話すると、電波で合図を送ることができました。現在のフードコートなどにある、料理ができたときにピーピー鳴って教えてくれる小型機器の原型のようなものです。その記事ではポケベルは「SMSによる夜間などの緊急呼び出し」の意味で使われています。 ↩

2. 安価な市販ルーターの中には32ビットのMIPSやARMv5TEアーキテクチャーを採用した非力なSoCが入っている機種も多くあります。それらには必要なマシン語命令がないためstd::sync::atomic::AtomicU64が存在しません。Mokaとそれが依存してるQuantaはAtomicU64を使用しているので、これらのプラットフォームをサポートするために修正が必要でした。そういった苦労？もありましたが、こうして自分の書いたコードが想像もしなかったところで動いているのを見られたり、見ず知らずの人と協力し合いながら何かを作り上げていけるのは楽しいものです。 ↩