ストレージシステムの事例

分散ストレージとは、Consistent Hashing、Paxos、Gossip などの用語を同じ図に並べることではありません。各メカニズムには明確な役割があり、システムの保証はそれらがどのように連携するかによって生じます。ここでは 2007 年の Dynamo 論文と 2012 年の Spanner 論文の設計課題を比較し、なぜ異なる組み合わせが選択されたのかを理解します。

ここで言う Dynamo は論文内の内部システムを指し、現在の DynamoDB 製品とは同一ではありません。同様に、Spanner の論文メカニズムは現在のサービスバージョンや分離レベルのドキュメントを代替するものではありません。先に 分散読み書きパス を読むと、以下のレプリケーション層とトランザクション層をより明確に区別できます。

ビジネス不変条件から比較を始める

2つのタイプのビジネスを想定します。ショッピングカートは、一部のノード障害時でも編集を受け付けることを望みます。口座振替は、引き落としと入金が同時に成立することを望みます。前者は競合後のマージを受け入れる可能性があります。後者は「まず両方が成功し、後でお金の出所を決める」という状況を通常受け入れません。

これは理解を助けるためのビジネスモデルであり、ある製品が特定のタイプのビジネスしか扱えないことを意味するものではありません。真の問題は、どの操作が独立して受信可能か、どの操作が確認前に調整を必要とするか、そして競合が発生した際に、正しいマージルールを提示する能力を持つのは誰かです。

Dynamo：競合バージョンを後続の調整に委ねる

論文内の Dynamo はキーバリューインターフェースを使用し、パーティショニングとレプリカ選択によってデータを分散させ、読み書きでは設定された数の応答を待ちます。ノードが一時的に到達不能な場合、ハンドオフとヒントの再生成によって対応します。複数のレプリカが同時に更新を受け付ける可能性があるため、オブジェクトバージョンとアプリケーション支援の競合解決はアーキテクチャの一部です。Dynamo 原論文 がこれらのメカニズムの根拠です。

ベクトルクロックは、すべてのバージョンに順序を与える整数ではありません。バージョン A が B をカバーする場合、B の履歴はすでに含まれているとみなせます。A と B が並行する場合、競合を保持するかマージを実行する必要があります。「ベクトルクロックの比較」を「最大の最新バージョンを取る」と簡略化すると、この設計で最も重要な分岐を見落とすことになります。

ショッピングカートのマージを例に挙げましょう。クライアント甲が本を1冊追加し、クライアント乙がペンを1本追加した場合、和集合は両方の追加を保持できます。しかし、乙の操作が本の削除だった場合、和集合は削除されたエントリを復元してしまう可能性があります。ビジネスで削除を優先する必要がある場合、現在の集合をマージするだけでなく、削除と因果情報を保持する必要があります。バージョン検出は、ビジネス上の競合がすでに解決されたことを意味しません。

「高可用性」でも、到達可能なノード数、ストレージ容量、障害ドメイン、回復条件によって制限されます。すべての候補ノードが到達不能な場合、データが何もないところから保存されるメカニズムはありません。マスターレスだからといって運用が簡単になるわけではなく、バックログの解消や競合状態の修復にも管理が必要です。

値のマージ後、「どのバージョンを見たか」というコンテキストもマージする

初期のショッピングカートには本があり、バージョンベクトルは (A=1,B=0) です。2人のクライアントがこのバージョンから開始します。A によって処理された更新はペンを追加し (2,0) になります。B によって処理された更新は本を削除し (1,1) になります。A 成分の方が大きいもの、B 成分の方が大きいものがあり、互いにカバーしません。

def dominates(a, b):
    return all(x >= y for x, y in zip(a, b)) and any(x > y for x, y in zip(a, b))

base = (1, 0)
left, right = (2, 0), (1, 1)
assert dominates(left, base) and dominates(right, base)
assert not dominates(left, right) and not dominates(right, left)
left_cart, right_cart = {"book", "pen"}, set()
assert left_cart | right_cart == {"book", "pen"}  # 和集合は削除された本を復元する

context = tuple(max(x, y) for x, y in zip(left, right))
merged_write = (context[0] + 1, context[1])  # A によって受け入れられたマージ書き込み
assert merged_write == (3, 1)
assert dominates(merged_write, left) and dominates(merged_write, right)
wrong_context_write = (left[0] + 1, left[1])
assert not dominates(wrong_context_write, right)
assert not dominates(right, wrong_context_write)

モデルは A、B の2つの成分を固定し、調整ノードが新しい書き込みに自分のカウントを追加すると仮定しています。ベクトルの切り捨てやノードの置換は含まれていません。ビジネスがマージ後の値を書き戻す際、左ブランチのコンテキストのみを伴う場合、新しいバージョン (3,0) は右ブランチ (1,1) と依然として並行状態になり、次の読み取りで依然として sibling が得られる可能性があります。値のマージと因果コンテキストのマージは、2つの作業です。

ここではビジネスに対して本が存在すべきかどうかを決定していません。削除優先を実現するには、操作または削除の因果情報を保持し、対応するルールを策定する必要があります。ベクトルマージを正しく行っても、ショッピングカートを正しくマージしたわけではありません。Dynamo 原論文の 4.1、4.4 節では、読み取り時の context を後続の put に戻すことで、更新が依存するバージョン履歴を表現しています。インターフェースとバージョンメカニズムの原文

Spanner：レプリケーション、トランザクション、時間がそれぞれ何を担当するか

Spanner の鍵は、3つの調整を区別することにあります。レプリカ間で永続操作の順序を決定すること、複数のデータシャードがトランザクションの結果を共同で決定すること、そしてトランザクション順序を外部で観察される時間順序に関連付けることです。古典的な設計では、Paxos、2フェーズコミット、TrueTime がそれぞれ異なる問題を解決するために使用されます。

古典的なクロスグループ書き込みトランザクションでは、参加グループはまず準備し、必要な状態を永続化し、コーディネーターがコミット決定とタイムスタンプを決定します。トランザクションはコミット待機条件を満たす必要があります。ログレプリケーションと待機は重複できるため、すべての段階を厳密に直列化された固定 RTT の合計として機械的に扱うことはできません。詳細なプロトコルは Spanner 論文 を参照してください。

TrueTime の鍵は明示的な不確実性区間

通常のクロック API は数値を返すため、呼び出し手がそれが正確な実時間であると仮定しがちです。TrueTime は実時間を含む不確実性区間 [earliest, latest] を返します。区間の幅は変動する可能性があり、ある測定で数ミリ秒の誤差しか出なかったからといって、すべての環境で固定の誤差定数があるわけではありません。

コミットタイムスタンプを s とした場合、「十分に大きいタイムスタンプ」を選ぶだけでは不十分です。成功を返す前に、実時間が s を超えたことを確認できるまで待機する必要があります。例えば TT.now().earliest > s を満たすまで待ちます。これにより、別のトランザクションが本トランザクションの完了を観察した後に開始した場合、そのタイムスタンプ選択が以前の完了順序と互換性を持つことができます。

タイムスタンプを未来に選んですぐに返すと、問題が残ります。別のノードがその後操作を開始する可能性がありますが、その時間区間は以前のタイムスタンプより前になる可能性があります。commit wait はこの不確実なウィンドウを排除するためにあります。区間が広いほど、待機時間が長くなる可能性があります。そのため、クロックインフラストラクチャは正しさの前提とレイテンシの両方に影響を与えます。

±5 ms の不確実性で、なぜ 10 ms を超える必要があるのか

意図的に簡略化した計算例を示します。実時間が t で、あるノードが常に [t−5,t+5]（単位：ミリ秒）を返すとします。t=100 のとき、コミットタイムスタンプ s=105 を取得し、参加者の準備時間などの他の制約がより大きな s を要求しないと仮定します。待機条件は t−5>105 であるため、t>110 まで待たなければなりません。100 からさらに 5 ms 待てばよいわけではありません。

def tt(real_time, epsilon):
    return real_time - epsilon, real_time + epsilon

s = tt(100, 5)[1]
assert s == 105
assert not tt(105, 5)[0] > s
assert not tt(110, 5)[0] > s  # 等しい場合でも厳密な after は満たされない
assert tt(111, 5)[0] > s

# T1 が t=100 で早期に返した場合、その後開始する T2 はより小さなタイムスタンプを選ぶ可能性がある。
s2_without_wait = tt(101, 3)[1]
assert s2_without_wait == 104 < s

# t=111 で返す場合、T2 が t=112 で開始すると、その上限は s より後になる。
s2_after_wait = tt(112, 3)[1]
assert s < 111 < 112 <= s2_after_wait

2番目のノードの区間 [98,104] も実時間 101 を含むため、「各ノードの誤差には境界がある」こと自体が 105、104 のような逆順序を防ぐわけではありません。コミット待機は、推論可能な連鎖を確立します。T1 のタイムスタンプは T1 が返す実時間より前です。T2 は返した後に開始するため、その後選択される有効なコミットタイムスタンプもさらに後でなければなりません。

レプリケーションが t=100 に開始し、t=108 に完了した場合、この整数サンプリングモデルではさらに 3 ms 待つだけで済み、2つの条件を通過する合計時間は 11 ms になります。レプリケーションの 8 ms と全体の待機時間 11 ms を足してはいけません。これは実際の Spanner のレイテンシ予測でもありません。実際の区間は変動し、タイムスタンプは他の制約によって引き上げられる可能性があり、ロック、調整、アプリケーションなどの段階もあります。論文では、commit wait と Paxos 通信が重複する設計について説明しています。Spanner コミットプロトコル

区間の上限を選んだ後、なぜ待つ必要があるのか

「タイムスタンプ選択からどれくらい待つのか」と「レプリケーション完了後もどれくらい待つのか」を同じ時間軸に置きます。下の図では t=100 で s=100+ε を取り、earliest=t−ε であるため、時間条件は Δt>2ε を要求します。整数ミリ秒サンプリングでは、最初に満たされる時刻は 2ε+1 ms です。これはレプリケーションの所要時間と大きい方を取りますが、足し算ではありません。この式は固定された対称誤差モデルに由来するもので、実際のシステムの固定レイテンシとして見なすべきではありません。

$$\Delta t_{\mathrm{return}}=\max (\Delta t_{\mathrm{replication}},2\epsilon +1\mathrm{ms})$$

外部一貫性とスナップショット読み取り

外部一貫性は、トランザクションが直列実行として振る舞い、外部で既に観察された順序関係を尊重することを要求します。T1 が完了した後に T2 が開始する場合、読者が T2 が T1 より前にあるかのようなトランザクション順序を観察させてはいけません。並行して重なるトランザクションについては、システムが有効な順序を決定します。

MVCC は、一貫したスナップショットを読み取るために履歴タイムスタンプを選択することを許可します。履歴読み取りは古い状態を返すことが明確なセマンティクスであり、レプリカのランダムな遅延による不整合を意味するものではありません。強い読み取りと履歴読み取りを1つの約束事に混同してはいけません。現在の Spanner の外部一貫性の説明と分離レベルの適用範囲は、TrueTime and External Consistency を参照してください。

どのように比較するか、システムを2列のラベルに圧縮しない

「Dynamo は速く、Spanner は遅い」と書くよりも、より意味のある比較は以下の通りです。

• 操作が複数の key、パーティション、またはリージョンを跨ぐ場合、どの調整境界を通過するか。
• 成功応答の前に、どのレプリカ、トランザクション状態、時間条件が確認されたか。
• どのような並行競合が許可され、マージを誰が担当し、どのビジネス不変条件を一時的に破ることができないか。
• 障害時にどの読み書きが継続可能か、回復後に一時的なバージョンと遅延レプリカをどのように処理するか。
• クライアントが明示的に古い読み取り、トランザクション分離、地理的配置を選択できるか。

レイテンシはレプリカの距離、負荷、プロトコルパスに依存し、運用コストは修復、容量、アップグレード、障害処理に依存します。2つの論文は再利用可能な設計アイデアを提供していますが、すべての現代データベースに適用できるパフォーマンスランキング表ではありません。

参考

• Dynamo，SOSP 2007
• Spanner 論文および拡張バージョン
• Spanner：TrueTime と外部一貫性
• 反熵とデータ修復
• 時間とクロック

キーワード：Dynamo、Spanner、並行バージョン、Paxos、2PC、MVCC、TrueTime、commit wait、外部一貫性