massivelyを用いたLSMコンパクションのデモを作った

現在おれは、GPU並列アルゴリズムライブラリ「massively」を開発しているが、その目的は、ストレージやVMなどのシステムソフトウェアをGPUによって高速化する基盤を作ることである。今回はLSMにおけるコンパクション計算をGPUで実行するデモを作った。

→ akiradeveloper/lsm-compaction

背景の説明をする。

RocksDBなどのキーバリューストアではLSMツリーというアルゴリズムが使われている。この概要はこうである。まず、書き込みはメモリ上のバッファに書かれ、その後ストレージにフラッシュされるときにSSTableというデータ構造になる。従って、1つのSSTableの中では、そのSSTableの中でのキーに対するバリューの値はわかる。だから、たくさんのSSTableを辿れば、ストレージ全体においてキーに対するバリューの値がわかることになる。

従って、LSMツリーにおいてはSSTableがどんどん増えていくわけだが、それだとストレージがすぐに一杯になってしまうのと検索効率も悪くなっていくので、たまに「コンパクション」と呼ばれるガーベジコレクション的な処理をしてSSTableを断捨離する必要がある。これが、CPUを圧迫し、 CPUが圧迫されると書き込みやクエリに影響が出るという問題が知られている。

LSMコンパクションを和らげる方法は色々と提案されているのだが、その一つとしてGPUにオフローディングするというものがあり、今回はその簡単なデモをmassivelyを用いて構築したということになる。

アルゴリズムを、コードをかいつまんで説明する。

このデモでは簡単のため階層は1階層しかなく、そこにあるSSTableの数が一定数以上になったらフルコンパクションをする。コンパクションではまず、SSTableの中にあるエントリをすべて集め（エントリ数は10M個くらい）、キー昇順、シーケンス番号降順にソートする（sort_by_key）。こうすると、キーのRunの中で最新のものが先頭に来ることになる。次に、キーの中で最新のものだけを集める（unique_by_key）。最後に、tombstone（削除マーカー）を持ったエントリを削除する（remove_where）。

コードでいうとこういう形になる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    massively::sort_by_key(
        &exec,
        zip2(keys.slice(..), seqs.slice(..)),
        zip3(seqs.slice(..), values.slice(..), is_deleted.slice(..)),
        EntryLess,
        zip2(sorted_keys.slice_mut(..), sorted_key_seqs.slice_mut(..)),
        zip3(
            sorted_seqs.slice_mut(..),
            sorted_values.slice_mut(..),
            sorted_is_deleted.slice_mut(..),
        ),
    )?;

    let unique_len = massively::unique_by_key(
        &exec,
        sorted_keys.slice(..),
        zip3(
            sorted_seqs.slice(..),
            sorted_values.slice(..),
            sorted_is_deleted.slice(..),
        ),
        EqualU32,
        unique_keys.slice_mut(..),
        zip3(
            unique_seqs.slice_mut(..),
            unique_values.slice_mut(..),
            unique_is_deleted.slice_mut(..),
        ),
    )?;

    let output_len = massively::remove_where(
        &exec,
        zip4(
            unique_keys.slice(..unique_len),
            unique_seqs.slice(..unique_len),
            unique_values.slice(..unique_len),
            unique_is_deleted.slice(..unique_len),
        ),
        unique_is_deleted.slice(..unique_len),
        zip4(
            output_keys.slice_mut(..),
            output_seqs.slice_mut(..),
            output_values.slice_mut(..),
            output_is_deleted.slice_mut(..),
        ),
    )?;

性能だが、自分の7735HS環境（iGPUは680M）では、 CPUが一回あたり0.85s、GPUはCPU-GPU間のメモリコピー込みで0.75s程度なので、単なるオフローディングだけでなく、高速化まで出来てしまったことになる。コピーごときは大してCPUを圧迫しないので、余ってるGPUを使ってアグレッシブにコンパクションを行ってよいことになり、ストレージの大幅な安定性向上が見込まれる。

ところで、デモの実装だが、このデモは100％AIにコードを書かせることが出来た。今後もAIを使ってmassivelyのデモを作ってみようと思う。アイデアがあったらこっそり教えてほしい。