自己設計システムとは、システム内の選択可能なプリミティブから、データベースのワークロードとハードウェアに最適な組み合わせを自動的に生成するという概念のものです[1]。今回は、この自己設計システムのコンセプトの著者の、キーバリューストアを題材とした直近の論文を紹介してみます[2]。 自己設計によるカスタマイズ (Customization through Self-Design)とは? 自己設計(Self-Design)は中世の原子論的に、基礎となる設計要素を組み合わせ、最適な組み合わせとなるシステムを構成する概念のものです。選択可能なプリミティグには、ハードウェアだけではなく、分散システムのパーティショニング方法(例: ハッシュ分割、レンジ分割)やデータアクセス方法(例: スキャン、ソート済検索など)などのソフトウェア(アルゴリズム)も含まれます [3]。 自己設計による最適化手法には、学習コストモデルを用いた最適化や機械学習が用いられ、新しい組み合わせが未知のアルゴリズムやデータ構造を生み出すことで、パフォーマンスを大幅に向上させる可能性があります[1][3]。本論文では、具体的な評価対象システムとしてキーバリューストアを題材に、自己設計(Self-Design)における手法を提案しています。 キーバリューストアとは？ キーバリューストアは、キーと値のペアを格納するデータ構造を実装したものです。キーバリューストアは、ソーシャルメディアのグラフ処理、アプリケーションデータのキャッシング、NoSQLストレージ、オンライントランザクション処理などの、多種多様なアプリケーションの基盤として活用されています[2]。 また、近年のリレーショナルデータベースであるGoogleのSpannerや、RockDBをMySQLのバックエンドストレージとしたMyRocks、FoundationDBをバックエンドストレージとしたデータウェアハウスのはSnowflakeなども、バックエンドにキーバリューストアが採用されています [2][5]。 主要なKey-Valueデータ構造 キーバリューストアのデータ構造については、読み取り・書き込み・メモリ消費量には常にトレードオフが存在し、この３つ全てを最適とするデータ構造は存在しません[2]。結論としては各目的に応じたデータ構造が必要となるのですが、現時点で代表的なデータ構造として、B+Tree、LSMツリーなどが存在しています。 B+Tree B+Treeは、RDBMSやファイルシステムでも採用されている主要なツリー構造で、合理的なメモリ消費量で読み取りと書き込み性能のバランスに優れ、現在はOracleの製品であるBerkeleyDBや、近年でもMongoDBの標準ストレージエンジンとなったWiredTiger、FoundationDBなどのキーバリューストアに採用されています。 LSMツリー LSMツリー(Logs-structured merge-tree)は、高速な書き込みと読み取り性能を共存させるデータ構造で、GoogleのLevelDBやBigTable、FacebookのRocksDB、Apache CassandraやHBase、さらにはMySQLやSQLiteなどのRDBMSの主なキー管理などにも採用されています。ただし、B+ツリー構造より書き込み性能は優れますが、読み込み性能は悪化する場合があります。 その他 (LSHテーブル、ハイブリッドな構成など) 近年はRiakのBitCaskやSpotifyのSparkeyに用いられているLSHテーブル(Log-Structured Hash-table)などの新しい構造もあります。また、アプリケーションに適切なパフォーマンスを提供するため、複数のデータ構造を排他的に提供する場合もあります。例えば、MongoDBのWireTigerでは、B+TreeとLSMツリー実装を排他的に個別にサポートしており、RocksDBでは部分的にハッシュテーブル構造を取り入れて最適化しています。 多くの最新のキーバリューストアは、相互に排他的なスワップ可能なデータレイアウト設計のセットで構成され、多様なパフォーマンス特性を提供します。たとえば、WiredTigerはBツリーとLSMツリーの実装を個別にサポートして読み取りまたは書き込みをそれぞれ最適化しますが、RocksDBファイルはソートされた文字列レイアウトまたはハッシュテーブルレイアウトをサポートして、範囲の読み取りまたはポイントをさらに最適化しますそれぞれ読み取ります。 自己設計(Self-Design)の目的 自己設計(Self-Design)の長期的な研究課題は、例えば前述のキーバリューストアの場合、対象の問題に最適なデータ構造を、簡単または自動的に選択できるかが重要な課題となります。自己設計は、対象となるドメイン知識となる原則を導き出すことを目的としており、今回の論文では、自己設計を実現するものとして、連続体(Design Continuums)の概念を提唱しています。…
自己設計(Self-Design)と設計連続体(Design Continuums)の概念について
