SQLServer 2014 “Hekaton”再考 - 急がば回れ、選ぶなら近道

SQLServer2014「Hekaton」

MSの主要DB。論文がでているので、それをベースに自分の理解を書く。当然実装は公開されていないので、合ってるかどうかは知らない。また実際に製品にテストベンチを走らせたわけではないので、あくまで公表された論文ベースでの理解になる。まぁもう普通に使われているDBで、細かい機能云々についてはいろいろ資料がでているはず。そのあたりを見ればいいと思う。論文が公表されて、だいぶいろいろ手がはいっているとは思うので「アーキテクチャの設計」として読んでる。

■論文の構成
基本的に三つの構成になっている。全体の枠組み・Txの処理を詳細に記述したもの・およびその厳密な証明。このうち、全体の枠組みは、Tx処理詳細のあとで書かれているので、若干の不整合がある。これはIndex実装の追加の話なので、多分パフォーマンス向上のためにRange Indexを追加したようだ。トランザクション方式については変更はないように見える

Hekaton: SQL Server’s Memory-Optimized OLTP Engine
https://web.eecs.umich.edu/~mozafari/fall2015/eecs584/papers/hekaton.pdf

High-Performance Concurrency Control Mechanisms for Main-Memory Databases
http://vldb.org/pvldb/vol5/p298_per-akelarson_vldb2012.pdf

Addendum to “High-Performance Concurrency Control Mechanisms for Main-Memory Databases”
http://pages.cs.wisc.edu/~sblanas/proofsketch.pdf

■位置付け
2017年現在は大規模OLTPが開発競争中で、サーバ・アーキテクチャの大幅な変更（メニーコア化・ノードあたりのメモリー量の増大）を受けて様々な方式が検討されている。その中でHekatonはどちらかというと、旧世代の一番最後、というか新世代の一番最初のDB、というような位置づけになっている。この分野は毎年のように新方式・実装提案がされており、パフォーマンスレコードが常に更新される状態で、すでにHekatonはパフォーマンスでは最後尾に位置になってしまっている。最新の方式とはすでに最高で50倍近い差がでている。まぁ仕方がないところではある。

とまれ、商用DBではIn-memory/OCC/MVCC系をちゃんと実装しているので、そもそもどういう仕組みなのかはまとめておいたほういいので、そういう感じ。

個人的なフォーカスポイントと感想

■全体的な感想
よく頑張ってつくったな、とは思う。開発者の苦労がよくわかる。HekatonはSQLServerのDBEngineとして位置づけられており、外側の皮の部分や、一部利用可能な実装はそのままSQLServerを再利用している。これだけ大規模な商用DBだとおいそれと全面フルスクラッチというわけにもいかないので、あれやこれやレゴブロック状態だったと思う。最初からSQLServerがそういう作りを意図していれば、問題はないと思われるが、そんな風には見えない。開発陣は相当な妥協とストレスを押し付けられたのは想像に難くない。そのせいか、論文に時々支離滅裂な文言というか表現も散見されて、およそDBの学術論文とは思えないきわめてファニーな展開がそこかしこに香り漂い、味わい深い出来になっている。違いがわかるネスカフェゴールドブレンド。ぜひ、一読を勧める。（これだけいろいろと面白いDBの論文は過去に経験がない。）

論文を読む限りは「普通に普通のことを普通にやりました！文句ないですね！」という感じの4ドア・セダン・カローラという感じだ。パフォーマンスチューニング用のアーキテクチャ的な仕掛けは特に設定しているようには見えない。ので、普通に遅い。Foedus(OCC)にしろ、Cicada(MVCC)にしろ、パフォーマンスをあげるための仕組みをこれでもかのてんこ盛りで入れているのに比べると、淡泊というか、なにもしてないな、ぐらいには見える。Plain味・バニラ風味。まぁ2-3年前だとこんなもんだろうな、とは思う。逆に言うとここ数年の進歩がすごいということでもある。

トランザクション周りについて
Hekatonは新しいサーバ・アーキテクチャに対応する次世代のIn-memory MVCC/OCC型の商用DBだ。（現時点ではこれに対抗する商用DBはSAP-HANAだろう。本命のOracleはまだ登場していないが、もうそろそろ出てくると思う。）この意味で、どのようなトランザクション・ポリシーを持っているか、重要である。少なくと、商用とOSSでは装備の重さが違う。その意味では重装備だとこんな感じで、このポリシーでもある程度行ける、というのは情報としては重要で、その意味で整理しておきたい。

■ざっくりの構成

SQLServer2014は、従前からのSQLServer部分とエンジン部分のHekatonから構成されている。Hekatonは特にin memory用に特化したエンジンで、専用のtableやindexを持ちtransaction処理を行う。ストプロもサポートしている（Transact-SQL 以下T-SQL）。性能目標は従来からの10-100倍のパフォーマンスに設定されている。

基本方針は、Indexはオン・メモリー前提に設計・最適化し、ロックフリー(IndexとMVCC)が基本で、T-SQLでストプロ実行可能する、また、パーティションニングについてはコア単位でのパーティショニングはしない、大体こんな感じになっている。

■俯瞰的なアーキテクチャ構成
HekatonとSQLServer部分より構成されている

・Hekaton部分は以下三つから構成される
Hekaton storage engine : index+data HA/Recoveryのベース
Hekaton compiler：ストプロ関係
Hekaton runtime system：libその他

・元からあるSQLServer部分には以下の機能要素をもつ
Matadata/Security：Hekaton storageのメタデータ
Query optimization / Query processing :クエリー関連
Storage:永続化

まぁいろいろレゴブロック状態。

■Storage and Indexingについて
storageについては特に特記事項はない。従前の永続化の仕組みが前提で、NVMは視野にいれていない。
二種類のIndexをもつ。
・hash index　 lock free hash table
・range index Bw-tree ( lock free )

■クエリー周り
いわゆるT-SQLの実行計画についての改良がメイン。基本ステージングコンパイラ。流れは以下

・T-SQL -> Parser + Query Optimizer -> Query Plan
このあたりは普通にコンパイル（型とか名前処理）して、Query Plan作成。ここまでは今までのSQLserverをそのまま利用。

・Query Plan -> MAT
MAT=Mixed Abstract Treeでいったん中間的な表現に落とす。

・MAT + Metadata -> Pure Imperative Tree（PIT）
MATにHekatonのメタデータを追加的に利用して、具体的な実行計画に変換する。これはCへのコード変換のための準備も含むようだ。というかCへの変換用のIRっぽい。以下愚痴がいろいろ。
・CとT-SQLでは型システムとexpression semanticsが違いすぎる
・Date/Time type / fixed precision numeric type（decimalとかそんなんか）とかどうすんだよ
・NULL とかどうすんだよ
・arithmetic expression evaluation errorとかどうすんだよ
なので、PITを導入したようだ。Asakusaとかやってるとこういう話題は普通にあるので、社内では「心を無にして実装する」が基本スタンスだったりする。こういう愚痴を言ってるうちは魂のステージが足りていない。

・PIT -> Cのコードへ変換- > binary
んでバイナリーの生成

・Schema Compilation
テーブル情報のコンパイル。テーブルに対するコールバック関数を生成する。キーとレコートに対するhash関数とcompareの提供。レコードのlog bufferへのserial化を準備する。若干飛ばし気味に見える。

Instead, we collapse an entire query plan into a single function using labels and gotos to implement and connect these interfaces…By keeping all of the generated code in a single function, we avoid costly argument passing between functions and expensive function calls. Although the resulting code is often challenging to read due in part to the large number of goto statements…..ふむ。

■Transaction Management
商用の方は基本Multi-version(MV)になっている。論文では一応Single-versionも試験的に実装してベンチマークしている。MVでは、OCC-validationベースと、PCC-lockベースの両者が混載されている。

・MVCC
定義：a transaction is serializable if we can guarantee that it would see exactly the same data if all its reads were repeated at the end of the transaction
ベースはSIで、RFの維持ができれば、というざっくりした定義。

二つのスタイルを利用している
Optimistic : validationによる
Pessimistic : lockによる
Single versionのlockベース
実装としては3種類試している。

・Invariant
invariantは以下

1.Read stability
コミット時点でvisible versionがまだ見えていること。すなわちTがV1を読む時は、TのTx終了時点までV1はvisibleである。

V1は他のコミットされたversionでリプレースされない
これはread lockまたはvalidationで実装可能
SIをベースに考えていることから推測するとvisible versionはコミット済みのものに限定してると思われる

2.Phantom avoidance
コミット時点でvisible versionに追加がないこと。すなわち、Tが終了するまで、Tでのscanは追加されたversionは返さない

predicate指定の時にreadした対象が変わっていないこと
deleteはversionの追加扱い
これはscanされたindexとtableをロックするか、re-scanして追加がないかどうか確認することで実装可能

ちなみに下位のIsolationレベルは以下の通りで実装可能

repeatable read -read stabilityの保証でよい
read committed -単純に最新のコミットされたversionを読むだけ
snapshot isolation -Txの最初にversionを読めばおしまい

・Timestamps and Version Visibility
1. Logical Read Time (RT)
基本Txの開始時刻。どのversionを読むか、ということの決定基準。IsolationレベルがSIの場合は必ずTxの開始時点になる。

BeginTime/Commit/EndTime
各versionはBegin field (BF) とEnd field (EF) を持っている。
Commit/EndTime でserialization orderを決定する。

2. ステータス
各Txは以下のステータスを持つ
・active　Txを開始している。
・preparation　コミットの準備。Validation中。
・committed　コミット済み
・aborted　アボート済み

3. Valid Time
versionのvisibleな期間：begin timeとend timeの範囲
begin time = versionが作られたTxのcommit time。BFに格納される。
end time = overwrite(またはdelete)したversionを作ったTxのcommit time。EFに格納される。
Overwriteされていない場合はinfに設定される。

4. Readsについて
VersionのValid Time spanにRTがヒットした時に、そのversionを読む。
各versionのvalid timeは重ならないので、最大でも一つのversionがアサインされる。
読んだ時点のrtsは打たないので、誰が読んでいるかはわからない。

5. Updatesについて
versionをinstallして、そのTx-IDを当該versionと上書き対象のversionに書き込む
new version の BF にセット。まだ未コミット状態で書く。コミット完了時にcommit timeに書き換える。
old version の EFにセット。 Tx開始のロックの代わりに利用。コミット完了時にcommit timeに書き換える。
したがって、write-writeは早いほうが勝つ。なお、write中のconcurrentはリードは可能。

■OPTIMISTIC TRANSACTIONS
ロックを取らずにvalidationでconsistencyを保証する。

◆Transaction Phaseの詳細
0. Txの開始
TimeStamp (TS)の取得

1. 読むversionを決める
indexからversionデータを取りにいく。

1-1 versionが一番最初のケース：
先行するversionがないのでBFはTx-ID
Tx-IDが自分自身の場合はversionのステータスはactiveでEFはinf
Tx-IDが自分自身でない場合は、他のTxが書いている、かつ

その「他のTx」のステータスがpreparationの場合は、コミット準備に入っているので、自分は投機的に読みに行く。この場合は、BFにはそのversionを書いているTxのTSが書き込まれるはずなので、その書き込まれるTSと自分のRTを比較してvisibleかどうかテストする。

その「他のTx」のステータスがcommittedの場合は、コミットはされたが、まだBFにまだTSが書き込まれていない。なので、そのTSと自分のRTを比較してvisibleかどうかテストする。

その「他のTx」のステータスがabortの場合は無視する。

1-2 versionのBFとEFにTSがセットされてる場合
自分のRTが収まる範囲のversionを見つける

1-3 versionのBFにTSがセットされていて、BF＜RTであって、かつ

1-3-1 BF(TS)-EF(inf)の場合
普通に最新のversionを読んでいるので、それを読む

1-3-2 BF(TS)-EF(Tx-ID)の場合
要するに上書きが始まっているような場合、でかつ

後続のTx（Tx-IDをもつ）のステータスが、activeな場合
後続のTxのversionは読めないので、普通に前のversionを読む。

後続のTx（Tx-IDをもつ）のステータスが、preparationな場合
後続TxのTSがわかるので、そのTSと自分のRTを比較する。
RT < TSならば、前のversionのEFはTSで、すなわち、BF < RT < EF = TSなので、前のversionを読む
TS < RTならば、もし、次のversionがコミットされた場合は、前のversionはそもそもvisibleではなくなる。しかし、abortの場合は前のversionが読める。なので、次のversionが確定するまで、当該Tx (自分自身)をブロックすることがよいが、できるだけnon-blockingにしたいので、投機的に前のversionを無視し(speculatively ignore)、次のversionに当該Tx (自分自身)がcommit dependencyを持つようにする。

後続のTx（Tx-IDをもつ）のステータスが、committedな場合
単にTSの書き込みが遅れているだけなので、普通にBF＜EF=TS＜infで、どこにRTが落ちるかテストして、visible versionを確定する。

後続のTx（Tx-IDをもつ）のステータスが、abortedな場合
自分がEFを読んだ後で、全然別の他のTxが前のversionを更新するかもしれない。この場合は他のTxは自分がEFを読んだあとで、EFを更新してかつactiveでないといけない。この「他のTx」のend timestampは自分がEFを読んだあとになるので、RTよりも後になる。よって、仮に他のTxが更新するとしても、自分が読むversionは前のものになるので、問題にならない

2. 更新Txの場合

更新できるversionはEFがinfかまたは、Tx-IDの場合は、そのステータスがabortedである場合のみ。w-w conflictをさけるためにfirst-writer-win ルールにしている。書きに行く時にEFに自分のTx-IDを書き込む。

作り出した新しいversionのBFに自分のTx-IDをセット
前のversionまた削除versionのEFに自分のTx-IDをセット
コミットする場合はend TSを取得し、ステータスをPreparationに変更

3. コミット可能かどうか判断する
Validation and Dependencies
コミット時点で読み込んだversionが更新されていないか、そのversionがvisibleかどうか確認し、phantomが発生していないかもう一度indexスキャンをしてverifyする。

validationはまずTxのend-timestampを取得する。このend-timestmapでserialization orderを決定する。validationを行うために各Txはread set(読んだversionへのpointerのリスト)と再スキャンに必要な情報をもつscan setを持つ。このvalidationはコストがかかると思われるが実際はL1/L2キャッシュに乗っているので、そうでもない。（と論文では言っているが実際はabortが頻発すると乗らなくなって極端に性能が落ちると思う）

validation phaseにあるTxで作られた（または削除された）versionを読む場合は、そのTxに対するcommit dependencyをとる。よってそのTxがcommitされるまでcommitされないし、そのTxがabortされた場合はabortする。

commit dependencyを取る場合は、dependしてるTxに通知し、自身のdependency countを増やす。依存先がcommitしたら、dependency countを減らす。依存先がロールバックしたら自身もロールバックする。基本、commit dependencyがクリアされるまでウェイトする。またclientにも通知されない。

4. コミット処理
コミット可能なら新しいversionと削除versionの情報をredo logにして永続化層に書き出し。その後にステータスをcommittedに変更。各Tx-IDをend TSに変更（前のversionのEFと新しいversionのBF）する。
なお、loggingはredoログのみ。SQLServer tx-logに格納

5. abortならば、ステータスをabortedに変更
abortの場合はBFとEFのそれぞれをinfにセットして読めなくしてGCする。

6. Tx終了
古いversionをGC。visibleでないversionはGC対象となる。

◆Checkpoint
・二種類のデータで構成されている。
インサートされたversion情報(data stream)と、それに関連した情報や削除されたversion情報についての情報(delta stream) 。それぞれSQLServerのシーケンシャルファイルに格納される。
なお、index操作はlogされない。復旧時に再構築。

・transaction loggingはWALではなくSILO方式で、dirty dataは書かずにgroup commitを利用してredo logのみを保持する。Logの処理は並列処理を想定して作られているが、実際はSQLServerがsingle log streamのみしかもっていないので、ちょっとアレだが、まぁ今のところは効率が良いので十分だ、と論文には書いている。が、そんなわけないだろう。

・リカバリータイムの短縮のために以下の二つ手法を利用
Continuous checkpointing
処理がピーキーにならないようにしている
Streaming I/O
RandomI/Oを減らしてパフォーマンスを上げている

・Checkpoint Filesについて
data stream (data file)
特定期間でinsertされたversion情報を持つ。append onlyで書いていてクローズしたらリードオンリーになる。リカバリー時点でversion情報をリロードしてindexを張りなおす。この時delta fileでフィルターする。
delta stream (delta file)
data fileとone for oneでdeleteされたversionの情報をもつ。
dataとdeltaでペアで持つことでリカバリーの並列処理ができる。ので効率がよいと言っているがそうなのかとは思う。別に一緒に書いても構わない気もする。

■PESSIMISTIC TRANSACTIONS
基本的にリードロックをとる。ロックの仕組みは以下

1.Lock
Lock Typesは二種類。

Record Lock
更新・削除は最新のversionのみが対象になるので、最新versionのみにリードロックをとる。
EFにロック領域をもつ。64ビット。MVの場合はTSかTx-IDになるがこれを利用する。

ContentType(1bit)をとって0の時はTS(63bit)。1の場合は以下の構成
・NoMoreReadLocks(1bit) lockがこれ以上許容できないよflag （また、リードロックが全部はずれて上書きのwriteがコミットに行くときに後からリードロックが来ないようにセットするときにも使う）
・ReadLockCount(8bit) number of read locks。よって255並列
・WriteLock(54bit) このversionへのwrite lockをもっているTx-IDまたはinf

Bucket Lock (Range Lock)
Phantom用のロックでBucketLockSetで管理する。
BucketLockSetは以下で構成
・ロック対象のhash backetへのポインタ
・LockCount このbucketに対するロック数のカウンタ
・LockList　このbucketに対するロックを持つTx-IDのリスト

2. Eager Updates, Wait-For Dependencies
通常はリードロックに対するwriteはブロックされるが、これではスレッド・スイッチが発生してコストが高い。
なので、対象versionへのリードロックがリリースされるまでwriteのコミットを遅延させる。
先にwriteロックをとって、あとからリードロックがかかっても同じ。Bucketロックも同じ扱い。（wait-for dependency）

Dependencyのトラッキングの仕組みは以下
各TxObjがもつdependencyのデータ
・WaitForCounter　自分が待っている（incoming）Txの数
・NoMoreWaitFor もうこれ以上待てない数になったらフラグる
・WaitingTxnList　自身のコミットが待たれている (outgoing) TxのID

制御は簡単で、リードに行ったら普通にリードロックをとる。リードロックがかかっているversionを更新する場合は、writeロックをとってwait-for dependencyに入る。WaitForCounterがゼロになったらコミット。また、writeロックがかかっていても後追いでリードロック可能。write側はリードが済むまでコミットできない。

3. Dead lock
普通に起きるので、wait-forグラフをつくって検出する。個人的にはあまり役に立つ気がしないので、普通にtime-outでいい気もするが、wait-for dependencyの情報があるので、それを利用しているという感じか。

4. OPTIMISSTICとの違いは以下
・リード時点でロックをとる
・visibilityからのcommit dependencyは同じ
・コミット可能かどうかの判断はvalidationによるのではなく、単純にロックリリースがされているかどうかによる。

■Serializationの比較。
まずSerializationの証明について
Addendum to “High-Performance Concurrency Control Mechanisms for Main-Memory Databases”
http://pages.cs.wisc.edu/~sblanas/proofsketch.pdf

・Pessimistic
MV2PLであるという記述になっている。
The multi-version pessimistic (locking) scheme is in fact a MV2PL scheduler

そして、Tx本を引用しているが、間違っている。まずTx本の方はfinal stepでの処理を導入しているが、Hekatonの方は単純なロック処理になっている。ここは違う。ただし、Tx本でのfinal stepがwrite可能性の判断なので、意味は同じで手法が違うだけ。むしろ2PLのわかりやすさ、という意味ではHekatonの方式の方が圧倒的にわかりやすい。一番の違いは、Tx本の方はw-wは単純な待ちで終わるが、Hekatonはabortになる。同じではない。

・Optimistic
The multi-version optimistic scheduler behaves like a MVTO scheduler, with the changes described below
とあり、一応MVTOライクと言っていて違いは以下ということになっている。

Property 1: Timestamps are assigned in a monotonically increasing order, and each transaction has a unique begin and end timestamp, such that TxBegin < TxEnd.
Property 2: A given version is valid for the interval specified by the begin and end timestamps. There is a total order << of versions for a given datum, as determined by the timestamp order of the non-overlapping version validity intervals.
1と2でTSの保証と全順序。妥当だと思う。

Property 3: The transaction Tx reads the latest committed version as of TxRead (where TxBegin <= TxRead < TxEnd) and validates (that is, repeats) the read of the latest committed version as of TxEnd. The transaction fails if the two reads return different versions.
リードしたものの前に別versionが入ると失敗。

Property 4: Updates or deletes to a version V first check the visibility of V. Checking the visibility of V is equivalent to reading V. Therefore, a write is always preceded by a read:
if transaction Tx writes Vnew, then transaction Tx has first read Vold, where Vold << Vnew. Moreover, there exists no version V such that Vold << V << Vnew, otherwise Tx would have never committed: it would have failed during the Active phase when changing the end timestamp of Vold.
RMWしかwriteさせない。よって、そのリードは前述のリード条件と同じ、ということ。

Property 5: The transaction Tx logically writes at TxEnd, because the version is invisible to other transactions until TxEnd
concurrent writeのversionのvisibilityの定義

証明はほぼMVTOと同じ証明手法をそのまま利用している。Serializableであることには問題ない。
ただし、blind writeを認めていないため、MVTOよりもserializable空間は狭い。

■一般的なMVCC/CSRと比較してみる。
単純にconflictによる比較をする。（これは論文にはない）

MVCC（MCSR）
w-w not conflict : can commute
w-r conflict read from relation : cannot commute
r-w conflict only if w committed before r otherwise can commute

CSR
w-w conflict
w-r conflict
r-w conflict

HekatonOCC
w-w later w is aborted thus restrictive than CSR
e.g. w1(x1)w2(x2)c1c2 fails though in CSR committable
w-r conflict : read is determined as latest version or on the fly version and cannot commute
r-w conflict only if w is committed before r because it would updates version read by r
e.g. r1(x0)w2(x2) conflict in CSR and cannot commute but possible in HekatonOCC
w2(x2)r1(x0) に交換しても先にTx1がコミットしてれば成立するので、conflictではない

w-w more restrictive than CSR
r-w more relax than CSR
よってHekaton OCCはCSRと直交する。

HekatonPCC（Pessimistic）
w-w conflict : write lock but aborted
w-r conflict: read is determined as latest version or on the fly version and cannot commute
r-w conflict only if commited before r cause it would updates version read by r
r1(x0)w2(x2) conflict in CSR but possible in Hekaton w2(x2)r1(x0) r-read lock and write always has wait-dependency for read and delay thus commutable

w-w more restrictive than CSR
r-w more relax than CSR
よってHekaton PCCはCSRと直交

基本的にHekatonではOCCもPCCも同じ空間になっている。ただし、CSRよりも狭い部分もあれば、広い部分もあり、全体としてはMCSRには及ばない。通常のMVTOの空間にも及ばない。そもそもRMWしか認めてない段階で、concurrentな複数のsingle writeすらabortすることになる。ので、MVのコストを払った分のメリットをとるのは厳しい。

version linkにTx-IDを利用してwriteコンフリクトの蓋をするという段階でどうやってもconcurrent writeはabortは増える。これは小手先でどうにかなる問題ではなく、アーキテクチャ限界になる。読んでるversionの更新を許さないために、結果として不要なwriteのabortを発生させることになる。最近のメニーコア・大容量メモリーは容易にスループットが上がるため、abortのコストが相当高くなっている。ちょっとabortのコストを甘く見ていたかもしれない。本来MVCCのメリットは広いserialization空間によるabortの低減である。そのメリットがとれていない。その意味ではMVCCと言い切るには、個人的に無理があると思う。ただのMVだろう。これではsingle versionのOCCにはまったく勝てない気がする。まぁ、なんかパッチをあてて、write delayさせて・・・ということは緊急回避でできなくはないが・・

とはいえ、先人的な仕事としては非常に意味のある実装だし、論文だと思う。既存資産を引っ張った状態で、商用のin-memory MVCCに挑戦という意味では、ここまで詰めるだけでも相当なコストになるはず。そういう評価になると思う。