Skip to content

Instantly share code, notes, and snippets.

@kubo39

kubo39/sieve-eviction-cache.md Secret

Last active May 21, 2024 04:11
Show Gist options
  • Save kubo39/dcb946262bceb320ba298292d78fcc92 to your computer and use it in GitHub Desktop.
Save kubo39/dcb946262bceb320ba298292d78fcc92 to your computer and use it in GitHub Desktop.
Download ZIP
SIEVEキャッシュについて
Raw
sieve-eviction-cache.md

SIEVEキャッシュについて

SIEVEというキャッシュアルゴリズムが2023年に発表された。 これはLRUよりシンプルであることを謳っており、実際にかなりシンプルなアルゴリズムだが、S3-FIFOやTinyLFUといった既存の優れたキャッシュアルゴリズムと同等の性能が出るらしい。

ちなみにsieveというのは日本語で「篩」という意味で、エラトステネスの篩とかもこれである。

アルゴリズム

SIEVEのウェブサイトの How does SIEVE work? のアニメーションをみればだいたいわかるが、各操作について書き下してみる。

シンプルなアルゴリズムであるが、LRUのようにひとことで説明するのはなかなかむずかしい。論文中で触れられているように、LRUよりもむしろページ置換アルゴリズムで用いられているCLOCKやセカンドチャンス・FIFO-Reinsertionといったキャッシュアルゴリズムに近い。

データ構造

SIEVEキャッシュは、最大容量・キャッシュのサイズ・単一の双方向連結リストとそれをキーで参照するハッシュマップを内部的に持つ。また、連結リストの先頭と末尾、そして各操作(get/insert)の最後に参照したノードへの参照であるハンドを持つ。 また、連結リストの各ノードはキーと値の組・前後のノードへの参照、さらに各ノードへのアクセス状態を記録するvisitedというフラグを持つ。

取得

内部のハッシュマップを経由して、キーに対応したノードが保持する値を取得する。 ノードはvisitedフラグを更新するが、LRUと違って連結リストの順序を並べ替えるような操作は行わない。

挿入

挿入操作は新規にエントリが追加される場合と、すでに存在しているキーと対応する値を更新する場合の二種類がある。

  1. 新規にエントリが追加される場合:

    キャッシュが制限容量に達している場合に、いずれかのエントリの削除を行う必要がある。ここのアルゴリズムがSIEVEの肝となる。 この操作は直近で操作を行ったノードへの参照であるハンドから連結リストの先頭に向かってエントリを辿っていく。その最中にvisitedフラグがたっているノードはvisitedフラグをfalseにし、visitedフラグがたっていないノードを見つけたらそのノードを削除して処理を終了する。先頭まで辿っていっても見つからければ末尾に移動して、再度先頭に向かって辿っていく。事前にvisitedフラグをfalseにする操作があるので、二週目で必ず削除対象のノードが出現するようになっている。 論文では、このハンドの位置の持ち方によって古くから生存しているエントリがリストの末尾のほうに集まっていくことが重要としている。

  2. 既存のエントリの値を更新する場合:

    この場合は値の更新とvisitedフラグを立てておくだけ。

削除

削除操作はpaperには記載されていないが、基本的にはハッシュマップと連結リストから当該エントリを削除するだけ。

ただし、ハンドが削除対象のエントリを指している場合、削除対象の一つ前のエントリを指すか、削除対象が先頭である場合は末尾を指すようにしたほうがよいと思われる。

各言語の実装

便宜的に各操作で内部的にロックを取得しているものをスレッドセーフな実装と書いてるが、そうでない実装であってもキャッシュに対する操作を自前でロックしてやればよい。

C

  • 1a1a11a/libCacheSim
    • 論文著者のリファレンス実装
    • paperの実装に加えて、expireの設定やハッシュマップからの削除を行うかどうかなどのカスタマイズが可能となっている

Go

  • scalalang2/golang-fifo
    • スレッドセーフな実装
      • キャッシュへの全操作にロックをとる
    • S3FIFOキャッシュも提供している
    • オリジナルのアルゴリズムに加えてexpireの仕組みが追加されている
    • star数が多い
  • opencoff/go-sieve
    • スレッドセーフな実装
      • キャッシュへの全操作にロックをとる

JavaScript(TypeScript)

Rust

  • jedisct1/rust-sieve-cache
    • 内部的にはロックをとらない、非スレッドセーフな実装
    • encrypted-dns-serverの実装はSieveCacheをスレッドセーフに扱うようにラップしている
      • キャッシュへの操作ができるスレッドを同時に一つに制限している

Zig

  • tensorush/zig-sieve
    • 内部的にはロックをとらない、非スレッドセーフな実装

Java

C++

D言語

  • kubo39/sieve-cache-d
    • スレッドセーフな実装とそうでない実装を提供
    • shared型によってロックを取得する実装としない実装を切り分けている
    • シングルスレッドで不要なロック操作が起きない

Nim

Ruby

Python

  • daipham3213/sieve.cache
    • スレッドセーフな実装
    • 他の実装はだいたいMITライセンスだが、これはApache 2.0

Swift

  • nixberg/sieve-swift
    • 内部的にはロックをとらない、非スレッドセーフな実装

C#

  • lostmsu/SIEVE
    • 内部的にはロックをとらない、非スレッドセーフな実装

Elixir

@1a1a11a
Copy link

1a1a11a commented May 21, 2024

This is a nice collection!

@kubo39
Copy link
Author

kubo39 commented May 21, 2024

@1a1a11a
Thank you for checking this! 😄
I have a question: is there any reason that libCacheSim's Sieve uses the chain-based hashmap, not Robin-hood hashmap in this repository?

FYI: the paper in this repo is worth reading: https://github.com/ka-weihe/hashmap-v

@1a1a11a
Copy link

1a1a11a commented May 21, 2024

I was trying different hash tables but did not finish it. In terms of performance, chained hashtable is as good as others when sized well, because they all need two random memory accesses. But there are ways to improve. I will take a look at the repo and get back.

@kubo39
Copy link
Author

kubo39 commented May 21, 2024

Thank you for your answer and I look forward to hearing from you!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment