論文メモ ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Aherad Logging

March 21, 2021

ARIES/IMは、B+木への直列化可能性のある並行処理とログ先行書き込み(Write-Ahead Logging, WAL)による復元を実現する。 ARIES/IMのベースには、先行研究のARIESがある。 復元手順は、平行処理の違いによる差異はあるものの、ARIESと大きく変わらない。 キーの参照先にあるデータのレコードとキーを同じロックで保護したり、ロックの代わりにラッチを使ったりすることで、ロックの頻度を下げ、B+木の高速化を実現する。

B+木のキーは、データのレコードを特定するレコードIDとkey valueのペアを意味する。 キーにロックをかけるときは、キーそのものではなくレコードIDの指すレコードをロックをかけ、前段落で述べた通り、同じロックでデータレコードとキーを保護する。 ページの保護には、ロックの代わりにラッチを使う。 3つ以上のインデックスのページが同時にラッチを獲得することはない。 木を探索するときは、親ページにラッチをかけた上で子ページへのラッチを要求し、ラッチを獲得できたら親のラッチを解放する。

木の構造を変える挿入、削除の操作は、Structure Modification Operations(SMO)とよばれる。 SMOによってページにあるキー数がページのもつべきキー数の範囲外になると、ページの分割や削除が必要になる。 ページの分割や削除は、キーの挿入や削除と同じトランザクションで行われる。 デッドロックを避けるためにラッチは下層にあるラッチを解放してから、上層のラッチを解放する。

ページに対するラッチに加え、B+木自体に対するラッチがあり、これは直列化可能性のためにSMO時に使われる。 葉にSMOを適用する直前に、排他ロックでB+木にラッチを適用し、上層へのSMOの伝搬が終わるとラッチは解放される。

論文をこちらからダウンロードできます。