おれは線形ハッシングの実装LinHashを作っているわけであるが、 前回の記事の最後に、並行性に関するアイデアだけを書き残しておいた。 要点は、「線形ハッシングはバケットごとが全く単純ではないものの シャードのような関係になっており、独立に扱えてもおかしくはない」 というものである。

調べてみると、全く同じ観点で研究がすでにされていた。1987年のことである。 https://dl.acm.org/doi/10.1145/22952.22954

論文を紹介したスライドもある。 https://wiki.eecs.yorku.ca/course_archive/2008-09/W/6490A/_media/presentations:huxia1.pdf

この研究のアイデアを借用して、LinHashに並行性を実装した。 ただし、LinHashではINSERTとDELETEは並行出来ないことにした。 これはきわどいケースでは危険だと判断したため。 一方、GETとINSERTとか、GETとSPLIT（バケットの分割処理、INSERTの延長で起こる）は論文どおり並行に動ける。 GETが他の操作にブロックされないことが論文の一番の目的なので、これはそのまま実現している。

論文のメインのアイデアはlocallevelという世代情報をバケットに埋め込むことなのだが、 もう１つは多段的なロックをとることである。 結果として、LinHashでは各操作が以下のようにロックをとることとなった。 SelectiveLockというのはReadLockとExclusiveLockの中間のようなロックで、 ReadLockとは並行するが、SelectiveLockとは排他されるというものである。

そして、Rustの力を活かすために、これを型で表現することにした。 バケットのロックは、全バケットについて用意するわけにはいかないから、 固定個のロックを用意してストライピングしている。 これによって、メモリ使用量がバケット数に依存することを防ぐ。

1
2
3
4
5
6

pub struct Insert<'a> {
    pub db: &'a LinHashCore,
    pub main_page_id: u64,
    pub root: RwLockReadGuard<'a, Root>,
    pub lock: util::SelectiveLockGuard<'a>,
}

この実装の素晴らしい点は、 INSERTの文脈ではRootのリーダロックとバケットのSelectiveLockをとっていることが 「証明」されることである。このアイデアはLean4から拝借した。 これはほぼ、型安全並行性と読んでもいいのではなかろうか。

あとはまぁ、コードを読んでください。本当に美しく書けた。Rustは本当に強力な言語だ。

https://github.com/akiradeveloper/LinHash