Transactional Information Systems 第９章 演習問題解答
Transactional Information Systemsにおける第９章演習問題の自分なりの解答。
間違っていたらご指摘ください。
9.1
Q
インクリメンタルなキー範囲ロックは、ユニーク制約を持つインデックスに対してはどう変更されるか？
A
基本のインクリメンタルキー範囲ロックは変更なくユニーク制約インデックスにも適用できる。Insertどうしが競合するようにすればよい。
instant duration lockとinsert lockを用いた最適化を適用する場合は、insert lockどうしが競合するように設定する。唯一値しか許容されないため、競合が検出された時点でそのinsertは諦める。
9.2
Q
インデックスに存在する最小のキーよりもさらに小さいキーの検索にはどのようにロックを取得すればよいか、またそのようなキーのInsertとのロック競合をどのように保証するか？
A
インデックス内の最小のキーよりもさらに小さいキーをinsertしたいとき、このままだと直前の葉が存在せず、適切なロックができない。
従って、どの値よりも小さい最小の葉を番兵として最初から配置しておくことにする。こうすればInsert時にもSearch時にもその葉へのロックが要求されるため、正しく競合が検出される。
9.3
Q
存在していないキーのInsertどうしは競合してブロックを生じうるが(例：27も28もインデックスにないとき、先のInsert(27)は後のInsert(28)をブロックする)、本来可換なはず。この競合を避けるための方法はあるか？
類似する状況におけるDelete/DeleteどうしやInsert/Deleteについては？
A
Insertの際、挿入するキーにinsert lockを、直前のキーにinstant duration lockをかけることにする。 また、Deleteの際には、削除したいキーのみにwrite lockをかけることにする。
- 直前のキーへのinstant duration lockは一瞬しかロックをかけないので、2つのInsert操作の間にブロックは起こらない。
- Deleteは削除するキーにしかロックをかけないので、異なるキーの削除は互いに競合しない。
- Insert-Deleteについても、全く同じ理由で互いに競合しない。
9.4
Q
ユニーク制約のあるインデックスでのInsert時に、キーが既に存在して失敗する場合のロックの要件は？
A
insert lockどうしが競合するように設定し、insert lockどうしの競合が検出された時点で失敗と判定する。
9.5
Q
直前のキーでなく、直後のキーへのロックを考えた場合のロック規則はどうなる？
A
- search(x)は、xがインデックスに存在すればxに対するread lockを要求する。なければ、xより大きい中で最小のキーに対するread lockを要求する。
- next(currentkey,currentpage,highkey)はcurrentkeyの直後のキーに対するread lockを要求する。
- insert(y,RID)は、yとyより大きい中で最小のキーに対するwrite lockを要求する。
- delete(y,RID)は、yとyより大きい中で最小のキーに対するwrite lockを要求する。
9.6
Q
図を用いた問題なので問題文略。
A
アクセスレイヤでのロック手順を最初に答える。
はじめに11の直前のキー9にread lockをかけ、9→12→13→15→16→17→20→22→24という順に進む。 次にInsertの際には、27の直前である24のロックがwrite lockに昇格される。
次にページレイヤを考える。
根からr→p1→q3とread lockを順にかけ、順次親のロックを解放しながら下りていく。q3が終わったらq4へ、次にq5へ、最後にq6の最小キーが25より大きいことを確認して範囲検索は終了する。 次にInsertの際には、r→p2→q6という順にwrite lockをかけ、順次親のロックを解放しながら下りていく（全部split-safeなので開放しても問題ない）。q6はwrite lockに昇格される。
9.7
Q
B+木において、pがsplit-safeでないが、その子孫qがsplit-safeであるケースを考える。pもqもあるInsert操作のパス上に含まれていた時、lock couplingテクニックでは、ロック競合を最小化するため、ロックをどう取り扱えばよいか？
A
ノード分割は、split-safeでない親に向かって伝播していくが、split-safeなノードが一つ挟まった時点で伝播は止まる。したがって、qの子孫でノード分割が起きたとして、その影響はq以下にしか及ばない。よって、qへのロックを獲得した時点で、qよりも上のノードは全てロックを解放しても問題ない。もちろん、そのようなsplit-safeなノードに出会うまではpのロックは保持しておく必要がある。
9.8
Q
link techniqueのロック獲得規則をフォーマルに記述せよ。
A
link techniqueの前身となるlock coupling techniqueのロック獲得規則は以下であった。
- searchとrange_searchは、ノードにアクセスする際、そのノードへのread lockを必要とする。insertはwrite lockを必要とする。
- search, insert, およびrange_search冒頭の根から葉への降下において、ノードへのロックが許可されるのは、そのノードがフリーかつ、そのノードの親のロックを保有している場合のみである。
- searchは、子へのロックを獲得したとき、親のロックを解放してもよい。
- insertは、(a)子へのロックを獲得し、(b)そのノードがsplit-safe(キーをもう一つ足しても分割が起こらない) なときのみ、そのノードへのロックを解放してもよい。
- range_searchが葉ノードへのロックを許可されるのは、その親ノードか直前の葉へのロックを保持している場合のみである。前者は冒頭の根から葉の降下に、後者はnext操作による葉の連鎖に関連する。
- next(currentkey, currentpage, highkey)はcurrentpageへのread lockを必要とし、直前の葉へのread lockを保持している場合に許可される。
searchやrange_searchはノード分割が並列に起きても問題なく実行されるという観察を踏まえた最適化がlink techniqueであり、以下のようになる。
- searchとrange_searchは、ノードにアクセスする際、そのノードへのread lockを必要とする。insertはwrite lockを必要とする。
- insertにおいてノードへのロックが許可されるのは、そのノードがフリーかつ、そのノードの親のロックを保有している場合のみである。
- searchは、子へのロックを獲得したとき、親のロックを解放してもよい。
- insertは、(a)子へのロックを獲得し、(b)そのノードがsplit-safe(キーをもう一つ足しても分割が起こらない) なときのみ、そのノードへのロックを解放してもよい。
- next(currentkey, currentpage, highkey)はcurrentpageへのread lockを必要とする。
9.9
Q
B+木の葉ノードが双方向に接続されている状況を考える。これはキーを降順に範囲検索するのに便利。
このとき、ページレベルのlock couplingやlink techniqueはどのような影響を受ける/変更されるか？
A
まず、link techniqueは葉のリンクが昇順にしか辿られず、新しいノードも同じ方向にしか作られないという性質に基づいた最適化なので、双方向のリンクがある場合には適用できない。
次にlock couplingであるが、
