Zenn
🗂

Storage Replication

2023/11/14に公開
storage
tech

複数のNodeにデータを分散させる一般的な方法については、以下のような2つが存在する

  1. Replication
    • 同じデータのコピーを複数Nodeに保持する方法
  2. Partitioning(Sharding)
    • データをPartitionと呼ばれる小さなサブセットに分割する方法

本記事では、Replicationに焦点を当てて整理していく.

変更をNode間でReplicationするのに利用されているAlgorithmは以下の3つに分類される.

  • Single-Leader Replication
  • Multi-Leader Replication
  • Leader-less Repcalition

概要

Item Description
Replica Databaseのコピーを保存する各node
Leader Replica 書き込み/読み込みが可能なReplica(Primary Replica, Master)
書き込みが発生すると新しいデータをLocal Storageに書き込み、Replication Log or 変更Streamn一部としてFollower Nodeに連携
Follower Replica エンドユーザーは読み込みのみ可能なReplica(Read Replica, Secondary Replica, Slave)
Replication Log or 変更Streamを受け取り、Leader上で行われた処理を同じ順序で全ての書き込みを行い、自身の持つDatabaseのlocal copyを更新

上記のようなReplication処理をSupportしているDatabaseの一覧(全てではない)

  • PostgresSQL
  • MySQL
  • Oracle Data Guard
  • SQLServer
  • Aurora
  • MongoDB
  • RethinkDB
  • Espresso
  • Kafka
  • RabbitMQ

他にも多くのサービスでSupportされている

Leader / Follower (Primary/Replica)

Synchronous or Asynchronous Replication

一般的に、Replicationは高速で、更新をFollowerに1秒以内には適用できる.
(かかる時間が保証されているわけではない)

Sync Replication Async Replication
データの一貫性 Leaderと一致していることを保証 Replication Lagが存在するためLeaderと一致しないことがある
依存性 LeaderはFollowerの書き込みを待つ(データの一貫性)ため、Followerで障害が発生すると書き込み不可になる LeaderはFollowerの状態に依存せず書き込み可能
障害: Follower Replica Crush or Network障害などなど

そのため、全てのFollowerを同期的にすることは現実的ではない.(Replicaの中で1つのみを同期的Followerにするのが一般的)
かつ、同期型のFollowerが利用不可になる場合、同期処理が遅延する場合、同期型Followerを非同期にして、もう一方の非同期Followerを同期型に変える.(Semi-Synchronous)
このことで、2つのノードに最新のデータのコピーがあることを保証できる.

Node障害

Follower Nodeの障害 -> CatchUp Recovery

各FollowerはLeaderから受信したデータ変更ログをLocal diskに保持している
FollowerがCrushして再起動した場合、FollowerはLeaderに接続し、接続が切れた後に生じた全てのデータ変更を要求可能
それらの変更を全て取り込むことで、以前と同様にデータ変更のStreamを受付続けられるようになる

Leader Nodeの障害 -> FailOver

FollowerのいずれかをLeaderに昇格させる
クライアントは書き込み先を新しいLeaderに設定し、他のFollowerはデータ変更を新しいLeaderから受信する必要がある(=Failover)

  1. Leaderに障害が発生
    • 検知にはTimeoutを利用しているケースがほとんど
  2. 新しいLeaderの選出(以下のようなケースがある)
    最もLeaderに適当なNodeは最新のデータ変更に一番追従しているNode
    • 選定のプロセス(残っているReplicaの過半数によって選出)が走る場合
    • 事前に指定されているControllerNodeによって新しいLeaderが指定される場合
  3. 新しいLeaderを使用するためのSystemの再設定
    • Clientに新しいLedaerを認識させること
    • 他のNodeが新しいLeaderからReplicationさせるようにすること
    • 以前のLeaderが復帰した場合、古いLeaderを降格させ、新しいLeaderを認識させること
Leader Node Failoverにおけるよくある問題
  • Asynchronous Replicationを利用する場合、新しいLeaderは以前のLeaderに障害が発生した時点までの全ての書き込みを受信していない可能性がある
    • 一般的な解決方法は、古いLeaderの持つReplicationされなかった書き込みは破棄する(これは、クライアントから見た場合の永続性の期待に反する可能性あり)
  • 書き込みを破棄することは、特にデータベース外にある他のストレージシステムがデータベースの内容と連携していなければならない場合に危険
    • MySQL and Redisのデータに整合性が求められる場合など
  • ある種の障害では、2つのNodeが共に自身をLeaderだと判定してしまうことがある(Split Brain)
    • 2つのleaderが書き込みを受付、衝突を解決するプロセスがないことから、データの損失や破損が生じる可能性がある
  • Leaderが落ちていると宣言するまでに、どの程度のタイムアウトが適切か問題
    • Timeoutを短くすると、単純なNetwork遅延にも関わらず、不要なFailoverが起きる可能性がある
    • Timeoutを長くすると、復旧までに時間を要す

Replication Log Implementation

Statement-Based Replication

最もシンプルな方法は、
Leaderは全ての書き込みRequest(INSERT/UPDATE/DELETE Statement)をログに記録し、そのStatementをFollowerに送信する.
Followerは、受信したStatementをparseして実行する.

この手法は、以下のような点における問題点がある

  • NOW()/RAND()といった非決定的な関数を呼び出すstatementの場合、replica間で結果に差異が生じる
  • INSERT/UPDATE/DELETEは各テーブルの状態に依存して結果は異なるため、実行順序をLeaderと同じ状態に保証する必要がある
  • 副作用を持つstatement(trigger/stored-procedure/user-defined function ...etc)は、その副作用が完全に決定的なモノでない限り、replica間で異なる副作用をもたらす可能性がある

解決策としては、Leaderは非決定的な関数の呼び出しを記録する際に、確定した値をFollowerに連携することで解決は可能.
しかし、edge casesは数多く存在するため、他の手法が好まれる.

WAL(Write Ahead Log)-Based Replication

WAL(or REDO Log) を利用する手法

  • log-structured Storage Engine(LSM-Treeなど)の場合
    • このLogがStorageの中心となる
  • B-Treeの場合
    • ここのdiskのblockが上書きされるが、クラッシュがあってもindexが一貫した状態を回復できるよう、全ての更新はまずWALに書き込まれる

Oracle/PostgreSQLなどで利用されているが、以下のような欠点は存在する

  • WALは低レベルで記述していること
    • WALに含まれるのは、どのdick block中のどのbyteが変更されたのか、といった詳細

ReplicationはStorage Engineと密接な繋がりを持つことになり、
Database Storage FormatのVersionを変更した場合、LeaderとFollowerでそのDatabaseの異なるVersionを動作させられなくなる可能性がある.
なので、Database Storage FormatのVersionUpには、down timeを発生させる必要が出てくる.

Logic(Row Based) Replication

ReplicationやStorage Engine用に独立したLog Format(Storage Engineのデータ表現とは分離したログ)を使う手法

  • 挿入されたrowの場合、ログには全ての列の新しい値が含まれる
  • 削除された場合、ログには削除された行をuniqueに特定するのに十分な情報を保持
    • primary-keyないtableの場合、削除前の値を全ての列について記録する必要がある
  • 更新された場合、ログには更新された行をuniqueに特定するのに十分な情報とすべえての新しい値を保持

MySQLのbinlog(row-based replicationを利用するように設定された場合)の場合、このアプローチを利用される.

  • 論理ログはStorage Engineとは分離されているため、後方互換性を保ちやすい(replica間で異なるVersionを利用可能)
  • 論理ログフォーマットは外部Applicationにとってもparseしやすいため、データウェアハウスなどに連携するのに役立つ(変更データのキャプチャ)

Trigger-Based Replication

上記のアプローチ(Database Systemに実装される手法)とは異なり、Database Systemの実装から分離した手法

  • ユースケース
    • データの一部のみをReplicationしたい場合
    • 異なる種類のDatabase間のReplicationしたい場合
    • 衝突を解決するためのロジックが必要な場合

上記のようなケースにはReplicationの処理をアプリケーションレイヤーに引き上げる必要がある

  • トリガー
    • database system内でデータの変更が発生した場合に自動的に実行されるカスタムApplicationCodeを登録できる
      このトリガーを使って、データの変更を別テーブルに記録できるため、その内容を外部プロセスから読み出せる(これを外部連携する形)
  • Services
    • Oracle Databus
    • Postgres Bucardo
  • 問題点
    • 他Replicationに比べてOverheadが大きい
    • バグが生じやすい
    • 制約が生じやすい

ただ最も柔軟性のある構築が可能になる.

Replication Lag Problem

基本的には、Replicationは非同期的に行われるため(耐久性を保証のため)、最終的にFollowerが追いつき、Leaderと一貫した状態になる(= Eventual Consistency).
そのため、Replicationされるまでの間にLagが生じることを許容した構成になっていることが一般的である.

Replication Lagを許容するすることで、Replication Lagがユーザー影響を及ぼさないようにするため、
Read-After-Writeを保証する必要がある点には、気をつける必要がある.
(どの程度のread-after-writeを保証するかはapplicationが求める仕様次第で異なる)

  • Types of Read-After-Write
    • モノトニックな読み込み(monotonic reads)
    • 一貫性のあるプレフィックス読み取り(consistent prefix reads)

モノトニックな読み込み(monotonic reads)

モノトニックな読み取りは、あるクライアントがあるデータアイテムを読み取った後、そのクライアントが同じデータアイテムを再度読み取るとき、前回の読み取りよりも古いバージョンのデータを見ることがないことを保証すること.
これはShardingされたDatabaseで発生する問題.

一貫性のあるプレフィックス読み取り(consistent prefix reads)

一貫性のあるプレフィックス読み取りは、書き込みが順序どおりに行われる場合、読み取りもその順序に従って行われることを保証すること

types of read-after-write consistency

replication lagへの対処方法

結果整合性(Eventual Consistency)のSystemを扱う場合、Replication Lagが数分、さらには数時間にまで大きくなった場合のアプリケーションについても考慮しておくべき.
UXを良くするためにもどの程度のread-after-writeのような強力な保証を提供できるようにシステム設計をする必要がある.
実際には、非同期Replicationを同期的であるかのように実装することは、いつか問題が生じる.

そのため、Replication Lagが数分、さらには数時間にまで大きくなった場合でも問題のない実装をしておくことが重要.
例えば、ある種の読み取り(金額の読み取りなど)は必ずLeaderを利用するなど.

Multi-Leader Replication

得られるメリットが加わる複雑さを超えることがほとんどないため、Replicaがいくつかのデータセンター存在する場合に利用することがほとんど.

  • 障害に対する耐久性を保証するため
  • ユーザーと近くの距離にデータを配置するため

Multi vs Single比較の理解

Single-Leader Multi-Leader
Location 1つのデータセンターに配置 それぞれのデータセンターに配置
Performance High Latency Low Latency
全ての変更をinternetを通じてleaderのあるデータセンターに送るため それぞれのデータセンターにleaderが存在するため
データセンターの障害耐久性 Leaderのあるデータセンターに障害が発生した場合、他のデータセンターにあるFollowerをLeaderに昇格させる 各データセンターは他のデータセンターと独立的に動作し続ける
ネットワークの耐久性 信頼性が低くなる可能性あり 耐久性が高い

書き込みの衝突問題

異なる2つのデータセンターで並行して同じデータが変更されることもありえるため、書き込みの衝突が発生する可能性がある.
この問題は2番目の書き込みはBlockされるためSingle Leaderでは発生しない.(書き込むタイミングでlockして、先方の処理が終了(transactionが閉じられる)して書き込みが行われる)

multi-leader write colision

  • 例:
    • 自動インクリメントキー
    • トリガー
    • 整合性制約(Unique Key ...etc)

衝突の回避方法

基本的には衝突を自動解決することは難しく、この部分におけるbugが原因で問題となることが多い.
そのため、衝突を回避するような構成に取ることが最もシンプルな構成になる.

ユーザー単位でLeader Replicaを指定する ことでユーザーにとってはSingle-Leaderのような振る舞いをするため、
書き込みの衝突を避けることが可能になる.(地理的な距離に基づいて各ユーザーのLeaderが選出される形を取ることが多い)

一貫した状態への収束

Multi-Leader構成では、書き込みの順序がrandomになるため、最終的な値がどのようになるかについて定かでない.
そのためLeader1ではtitle=hoge, Leader2ではtitle=fugaの状態になることがある.
この状態を許容することはできないため、最終的にはReplica間でデータが同じになるようにする必要がある.

そのため、Databaseは収束する方法で衝突を解決する.(以下が具体的な方法)
※収束: 全てのReplicaが同じ最終地にたどり着くこと

  • それぞれの書き込みにUnique ID(timestamp, 桁数の多い乱数, UUID, key-value hash...etc)を与え、最も大きいIDを持つ書き込みを最終的な値となる(他の書き込みは廃棄)
  • それぞれのReplicaにUnique IDを付与して、IDの値の大きいReplicaから発行された値を優先する
    • このアプローチはデータロスの可能性あり
  • カスタムの衝突解決ロジックを作成する
    • どのように衝突を解決するかの仕様はアプリケーションの仕様に依存するため、衝突解決ロジックをアプリケーションコードで描けるようになっている
      • 書き込み時に実行されるHandler(高速に実行できる必要あり)
        • Replicationされた変更ログからDatabase Systemが衝突を検知するとHandlerが呼ばれる
      • 読み込み時に実行されるHandler
        • 衝突を検知した場合に、複数のVersionを返すようにするなど
  • 全ての情報を保存するデータ構造を明示的に持って衝突を記録し、後の何処か時点で衝突を解決するアプリケーションコードを書く

ネットワークの物理的または論理的な配置や構造(=Topology)

循環トポロジー

それぞれのNodeは1つのNodeから書き込みを受信し、それらの書き込みを他の1つのノードに転送する

スタートポロジー

ルートに指定された1Nodeが、書き込みを他のすべてのノードに転送する

All-To-Allトポロジー

最も一般的で、全てのLeaderが受け付けた自身の書き込みを他全てのLeaderに送る.
最も強い制約が求められる構成でもある.(衝突の回避or解決のため)

Types of Multi-Leader Replication

Leader-less Repliaction

Dynamo, Riak, Cassandra, Voldemortなどはこの手法を利用したLeader-Less Replication Modelを採用している.

書き込みのためのQuorum

n個のnodeがあるとき、書き込みは少なくともw個のnodeで成功されたものとみなされないといけない、読み込みの際には最低でもr個のnodeでqueryを実行しなければならない

n: total node数
w: write node数
r: read node数

  • w < nであれば、1つのnodeが利用できなくても書き込み処理は継続可能
  • r < nであれば、1つのnodeが利用できなくても読み込み処理は継続可能

通常読み書きは常にn個すべてのReplicaに並行に送信される.パラメータwとrは待たなければならないnode数を決定する.

  • Leader-Less 構成には FailOver は存在しない
  • 読み書きについて(1Down Replica, 2Active Replica, in total 3Replica)
    1. 書き込みを並行にすべてのReplicaに送信する
    2. 利用可能なReplicaは書き込みを受け付ける & 利用不可のReplicaはその書き込みを逃す
    3. 書き込みを承認するには3Replicaのうち、2Replicaが成功すれば十分だとして、書き込みを終了する
    4. 利用不可のReplicaがONLINEに戻ったときに、クライアントがそのノードから読み取りを始めると古いデータを参照してしまう
      • そのため、クライアントが読み取りを行う際に、リクエストを複数のノードに対して並列に送信することで最も新しいデータを参照するようにする(新旧比較にはVersion番号利用)

leader-less-replication

読み取り修復と反エントロピー

Replication Schemeでは、最終的にはすべてのreplicaにすべてのデータをコピーしないといけない.

  • 読み取り修復
    1. クライアントが複数のnodeから読み取りを行う
    2. 古いversionを検知した場合、クライアントは新しい値を書き込む

この手法は、頻繁に読み取られる値についてはうまくいくが、頻繁に読み取られない値については、新しい値に更新されない状態となってしまう.

  • 反エントロピー処理
    • Background処理にてreplica間の差異を探し、欠けているデータがあればreplicaから他のreplicaへコピーする(データストアによる)
    • 反エントロピー処理は書き込みのコピーは順序づけされていないので、データがコピーされるまで大きな遅延がある可能性がある

Discussion