情報処理学会研究報告
IPSJ SIG Technical Report

キーバリュー分離下で範囲クエリを効率的に行うデータ格納手法の提案
杉浦直人 1

藤木大地 1

概要：キーバリューストアはデータの格納にログ構造化マージツリー（LSM ツリー）を使用しているが、その高い書き込み増幅が問題となっている。LSM ツリーの書き込み増幅を減らす方法として、キーバリュー分離という手法がある。キーバリュー分離では、キーのみを LSM ツリーに格納し、サイズの大きいバリューを別のログに保存する。このログは書き込み順にデータを格納するため、範囲クエリを行う際にランダムアクセスが発生する。そこで本研究では、このログ上のバリューを範囲ごとに分割して配置することで、範囲クエリを高速化する手法を提案する。
キーワード：データベース、キーバリューストア、ストレージシステム、SSD

1. はじめにョンを実現している。vLog をハッシュベースで segment に分割し、キーのグルーピングを行う。同じハッシュ値を持キーバリューストアでは、ログ構造化マージツリー[1]つものは必ず同じ segment に格納される。segment ごとに（LSM ツリー）を使用し、書き込みを最適化している。

GC を行うことで、LSM ツリーへクエリを行わずに、どのLSM ツリーは、ランダムな書き込みをメモリ上にバッファバリューが最新かどうか確認できる。GC から時間のかかし、大きなシーケンシャルライトを行うことで、高速な書る LSM ツリーへのクエリを排除することで、HashKV は効き込みを実現する。その後、効率的な検索を可能するため率的な更新を実現した。に、古いキーバリューペアを削除し、キー順にソートする

これらのキーバリュー分離は、効率的な書き込みや更新コンパクションという処理を行う。大量のデータが書き込を実現しているが、vLog 上のバリューがソートされていなまれると、コンパクションが頻繁にトリガーされ、同じデいため、範囲クエリ時にランダムアクセスが発生し、範囲ータが何度も書き直しされることになる。このような書きクエリのパフォーマンスはよくない。ビッグデータの時代込みの増幅は最大で 50 倍になると報告されていて[2]、問において、効率的な範囲クエリは、ますます重要になって題になっている。

いる。分析を行うためには、キーバリューストアに保存しこの書き込み増幅を削減する手法として、WiscKey[2]のたデータを範囲クエリで集計する必要がある。大量のデーキーバリュー分離がある。WiscKey では、バリューを LSM

タを扱うキーバリューストアにおいて、範囲クエリの高速ツリーではなく、別の vLog と呼ばれる循環ログに格納し、化は重要な課題である。

LSM ツリーにキーとバリューのアドレスを格納する。読み

本研究では、範囲クエリの高速化の方法として、HashKV取り時には、LSM ツリーからバリューのアドレスを取得し、のバリューのグルーピング方法をハッシュベースではなく、vLog からバリューを取得する。バリューのアドレスはバリ範囲ベースで分割することを提案する。これにより、範囲ューに比べてサイズが小さいことが多いため、コンパクシクエリ時のランダムアクセスを緩和できる。

ョンによる書き込み増幅が削減される。また、LSM ツリー

本稿では、HashKV を範囲ベースに変更した場合の範囲のサイズが小さくなりメモリにキャッシュされることで、クエリの性能を評価し、今後の研究方針についてまとめる。

読み取り性能も向上する。
しかし、WiscKey の vLog は一つの大きなログ構造に全2. 実装てのバリューを配置するので、古いバリューを削除するガ

実装は、公開されている HashKV のコード[4]を元に行なーベジコレクション（GC）のオーバーヘッドが大きいといった。HashKV のハッシュ値に変換しグループを決定する

う問題がある。GC では、vLog の末尾から順に LSM ツリー処理を、範囲でグループが決まるように変更を加えた。

へクエリを行い、バリューが更新されていないか確認を行う。更新されていないバリューのみを vLog の先頭に書き3. 評価込み、使用していたスペースを開放する。GC の問題点とし

WiscKey、HashKV、範囲ベースの HashKV それぞれの範て、LSM ツリーへのクエリは時間がかかるため、更新中心囲クエリにかかる時間を計測した。HashKV でのグループのワークロードでは性能が低下してしまう。

数は 100 と設定している。キーバリューペアのサイズは 1

この問題に対処するために、HashKV[3]は、vLog をハッKB で、0 から 999999 の範囲のキーをキーバリューストア

シュベースで分割することで、効率的なガーベジコレクシに書き込んだ。実世界のワークロードを模すために、書き込んだキーに対し、ランダムに 10 万回の更新を行った。そ1 慶應義塾大学ⓒ2023 Information Processing Society of Japan

1情報処理学会研究報告
IPSJ SIG Technical Reportの後、範囲 1000 （約 1 MB）の範囲クエリを行い、実行時ヒット率を上げることなども検討している。キャッシュヒ間を計測した。結果を図 1 に示す。

ット率の向上により、読み取り性能の向上ができると考えている。

計測時間 [μs]

2.5

参考文献

2[1]

1.5

[2]

1[3]

0.5
0WiscKey
図 1HashKVRange

範囲クエリの計測時間

[4]
[5]

O’NEIL, Patrick, et al. The log-structured merge-tree (LSM-tree).
Acta Informatica, 1996, 33: 351-385.
LU, Lanyue, et al. Wisckey: Separating keys from values in ssdconscious storage. ACM Transactions on Storage (TOS), 2017,
13.1: 1-28.
CHAN, Helen HW, et al. {HashKV}: Enabling Efficient Updates
in {KV} Storage via Hashing. In: 2018 USENIX Annual TechnicalConference (USENIX ATC 18). 2018. p. 1007-1019.
http://adslab.cse.cuhk.edu.hk/software/hashkv/
TANG, Chenlei; WAN, Jiguang; XIE, Changsheng. Fencekv:
Enabling efficient range query for key-value separation. IEEETransactions on Parallel and Distributed Systems, 2022, 33.12:
3375-3386.

結果は、WiscKey が 2.09 µs、HashKV が 1.94 µs、範囲ベースの HashKV が 1.57 µs であった。範囲ベースにした場合、WiscKey に対し 1.3 倍、HashKV に対し 1.2 倍の高速化が行えることがわかった。vLog 上のバリューの配置を範囲ベースに変更することで、範囲クエリ時に、同時に読み取られる可能性が高いデータを近くに配置することで、性能を上げることができた。

4. まとめと今後の方針
本稿では、HashKV のグルーピングをハッシュから範囲ベースに変更することで範囲クエリの高速化をすることができた。
今回の評価では、キーの範囲が 0 から 999999 と設定しているが、実際のワークロードではキーの範囲や、分布はわからない。HashKV では、グループ数は固定であり、変えることはできない。また、格納する範囲が固定であると、負荷が偏ることが想定される。そのため、HashKV を範囲ベースに変えるだけでは、実際のワークロードで使用することは難しい。
格納する範囲をワークロードの中で決定する研究として FenceKV[5]がある。FenceKV では、グループが含む最小のキーとしてフェンスを生成し、フェンスベースでグループを決定している。しかし、フェンスは確率的に生成し、一度生成されたら削除されない。そのため、実際の分布を考慮できず、フェンスによっては、分布が偏ってしまう可能性がある。
今後の方針として、我々は、上記問題に対して動的シャーディングを用いて対処する予定である。ワークロードに合わせて、シャードの数やシャードが格納する範囲を動的に変えることで、実際のワークロードにも適応できると考えている。
そのほかの研究の方向として、In SSD processing を用いて、古いデータを削除することで、ホスト側のキャッシュⓒ2023 Information Processing Society of Japan2