WIP【備忘録】DBの論文を読む : 新しいDBMSアーキテクチャ
そろそろデータベースに関するちゃんとした基礎知識をつけたいという思いがあるので、Readings in Database Systems, 5th Edition を読んでいこうと思う。
URL: http://www.redbook.io/index.html
この本は、DB に関する古典的な論文から、近年の特に重要な論文まで、章ごとに短い解説とともに紹介されている。
今回は Ch4 新しいDBMSアーキテクチャ
を読む。
紹介された論文
C-store: A Column-oriented DBMS. SIGMOD, (2005)
- 列ストアのDBである
C-store
に関する論文
- 列ストアのDBである
Hekaton: SQL Server's Memory-optimized OLTP (2013)
- インメモリOLTPである
Hekaton
に関する論文
- インメモリOLTPである
OLTP Through the Looking Glass, and What We Found There. SIGMOD, 2008 (2008)
- OLTP向けDBの標準的な機能にどれだけ処理時間が食われているかを調査した論文
解説を読んだ
ここ20年ぐらいでRDBMS市場は大きく変わったらしい。
特に以下の4つの大きな変化があった。
- DWH市場では列ストアの優位性が高まる
- メインメモリの価格の低下
- 確かに、RAMの価格の低下は個人レベルでも感じていた
- NoSQLの台頭
- 「すぐに使えること」「半構造化データのサポート」を特性として持つ
- Hadoop・HDFS・Sparkの出現
- 詳しくは6章を参照とのこと
- Sparkは仕事でも使っているから個人的に馴染み深い
こうしてみると、1,3,4は私が本格的にデータ分析やCSを学び始めた頃には当然のようにあったので、そんなに新しい技術という感じはしていなかったが、最近の変化だったのかぁという感想。
この章で紹介されている論文はわからない単語が多くて特に大変だった。。
論文1について
Abstract
この論文では、特に読み取りに最適化されたRDBMSの設計を紹介している。
具体的な特徴としては、
- 行単位ではなく列単位でデータを格納
- クエリ処理中にメインメモリを含むストレージにオブジェクトを格納する際には慎重にコーディングしてパッキング
- 現在のテーブルやインデックスではなく、列指向のプロジェクションのオーバーラップしたコレクションを格納
- 読み取り専用トランザクションの高可用性と snapshot isolation を含む、従来とは異なるトランザクションの実装
- B-tree構造を補完するためのビットマップインデックスの使用
等が挙げられる。
また、論文では、TPC-Hのサブセットにおける予備的な性能データを提示している。
感想とメモ
背景
先に書いたように、時代が進むにつれてDWH
では列指向DB
が適しているとされるようになった。
(そもそもOLTP/OLAP/DWHって何?という人はこのサイト等で確認してほしい)
DWH
はその使用用途から少なくとも以下の要件を満たすことが求められる。
高速な読み込み
- 逆に、書き込み速度はそこまで重視されない
少数の列かつ大量の行に対するクエリに最適化されている
- 逆に、
select *
等のクエリは余り使用されない - 例えば、スタースキーマで設計されている場合はファクトテールブルの行数は非常に多くなる
- 逆に、
これらの観点に関して、行指向DB
よりも列指向DB
は優れているとされる。
簡単に言うと、行指向DB
は行単位でデータを持っているため特定列(属性)の効率的な取得ができないが、列指向DB
は列単位でデータを持っているためこの操作が効率良くできるというイメージだ。
この2方式のより詳細な説明は以下のサイトを参考にしてほしい。
- https://docs.treasuredata.com/pages/releaseview.action?pageId=331325
- https://dataschool.com/data-modeling-101/row-vs-column-oriented-databases/
- https://www.cs.ucdavis.edu/~green/courses/ecs165b-s10/Column_Store_Tutorial_VLDB09.pdf
C-storeは列指向DB
の実装の一つだ。
C-storeの特徴
C-storeは以下の特徴を持つ。
この内、幾つかの特徴は列指向DB一般に言えることに注意。
- DWHのような読み取りに最適化された用途に焦点を当てているが、書き込み頻度の低い用途にも対応
- 必要な属性(列)だけをメモリに取り込み、必要な分析を行うことができる
- 同じ列の属性は同じデータ型であるため、効率的な保存/検索のために情報をエンコードすることができる
- 圧縮。byteやwordの境界で整列するのではなく、より密に纏められる
- 「特定のキーでソートされた列のグループ」(
projection
)を、物理的に連続した空間に格納する
- シェアードナッシングの分散アーキテクチャに対応
- シェアードナッシングアーキテクチャについては、Gammaを参照
- 異なるプロジェクションがシステム内の異なるノードに配置されることも想定
- 並列クエリの問い合わせの高速化 (
holizontal partition
) - システム内のk個のノードに障害が発生しても、DBへのアクセスとデータの回復/クエリ問い合わせが可能 (
k-safe
のサポート)
- ロック・2PCを使用しない、高速な読み取り(分散)txn (
snapshot isolation
) - 列指向のクエリオプティマイザ
- late materialization
なお、C-storeに含まれる殆どの技術は既に存在していたが、C-storeはそれを纏め上げたところに注目するべきか。
C-store データモデル
C-storeは論理データモデルは一般的なRDBと同じだが、物理データモデルは一般的な行ストアと大きく異なる。
論理データモデル
C-storeの論理データモデルは一般的なRDBと同じく、主キーや外部キーを持つテーブル形式だ。
出典: C-store: A Column-oriented DBMS
物理データモデル
C-storeの物理データモデルは一般的な行ストアとは大きく異なる。
一般的な行ストアはテーブルを直接実装し、別途indexを追加することで高速なアクセスを実現していた。
一方で、C-storeはprojection
と呼ばれる「特定のキーでソートされた列のグループ」のみを実装する。
projectionは論理テーブルにつなげられており、それ故にその長さは繋げられた論理テーブルの行数と等しくなる。
ただし、projectionは外部キーによる結合先の列も含めることができる。
projectionの例
# PROJECTION_NAME (col1, col2, ... | sorted cols) EMP1 (name, age | age) EMP1 (name, age | name) EMP3 (dept, age, DEPT.floor | DEPT.floor) # DEPT.foorは外部キーにより取得したカラム EMP4 (name, salary | salary) DEPT1 (dname, floor | floor)
なお、projectionはhorizontally partition
、つまり行方向に分割ができる。
分割はソートキー(列)の値範囲により行われ、分割後のデータをsegments
と呼び、SID
が付与される。
さらに、各セグメント内の行をrecord/tuple
と呼ぶ。
また、projectionの集合は以下の要件を満たす必要がある。
- 任意のクエリに対応するため、projectionを組み合わせることで完全なテーブルを構築できる
各projectionはsegmentsに分割されているため、この要件を満たすには各projectionの各segmentのtuple同士を紐付ける仕組みが必要だ。
そのためにStorage Keys
とJoin Indices
を導入する。
Storage Keys
Storage Key(SK)
はtupleに対して「同じsegmentの異なる列の値が元々論理テーブルで同じ行だった組で紐づくように」付与される値。
Join Indices
テーブルTを復元できる2つのprojectionの組 {T1, T2} があった時、
「T1のM個のsegmentとT2からN個のsegmentへのjoin index
」は論理上Mつのテーブルの集合である。
テーブルの内容は、T1のsegment Sに対して(s: SID in T2, k: SK in segment s)
となっている。
下例はEMP1からEMP2へのjoin indexの例だ。(EMP1のSID=1を仮定)
出典: C-store: A Column-oriented DBMS
C-storeの構成
C-storeは読み込みに対する最適化と書込み可能の両立を図るために、以下の3つの要素でFigure1のように構成される。
- WS (Writable Store) ... insert/update
等の書き込みが可能なアーキテクチャ
- RS (Read Optimized Store) ... 読み込みに最適化されたアーキテクチャ. 大容量の情報が扱える.
- Tuple Mover ... WSのレコード(tuple
)をRSへ移動させる役割を担う
出典: C-store: A Column-oriented DBMS
RS
RS
は読み込みに最適化された列ストアであり、以下の特徴を持つ。
tuple
のSKはsegment内のrecord
の序数であり、それ故保存はされず必要な時に計算されるjoin indexes
は通常のカラムと同じように保存される- RSの列は以下の4通りのエンコーディングで圧縮される
- Type1: 自カラムによるソート, ユニーク値が少ない :
run length encoding
- 右tupleのシーケンスで表現される
(v: value, f: vが現れる最初のposition, n: vの出現回数)
- clusterd B-tree indexが使えるらしい
- 右tupleのシーケンスで表現される
- Type2: 他カラムによるソート, ユニーク値が少ない :
bitmap encoding
- 右tupleのシーケンスで表現される
(v: value, b: vが現れる場所に1, それ以外に0)
- bitmapはsparseなので、更に
run length encode
される offset index
(positionを値にマップするB-tree)を使うらしい
- 右tupleのシーケンスで表現される
- Type3: 自カラムによるソート, ユニーク数が多い :
block-oriented delta encoding
- 前の値からの差分で表現される ex) (1, 4, 4, 5, 5) -> (1, 3, 0, 1, 0)
- olock-orientedの意味がわかっていない。。。
densepack B-tree at block-level
が使えるらしい
- Type4: 他カラムによるソート, ユニーク数が多い : エンコードなし
- この場合、エンコーディングは行わない
densepack B-tree at block-level
が使えるらしい
- Type1: 自カラムによるソート, ユニーク値が少ない :
エンコーディングの参考
- https://www.youtube.com/watch?v=bUY2-8GHKsQ
- https://techblog.yahoo.co.jp/entry/20190924753251/
- http://www.clg.niigata-u.ac.jp/~lee/jyugyou/info_system/medsys004_printw.pdf
WS
WS
はRS
と同じオプティマイザを使うため、RS
と同じ列ストア・物理DBMS設計となっている。
しかし、効率的な書き込み(更新)txnを実現するため、storage representation
は全く異なるものになっている。
- SKは明示的にsegmentに保存される
WS
はRS
と同じようにhorizonzal paritition
される- よって、
RS
のsegmentとWS
のsegmentは1:1で対応する
- よって、
WS
はRS
と比べて小さいと想定されるので、データの圧縮は頑張らないWS
のprojectionは(v: value, SK)
の集合で表現される (夫々のペアはSKのB-treeで表現される)- ソートキーは
(s: sort key value, sk: sが最初に現れるSK)
の集合で表現される
- ソートキーは
TODO: jion indexの話
Tuple Muver
Tuple Muver (TM)
はその名の通りWS
のtuple
をRS
へ移動させる。
具体的には、tuple
のブロックをWS
からRS
へ移動し、プロセス内のjoin index
を更新する。
TM
は更新が必要なすべてのsegmentについて、RS
に新しいセグメントを作成する。
新しいsegmentが作成されると、古いsegmentが置き換えられ、古いsegmentを削除することができる。
TM
に関しては以下のpdfがわかりやすい。
http://dsg.csail.mit.edu/6.830/lectures/lec7.pdf
トランザクション関連のお話
snapshot isolation
読み取り(read-only
)txnを高速にするため、ロックと2PCを使用しない方式であるsnapshot isolation
を使用している。
これにより、読み取りクエリは最近のある時点でデータベースにアクセスし、コミットされていないトランザクションがないことを保証できる。
https://ja.wikipedia.org/wiki/Snapshot_isolation
TODO: ここら辺、もう少し書く
クエリ最適化
C-storeで使用しているオプティマイザは以下の特徴がある
- データの圧縮形式を考慮する
- どのprojectionの組み合わせを使用するかを考えてくれる
- late materialization
: 実行計画の後ろの方でデータの解凍をおこなう
- メモリの節約
なお、クエリ最適化の図示は以下のpdfがわかりやすい
http://dsg.csail.mit.edu/6.830/lectures/lec7.pdf
分散コミットやリカバリの話は気が向いたら書く。
関連論文
- https://vldb.org/pvldb/vol5/p1790_andrewlamb_vldb2012.pdf
- https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.141.5843&rep=rep1&type=pdf
参考になりそうなリンク
- https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-830-database-systems-fall-2010/lecture-notes/MIT6_830F10_lec15.pdf
- https://sookocheff.com/post/databases/c-store/
- https://dataschool.com/data-modeling-101/row-vs-column-oriented-databases/
- https://blog.csdn.net/The_Time_Runner/article/details/115356992
- https://www.cs.ucdavis.edu/~green/courses/ecs165b-s10/Column_Store_Tutorial_VLDB09.pdf
- https://slideplayer.com/slide/6948535/
- https://web.eecs.umich.edu/~mozafari/fall2018/eecs584/reviews/summaries/summary11.html
- https://medium.com/@ameya_s/c-store-a-columnar-database-1fe7e84d7247
Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005
論文2について
Abstract
この論文は、Hekaton
と呼ばれるメモリ常駐データとOLTPワークロード用に最適化された新しいデータベースエンジンの解説をしている。
HekatonはMicrosoft社のSQL Serverに統合されているインメモリOLTP
であり、独立したシステムではない。
Hekatonは以下のような特徴がある。
手軽に利用できる
- ユーザーがHekatonを利用するには、テーブルメモリの最適化を宣言するだけでよい
- 通常のSQL Serverのテーブルと同じ方法でT‐SQLを使用してアクセスする
- クエリはHekatonテーブルと通常のテーブルの両方を参照できる
- txnは両方のタイプのテーブルのデータを更新できる
高いパフォーマンス/最適化/同時実行制御
感想とメモ
背景
Hekatonの話に入る前に、インメモリDB(IMDB)
とは何か/何故登場したかというところから勉強する。
1970年代に初めて登場したDBMS(System R)は以下のような環境で設計されていた。
1. シングルコアCPU
2. 小容量のRAM
しかし、時は流れCPUの進化やRAM(メモリ)の低価格化・大容量化が進んでいった。
そのため、上記2点を前提にしない、特に大容量のRAMを活かすようなDBMSの開発が進んだ。それがIMDB
だ。
インメモリDBの定義をwikipediaから引用する。
インメモリデータベース(IMDBあるいはメインメモリデータベース、MMDB)はデータストレージを主にメインメモリ上で行うデータベース管理システムである。ディスクストレージ機構によるデータベースシステムと対比される。
出典: wikipedia
メモリが大量にあるならディスク上ではなくメモリ上にデータを乗っけちゃえばいいじゃんという発想だ。
IMDBの特徴としては例えば以下のような項目が挙げられる。
- 勿論ディスクよりメモリのほうがパフォーマンスが高い
- キャッシュを利用したシステムより柔軟な制御が可能であり、データ管理方法の最適化ができるかも
- IMDBは内部最適化アルゴが簡素で、(通常のDBより)相対的にCPU命令数が少ない(らしい)
- HDDを使用することによって発生していた問題が無くなる
- 例1. データとキャッシュのコピーを同期する必要がない
- 例2. ディスク上に比べて、データの効率良い圧縮/解凍ができる
- その他、バッファプール, 並列制御(ロック), ロギング/リカバリ...
- ACIDの内、D(永続性)については別途考えないといけない
そんなわけで、この特徴から見るとIMDBは従来の(OLTP)DBに比べてリスクが高そうなので、OLTPというよりOLAP向けなのかなぁという気がするが、
IMDBの普及に従いOLTP分野へも進出してきた。
その一つの例がSQL ServerのHekaton
だ。
「HekatonはMicrosoft社(MS)のSQL Serverに統合されているインメモリOLTP
」と冒頭で述べた。
インメモリOLTP
とはなんだろうか? MSの公式サイトから引用する。
インメモリ OLTP は、トランザクション処理のパフォーマンスの最適化、データの取り込み、データの読み込み、および一時的なデータのシナリオに SQL Server と SQL Database で使用できる高度な技術です。 ...(省略)...
インメモリ OLTP は、トランザクション処理のパフォーマンスを向上させる SQL Server テクノロジであることに注意してください。出典: 概要と使用シナリオ
う、うーん。つまるところ、IMDBの技術を使用したOLTPぐらいの理解で良いか。
インメモリOLTPについての話は、引用先のリンクから参照できる17分の動画も分かりやすかった。
OLTPで使用するんだから、勿論、耐障害性を持つ。
現在では、データがメモリ内にあるからというだけで、障害が発生したときにデータが失われることを意味しなくなりました。 既定で、すべてのトランザクションは完全に持続可能になりました。つまり、SQL Server の他のテーブルと同じ持続可能性の保証があります。
...(省略)...
トランザクション コミット後のどこかの時点で障害が発生すると、データベースがオンラインに戻ったときに、コミットされたデータを利用できます。 さらに、インメモリ OLTP は、SQL Server の高可用性とディザスター リカバリー機能 (AlwaysOn、バックアップ/復元など) と連携します。出典: 概要と使用シナリオ
インメモリOLTPが特に有効なのは、「高スループット、低遅延txn」の場合である公式サイトに記載されている。
個々のトランザクションの低遅延を保ちながら、大量のトランザクションに対応します。 一般的なワークロード シナリオとして、金融商品の取引、スポーツくじ、モバイル ゲーム、広告配信などがあります。 また、一般的なパターンとして、読み取りや更新が頻繁な "カタログ" もあります。 たとえば、大きなファイルが複数ある場合、各ファイルは複数のクラスター ノードに分散され、メモリ最適化テーブル内にある各ファイルの各シャードの場所を分類します。
出典: 概要と使用シナリオ
一般のインメモリOLTPの話とHekatonの話が混ざっている気がするが、何となくのイメージは掴めたと思う。
インメモリDBの説明は、このスライドの前半部分も分かりやすかった。
Hekatonの特徴と構成
まずはHekatonの特徴をまとめる。
- SQL Severに統合
- メモリ上に配置するテーブルを選択することができる
- 完全なACIDをサポート
- メモリに最適化されたindex (ハッシュ、
Bw-tree
) - 高い同時実行性
- どのスレッドもラッチ/ロックを取得せずにテーブルの任意の行にアクセス可能
- ラッチのないデータ構造によりスレッド間の物理的な干渉を回避
MVCC
(多版同時実行制御)によりtxn間の干渉を回避
- どのスレッドもラッチ/ロックを取得せずにテーブルの任意の行にアクセス可能
Hekatonは高いスループットを実現するためにtxn毎の実行命令数の削減とCPI(1命令あたりのサイクル数)を低くする必要があった。 そのため、Hekatonは以下の原則を元に設計された。
- メインメモリのインデックスを最適化
- 複雑なバッファプール管理を避ける
- インデックス操作はログに記録しない (耐久性はロギングとチェックポイントによって保証する)
- 複雑なバッファプール管理を避ける
- ラッチとロックの排除
- ラッチやスピンロックによるスケーラビリティ低下を防ぐ
- 内部データ構造(アロケータ、インデックス、トランザクションマップ, ...)は完全にロック/ラッチフリー
- MVCC
- ラッチやスピンロックによるスケーラビリティ低下を防ぐ
- リクエストの機械語へのコンパイル
- 実行時のパフォーマンスを最大化
- 実行時のオーバーヘッドを削減するため、コンパイル時に多くの決定を行う(ex データ型)
- 実行時のパフォーマンスを最大化
なお、テーブルのパーティション分割はサポートしていない。
Hekatonは以下のコンポーネントで構成される。
- Hekatonストレージエンジン
- Hekatonコンパイル
- Hekatonランタイム
- SQL Serverのリソースとの統合などもろもろ
Hekatonは、既存のSQL Severの資産を可能な限り生かす様に設計されている(のだと思う)。
これらのコンポーネントは図1の様に配置される。
引用: Hekaton: SQL Server's Memory-optimized OLTP
図に関する詳しい説明は論文参照。
各部
インデックスとレコードの読み取り/更新
メモリ上に作成されたテーブルに対して、Hekatonは2つのindexを提供する。
- hash index ... ロックフリーハッシュテーブルを使用
- ハッシュバケットによる分割
- Bw-treeによる範囲index ... B-treeのロックフリー版
indexについて以下を抑えておく。
- indexには実際のデータへのポインタが格納される。
- 1つのテーブルに対して複数のindexを作成でき、レコードには常にindexでアクセスする。
下図はテーブルとindexの例。
引用: Hekaton: SQL Server's Memory-optimized OLTP
Begin
とEnd
が気になると思う。
これらは「値が有効であり、期間が厳密に重複していない場合のトランザクションタイムスタンプの範囲」を表している。ざっくりいうと有効時間。
例えば、John
に関するレコードは時刻10~20まで(John, London, 100)
で、20~Tx75
まで(John, Longon, 110)
で、最新が(John, London, 130)
と解釈できる。
赤文字の100
は更新に関する所なんだけど、これは論文を参照してほしい。
読み取りについて
読み取りは、読み取り時点の時刻を指定し、有効時間が読み取り時刻と重複するバージョンのみが表示される。
更新について
更新時の操作については論文参照。
更新は新しいバージョンのレコードを作成することで行われる。
古いバージョンはtxnから見えなくなった際にGCされる。
プログラミングとコンパイル
Hekatonを作る上での目標に、
- アドホッククエリの実行を最適化するのではなく、 compile-once-and-execute-many-timesワークロードの効率的な実行(ざっくり、同じクエリの複数回実行)をサポートする
- HekatonはOLTP向け
- 既存のSQL Serverアプリとの高い言語互換性もつ
というものがある。
これを達成するため、Hekatonはクエリのコンパイル機能を提供する。
また、HekatonコンパイラはSQL Serverの機能(ex メタデータ, パーサー, 名前解決, ...)を再利用している。
恐らく、私達が触れているDBMSではクエリはインタプリタ方式で実行されるだろう。
しかし、HekatonはHekatonコンパイラによってクエリをコンパイルし機械語に変換することができる。
これは(多分)一般のプログラミング言語でいうJIT(Just In Time)コンパイル
だろうか。
コンパイラの出力はCコードであり、Microsoft VC++でDLLにコンパイルされ、実行時にロード・実行される。
引用: Hekaton: SQL Server's Memory-optimized OLTP
詳しい実装は論文を参照。
一応、ストアドプロシージャの説明を記載しておく。
ストアドプロシージャ (stored procedure) は、データベースに対する一連の処理をまとめた手続きにして、関係データベース管理システム (RDBMS) に保存(永続化)したもの。 永続格納モジュール (Persistent Storage Module) とも呼ばれる。ストアドプロシージャの格納先はRDBMSの実装により異なり、RDBMSのデータ辞書や専用の格納スペースが用いられている。
引用: wikipedia
トランザクション/MVCC
Hekatonは楽観的な多版同時実行制御(MVCC)
を使用することで、ロックを使わずにtxn管理を行う。
Hekatonのtxn管理について論文には記載されているが、ここではMVCC
の定義に関する話をするに止めようと思う。
私のここら辺に関する理解が深まったらもう少しちゃんと書きたい。
MVCC
について、wikipediaには以下のように記載されている。
MultiVersion Concurrency Control (MVCC, マルチバージョン コンカレンシー コントロール) は、データベース管理システムの可用性を向上させる制御技術のひとつ。複数のユーザから同時に処理要求が行われた場合でも同時並行性を失わずに処理し、かつ情報の一貫性を保証する仕組みが提供される。日本では多版型同時実行制御、多重バージョン並行処理制御などと訳される。また単にマルチバージョンとも呼ばれる。
MVCCは、書き込み処理(トランザクション)が行われている最中に他のユーザによる読み取りアクセスがあった場合、書き込みの直前の状態(スナップショット)を処理結果として返す。つまり、書き込み中も読み取りができ、読み取り中でも書き込みができる。
MVCCにおいて可用性を達成するには、最低限、全ての処理が「どの順番で」行われたかを確実に記録する必要がある。そのため、タイムスタンプやトランザクションIDなどを用いて全ての更新処理が管理される。
引用: wikipedia
雑に、「複数の状態(スナップショット, バージョン)を管理することで同時実行制御をする方式」ぐらいでも多分良さそう。
より詳しいMVCCの説明は以下の記事がわかりやすかった。
- https://the-weekly-paper.github.io/jekyll/update/2017/06/25/An-empirical-evaluation-of-in-memory-multi-version-concurrency-control.html
- https://stackoverflow.com/questions/5751271/optimistic-vs-multi-version-concurrency-control-differences/39269085
- OCCとMVCCの違いに関する説明
とはいえ、ここらへんの話はもう少しちゃんと勉強しないと腑に落ちなさそうな気がしている。。
MEMO:後で読む
- https://www.slideshare.net/hironorimiura/nightmvcc
- https://bellsoft.jp/blog/system/detail_586
- https://blogs.sap.com/2016/03/01/from-the-archives-why-snapshot-isolation-is-so-useful/
ロギング・チェックポイント・リカバリ
Hekatonのロギング、チェックポイント、リカバリコンポーネントの設計 は以下の原則に基づいて行われた。
- シーケンシャルアクセスへの最適化
- 顧客が高速なランダムアクセスを備えたI/Oデバイスではなくメインメモリにお金を使えるように
- 通常時のtxn処理のオーバーヘッドを最小化
- 作業はリカバリのときに押し込めたい
- スケールする際のボトルネックの解消
- リカバリ中のI/O, CPUの並列処理を有効にする
Hekatonはメインメモリのテーブルに最適化されているが、障害後にこれらのテーブルを回復できるようにtxnの耐久性を確保する必要がある。
ログについて
通常、txnログの末尾がボトルネックであるため、ログに追加されるログレコードの数を減らすと、スケーラビリティが向上し、効率が大幅に向上する。
Hekatonのログについて纏めておく。
- ログは基本的にコミットされたトランザクションのREDOログで構成される
- UNDOログは記録されない
- ログにはtxnによって挿入/削除された全てのバージョンに関する情報が含まれている
- index操作のログは記録されない
- 全てのindexはリカバリ時に再構築される
- txnのコミット時にのみログレコードを生成する
- WALは使用しない
- 複数のログレコードを1つの大きなI/Oにグループ化する
- DB毎に同時に生成される複数のログストリームをサポート
ここら辺はインメモリのおかげでシンプルになっているんだろうか。
チェックポイントについて
チェックポイントはリカバリ時間を短縮するために実装されるが、特にHekatonでは以下の2要件を満たすように設計された。
- 継続的なチェックポイント ... チェックポイント関連のI/Oは、txnが蓄積されるにつれて、段階的かつ継続的に発生する
- 突然頑張りだしてシステム全体のパフォーマンスが突然落ちるのは避けたい
- ストリーミングI/O ... 可能な限りランダムI/OではなくストリーミングI/O
MEMO: ストリーミングI/Oと調べたんだけど結局なんなのか分からんかった。 シーケンシャルI/Oだと思って良い?
チェックポイントは複数のデータ/デルタファイルとファイルとチェックポイントファイルインベントリで構成される。
夫々の役割を確認しよう。
- データファイル
- 特定のタイムスタンプ範囲で挿入された(挿入と更新によって生成された)バージョンを含む
- 開いている間は追記のみ可能で、一度閉じるとそれ以降は読み取り専用となる
- デルタファイル
- データファイルに含まれているバージョンが後で削除という情報を含む
- デルタファイルとデータファイルは1:1で対応
- 対応するデータファイルの存続期間中に追加のみ可能
- チェックポイントファイルインベントリ
- 完全なチェックポイントを構成するすべ てのデータとデルタファイルへの参照を追跡する
実質的に、チェックポイントは圧縮されたログのように考えられる。
リカバリはデータファイル読み込み->デルタファイルによるフィルタリングという流れで行われる。
チェックポイントの作り方やリカバリの詳しい話は論文を参照。
GC
書き込み方法から明らかなように、メモリ上には古いバージョンのレコードがどんどん増えてくる。
そのため、アクティブなtxnからは見えなくなったバージョンを削除する必要がある。
GCと聞くと一般的にはポインタの到達可能性を元に行われることを想像するが、HekatonのGCは「(アクティブなtxnからの)バージョンの可視性」によって行われる。
Hekaton GCは以下の特徴を持つ。
- ノンブロッキング ... アクティブなtxnの処理を停止することはない
- 協調的 ... txnを実行しているスレッドは、ガベージに遭遇したときにそれを削除できる。よって、スキャンの邪魔になるものは事前に削除できる。
- 処理はインクリメンタル ... GCは簡単に調整でき、過剰なCPUの消費を避けるためにGCを開始/停止できる
- 並列的/スケーラブル ... 複数のスレッドで同期を殆ど行わず動作する
GCの詳しい処理は論文参照。
関連論文
- http://www.vldb.org/pvldb/vol9/p1609-larson.pdf
- https://link.springer.com/content/pdf/10.1007/s00778-021-00663-8.pdf
参考
- https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%82%A2%E3%83%89%E3%83%97%E3%83%AD%E3%82%B7%E3%83%BC%E3%82%B8%E3%83%A3
- https://stackoverflow.com/questions/5751271/optimistic-vs-multi-version-concurrency-control-differences/39269085
- https://ja.wikipedia.org/wiki/MultiVersion_Concurrency_Control
- https://docs.microsoft.com/ja-jp/sql/relational-databases/in-memory-oltp/sql-server-in-memory-oltp-internals-for-sql-server-2016?view=sql-server-ver15
- https://deep.data.blog/2013/07/03/sql-2014-in-memory-oltp-hekaton-training-videos-and-white-papers/
- https://sookocheff.com/post/databases/hekaton/
- https://web.eecs.umich.edu/~mozafari/fall2018/eecs584/reviews/summaries/summary14.html https://www.slideshare.net/InsightTechnology/dbts-osaka-2014-d35-hardware-hiroyuki-komori
- https://yizhang82.dev/hekaton
- https://docs.microsoft.com/ja-jp/sql/relational-databases/in-memory-oltp/in-memory-oltp-in-memory-optimization?view=sql-server-ver15
- https://15721.courses.cs.cmu.edu/spring2020/notes/02-inmemory.pdf
- https://www.youtube.com/watch?v=a70jRWLjQFk&list=PLSE8ODhjZXjasmrEd2_Yi1deeE360zv5O&index=3
- https://www.db-siken.com/kakomon/31_haru/am2_18.html
論文3について
Abstract
OLTP向けDBから標準的な機能であるログ、ロック・ラッチ、バッファマネージャを取り除いた場合、どの程度処理速度が向上するかを調査した論文。
感想とメモ
この論文に関してはかなりよく纏まった記事があったので、纏めることはしない。
バッファマネージャ、こんなに処理時間食うのかという感じだった。