我读了《数据驱动应用设计》第二部（分布式数据）

2 年 ago

科, 颖

3 minutes

因为阅读了，所以留下了个人备忘录。
此备忘录不是详尽无遗的。

? 5~9章「データ指向アプリケーションデザイン」第 II 部 (分散データ) を読んだ

10~12章「データ指向アプリケーションデザイン」第 III 部 (導出データ) を読んだ

因为我读过了，所以留下一些个人的备忘录。
并不是详尽无遗的备忘录。

第五章复制

数据复制的好处

(読み取りクエリを処理するマシンをスケールアウトさせられ)スループットを高められる

几乎所有的数据库都使用以下其中一种算法来在节点之间复制变更。

リーダーレス

5.1 单一领导者(Note: This paraphrase assumes the phrase “シングルリーダー” is referring to a single leader in a specific context, such as a team or organization.)

PostgreSQL、MySQL、MongoDB、Kafka、RabbitMQ等都是常用的数据库及消息队列工具。

这些都是复制品

writeを受け付ける。新しいデータをローカルストレージに書いたあと、フォロワーに送信する(=レプリケーション)
readを受け付ける。

残りはfollower (= read replica = slave = secondary = hot standby)

readを受け付ける。

在中文中的表达：

复制是一个过程，通过该过程可以制作出与原物相似的副本。

フォロワーでデータ更新がコミットされるのを確認してからマスターで更新がコミットされる。
?️(書き込みしたクライアントから見て？)フォロワーが持っているデータは常に最新でありリーダーとの一貫性が保障される

非同期的

?️クライアントに成功が返された場合でも書き込みの永続性は保障されない。

例えば、書き込んだ直後のリーダーに障害が発生し、その更新が反映された他のレプリカがfail overによってリーダーになった場合。

フォロワーが多い場合やフォロワーが地理的に分散している場合に広く利用される。

同一的数据库中，可以根据追随者的选择来选择同步或异步模式。
常见的做法是针对多个追随者中的一个进行同步复制，如果速度下降，就将另一个追随者之一切换为同步模式。
?可以在不加锁的情况下对整个数据库进行快照。对于MySQL，需要使用第三方工具innobackupex。
?数据库的状态被分配了一个版本ID。对于PostgreSQL来说是日志序列号，而对于MySQL来说是binlog coordinate。

对节点故障的应对措施

(障害 = クラッシュして再起動や、リーダーとのネットワークが一時的に切れる)
?️ フォロワーは自力でキャッチアップリカバリーによって復活する。(保持しているデータ変更のログを使う + リーダーにキャッチアップ)

リーダーの障害

?️フェイルオーバーを行う。

(リーダーはリーダーとして復活することはない)
フォローのいずれかをリーダーに昇格させる
フォロワーたちはデータ変更を新しいリーダーから受信しはじめる

自動的なフェイルオーバーと、管理者による手動のフェイルオーバーがある。

自動だとフェイルオーバーの検知でフォースポジティブが発生しうる。(システムの高負荷やネットワークの問題でタイムアウトが発生した場合に、これがリーダーレプリカの障害と見なされる可能性がある)

关于自动故障转移

リーダーに障害が起きたことの確認。タイムアウトを利用して検知することが多い。
新しいリーダーの選出。

最もふさわしい候補は、それまでのリーダーのデータ変更に一番最近まで従事していたレプリカ
選出方法は

残っていレプリカによる選出で行われる
コントローラーノードが指定することもある。

システムの再設定

クライアントの書き込みを新しいリーダーに送信するように設定
フォロワーは新しいリーダーを新しいリーダーから受信する(ように設定？)

在故障转移中可能发生的问题

スプリットブレイン(複数のレプリカが自分をリーダーと信じている状態)が発生しうる。

领导者基于的复制方法

リーダーは書き込みリクエストをログに記録し、そのステートメントログをフォロワーへ転送する。
?️ NOW() や乱数などの非決定的な関数を呼ぶステートメントは破綻を呼ぶ。
?️インクリメントするidがテーブル内に振られている場合、実行順序が影響する。→ レプリカ上でも実行順序を合わせる必要がある→複数のトランザクションをserializableに実行する必要が生じる

write-aheadログの転送

リーダーがログファイルへの書き込みのかたわら、ネットワーク経由でそれをフォロワーにも送信する
?️リーダーとフォロワーのストレージフォーマットを統一する必要がある → 場合によりデータベースのアップデート時にダウンタイムが発生する。

論理ログ(rowベース)を使用したレプリケーション

レプリケーション用の独立したログフォーマットのログ(論理ログ)を使用する
?️論理ログのフォーマットは後方互換性を保ちやすい
?️論理ログのフォーマットは外部のアプリケーションがパースしやすいので、外部に送信してそこで使用(= 変更データのキャプチャ)できる

トリガーベースのレプリケーション

アプリケーション側のコードを使用する。
例えば、

データベースのログを読み取るツールを使う
RDBのstored procedureを使い、別のテーブルにデータの変更を書き込む。これをフォロワーが読む。

?️柔軟性が高い。
?️オーバーヘッドが大きい。バグが発生しやすい。制約が生じやすい。

与复制滞后相关的问题

由于分散性，不可能完全同时对多个节点进行更新。结果就是会出现问题。

以下是三个由于异步复制的复制滞后而引起的问题。对于每个问题，介绍了在领导者基础上采用异步复制的保证方法（这些繁琐的保证方法是事务存在的意义，可以使应用程序摆脱这些麻烦的保证方法）。

原因: read時にまだ、followerレプリカに変更が反映されていたい。
保障:これが発生しないように保障されている状態を「read-after-write consistencyが保たれる」と呼ぶ。リーダーベースで非同レプリケーションの場合の実現方法は、

自分が更新したデータのreadは leaderレプリカから読み取る
データの更新時刻を記録するようにする。最後の更新時刻から例えば一分以内に行うreadはleaderレプリカから行う
followerレプリカのレプリケーションラグをモニタリングし、一分以上leaderから遅延しているレプリカからはreadを行わない。
clientは最後の書き込みのタイムスタンプを保持する。そのタイムスタンプまでの更新が反映済みのレプリカからしかreadを行わない。

問題② あるクライアントによってあるレコードがwriteされたとする。この時、他のあるクライアントにとって1回目のreadではAが見えるが、2回目のreadではAが見えない。

原因: 1回目と2回目で異なるfollowerレプリカを見ており、前者には変更が反映されているが後者には変更が反映されていない。
これが発生しないように保障されている状態を「monotonic readが保障される」と呼ぶ。リーダーベースで非同レプリケーションの場合の実現方法は、

あるユーザーのリクエストによるread先のレプリカを常に同じものにする。例えば、user id のハッシュ値によって決める。

問題③ 他のクライアント(たち)によってA→Bの順にレコードが書かれたとする。あるクライアントのread時にAは含まずBだけがreadできてしまう。

原因: leaderレプリカが複数ある、例えばシャーディングされたDBで問題になる。最初にreadしたfollowerレプリカにはAの変更が反映されていなかったが、後者にはBの変更が反映されていた。
これが発生しないように保障されている状態を「consistent prefix が保たれる」と呼ぶ。リーダーベースで非同期レプリケーションの場合の実現方法は、

因果関係のある書き込みは同一のleadレプリカに対して行う。

5.3 多主复制

由于在单一数据中心内的利益较少，因此很少被使用。

(複数ロケーションによる)availabilityの改善はなし

即使在多读取器复制中，使用同步复制并没有太多好处。

?️ 同期的に衝突を検出したいのが目的なら、シングルリーダーレプリケーションを使うべし。

在多数据中心中

同一データセンター内のfollowers
他のデータセンターのleader (ここで別の変更が行われていた場合、書き込みの衝突⭐の解決が必要)

?️ 以下と合わせて問題になりうる。よって可能であれば避けるべきと見られることも、

自動インクリメントのキー
DBのトリガー
DBのconstraint

使用例として、オフラインでも使用できるカレンダーアプリ。デバイス内、リモートサーバー内のそれぞれにリードレプリカを持っていると解釈できる。

每个领导者副本都有关于冲突的自己的想法，并在更新历史中持有其他领导者收到的副本。当满足以下所有条件时，我们可以说发生了冲突？（版本向量可以实现这一点吗？）

それらのコミットが同じレコードに関するものだったり、アプリケーションロジック上片方しか許容できない

我觉得仅仅给更新添加时间戳是无法检测到冲突的。

5.4 无主复制

dynamo db を含むdynamo スタイルのDBは使用している。
cassandra (dynamo dbに影響を受けた)

適する状況

高可用性と低レイテンシーが求められ、時折古いレコードが読まれることが強要される場合。
マルチリーダーレプリケーションと同様、マルチデータセンターでの使用に適している。

実装方式は色々

?クライアントが書き込みを自分で複数のレプリカに送信する
coordinator nodeが各レプリカに送信する

在本书中，解释了一种名为“Quorum写入/读取”的绿色无领导副本复制算法。它的原理是，在存在 N 个副本时，将 w 和 r 设置为满足 w + r > N。

読み込み時には、最低r個のレプリカからの読み取りを必須とする

額外说明，仅部分复制品中的更新将按照以下方式传递至所有复制品。

= クライアントが複数のプロセスから読み出した際、最新の書き込みバージョンを持つレコードの値をそうでないレコードの値に上書きする

半エントロピー処理

= バックグラウンドプロセスによるレプリケーション。

关于w和r的设置、

N <<< w + rの時、古い値を読み取ってしまう可能性が高まる。-> 衝突の解決が複雑になる？

有关并行写入

「あるレコードXに対して二つの書き込み操作があり、X->AとX->B である時、(AのヒストリーにBが含まれていない) && (BのヒストリーにAが含まれていない) の時にこれらは並行な書き込みと言える(?)
並行な書き込みの解決方法
レプリカが一つの場合

サーバー側とクライアント側のそれぞれで、「あるレコードのバージョンヒストリー」を保持しておく。クライアント側で書き込み時にはまずサーバー側のバージョンヒストリーを読み出す。もしもそこに自分にないバージョンが含まれていることを検知したら、次の書き込みバージョンは所謂マージコミット的な変更になる。

マージのアルゴリズムは、色々。アプリケーション層での実装例としては、

タイムスタンプを見て新しいバージョンを採用。
変更を比較して和集合を取る。(appendの変更しかない場合に有効)

レプリカが複数の場合

バージョンベクトルを使用するなどする。

?Cassandra是受到 Dynamo DB 启发的无服务数据库。

第六章划分

分割的目的是为了可扩展性。（每个节点可以独立地查询其拥有的分区）

这一章中将要说明的内容如下。

DBのリクエストを適切なパーティションにリクエストするルーティング

在某些分区中，记录的分布不平衡被称为Skew，而将出现这种情况的分区称为hot spot。

索引的方法

?️ そのキーによるrangeに対するスキャンが容易になる
?️アクセスパターンによってはホットスポットが発生する
ダイナミックパーティショニングを行う(❌パーティション数固定はだめ。それぞれのパーティションの範囲を事前に決めると、偏りが発生することがある)

キーのハッシュ値の範囲に基づく

⚠️ハッシュ値のmodで切るのはNG (リバランシングの負担が極めて大きくなる)
?️ホットスポットを避けれる
?️rangeによるqueryはすべてのパーティションに送られ、結果をマージする必要がある

複合キーを作成する

以下。

分区和次要索引

プライマリーキーのハッシュ値によりパーティションを決定。
各パーティション内で、セカンダリーキーによるインデックスを貼る(ローカルインデックス)

通常セカンダリインデックスは特定の値を検索する方法

由此产生的结果

パーティション内でセカンダリーキーによるrangeのqueryのパフォーマンスが良い。

然而，基于二级索引的搜索读取将变成对所有分区进行散列与合并的过程。

?️ セカンダリーキーによる検索時に、どのパーティションを見に行く必要があるか分かる。
?️ 書き込み時にこのインデックス更新するために低速で複雑になる

なお、Dynamo DBではこのインデックス更新は非同期で行われる。

重新平衡分区

解釋如何從一個集群節點將負載轉移到另一個節點的過程。

?再平衡战略

ノード数よりはるかに多くのパーティションを作成しておき、１つのノードに複数のパーティションを割り当てる。あるノードの負担が大きくなったら新たにノードを増やし、既存の全てのノードからパーティションを盗む。

リバランシングの最中は古いパーティションに対する読み書きが行われる
?️ パーティションを増やせないため、データ量増加によりパーティションのサイズが巨大になりうる。すると、リバランシングやノード障害からのリカバリの負担が大きくなる。

dynamic partitioning

パーティションのサイズが閾値より大きくなれば分割。小さくなれば他とマージする。
?️ パーティション分割、マージしたあとも、キーの範囲は

ノード数に比例するパーティショニング

ノードごとのパーティションの数を固定する。データが増えたら新しいノードを加え、既存の全てのノード内のパーティション(それぞれ１つ？)のレコードを盗んでくる？？？

?资产再平衡操作

?️ 例えば、あるノードが過負荷でリクエストのレスポンス処理速度が落ちたとする。結果、他のノードがこのノードが落ちたと見なしてリバランシングを開始した場合、さらなる負荷がかかる。

手動のリバランシング

(処理のどこかに人を介在させるのがおすすめ)

绿色-请求的路由使用服务发现。用于解决包含特定键记录的分区所在的节点。映射的存储位置为。

各ノードそれぞれ

无论如何，这些都是引用诸如Zookeeper的集群管理服务所持有的映射。每个节点在进行重新平衡时会向其发送更新。

第七章交易

长篇累牍地总结了一番，P288的总结非常精炼。

交易所提供的安全保障

commit all .or. abort al
DBの特性

Consistency (一貫性)

アプリケーションが満たさなければならない不変性。
アプリケーションによって異なる。例えば会計システムの場合、全てのアカウントでまとめると常に貸方と借方は等しい、など。
DBの性質ではなくアプリケーションの特性

Isolation

並行して実行されたトランザクションがお互いから分離されていること
複数のレベルがある

serializable level
snapshot isolation level
read committed level

DBの特性

Durability (永続性)

トランザクションが成功したらそこで書き込まれた全てのデータが失われないこと
DBの特性

顺便提一下，接下来出现的同一个词汇被用于多种含义中，导致了困惑。

整理”原子性”和”一致性”的意义

In ACID, commit all or abort all
In multithreaded programming,ある処理の途中に他のスレッドから途中の状態が見えないこと (ACIDでこれはisolation)

Consistency

In asynchronous replication, 結果整合性
In CAP, 線形化可能性 (9.2章に詳しい)
IN ACID, データベースが「良い状態」にあることを表すアプリケーション固有の概念

在应用层中重试失败的事务，而不是在数据库内部重试的问题点。

? アプリケーションレベルでの重複排除仕組みが必要

失敗がDBの過負荷によるものだった場合、リトライは状況を悪化させる

? リトライの回数を制限する。exponential backoff を行う。過負荷に関するエラーは他のエラーと異なる対応をする。

トランザクションがDB外に副作用を持つ場合がある。

? 複数のシステムをまとめてコミットするにはtwo phase commitが使えるかも

クライアントのプロセスがリトライ中に落ちたらそのプロセスがDBに書こうとしたデータは失われる。

以后是关于孤立的话题。

读取提交级别

ダーティーリードが発生しない = 他のトランザクションの未コミットの変更は見えない
ダーティーライトが発生しない = 他のトランザクションの未コミットの変更を含むオブジェクトへの上書きができない

実装方法

ダーティーリードが発生しない

? オブジェクトごとに、書き込みトランザクションに関して、コミット前の古い値と、コミット予定の新しい値の両方を保持する。トランザクション進行中のオブジェクトの読み取り時には、古い値を返す
❎ 読み込みをするトランザクションはそのオブジェクトの行ロック⚠️を取得する、だとパフォーマンスが悪い

ダーティーライトが発生しない

? 書き込みをするトランザクションはそのオブジェクトの行ロックを取得する。

可能发生死锁。

快照隔离级别

这也满足了“读取提交”的保证。

non repeatable read が発生しない = トランザクションが読み取るデータは、全てそのトランザクション開始時にDBにコミット済みのもののみ。

⚠️ これは各オブジェクトのバージョンではなく、読み取り時のテーブルのバージョン、と捉えるべき。別のトランザクションが走っているとして、「レコードAの読み取り後にそのトランザクションが完了して、次のBの読み取り時にそのトランザクション反映後の新しい値が返される」のは、non repeatable read である。
non repeatable readは、DBのバックアップ時や、実行時間の長い分析クエリ時に問題になる

それぞれのDBにおける呼び名

Oracleでは、Serializable level (がこれを満たす中で最も制約が弱いレベル)
PostgreSQLでは、repeatable read
MySQLでも、repeatable read

実装方法

書き込みロック + MVCC(multi version concurrency control ?)を用いる。
読み込み時には、トランザクション中ずっと同じスナップショットから読み取りを行う。

?読み取りが書き込みをブロックすることはなく、書き込みが読み取りをブロックすることもない

インデックスは、単純にオブジェクトの全バージョンを指しておき、見えないバージョンは無視する。(実際は色々 P.261)

以下是用于读取一致的快照的实现方式。（保存每个快照会导致性能太差）

それぞれのトランザクションの開始時点で、DBは実行中のトランザクションのリストを作成する。
新しくオブジェクトを作成する場合には、オブジェクトが内部的に保持するcreated_byにそのトランザクションのIDが保持される。
オブジェクトの更新時は、既存のオブジェクトはそのままで、新しいオブジェクトを作成し、それが内部的に保持するcreated_byにそのトランザクションのIDが保持される。
オブジェクトの削除時は、読み出したスナップショットに含まれるバージョンのオブジェクト(後述)が内部的に保持するdeleted_byにそのトランザクションのIDが保持される
トランザクション中に読み込み時に、それまでにコミット済みのtransaction_idの集合をidsとすると、(created_by in ids && created_by) && (deleted_by == null || deleted_by not in ids) の中でcreated_byが最大のバージョンのオブジェクトを読み取る

写入排队问题

作为前一章没有提及的赛车条件之一，写入偏斜被提出。写入队列是指当两个事务根据来自相同对象（组）的读取结果进行写入时会发生的赛车条件。

在这些中，我们提到了“更新丢失”和“幻影”（在某些数据库中，使用上述版本可能不会发生这种情况）。

更新的丢失问题 de

「アプリケーションがDBからなんらかの値を読み取り、その値を元に新たな値をDBに書き込む」read-modify-write 操作を二つのトランザクションで同時に行った時に発生しうる。
(1つ目のトランザクションの読み取り) -> (2つ目の読み取り) -> (1つ目の書き込み?) -> (2つ目の書き込み?) の順に行われた場合、?が?を上書きし、?の更新が失われる。

例

二人のユーザーがドキュメントを更新する場合に、片方の更新が失われる。

解決方法

① DBの提供するアトミックな更新処理を利用する。多くのRDBでは

SELECT users SET col = col + 1 WHERE key = ‘foo’ で、read-modify-write 操作をアトミック(transactionより粒度は小さいはず)に実行してくれる。
可能な内部実装は、

①カーソル固定 = トランザクションは読み取り〜書き込み完了までオブジェクトのロックを取得する。
②全ての操作を単一スレッド上で実行する

ORmapperを使うとこれを使わず、意図せず安全なread-modify-writeサイクルを実行するコードを書きがち。

② DBの提供する更新のロストの自動検出を利用する

read-modify-writeサイクルの並列実行を許可し、トランザクションマネージャーが更新のロストを検出したら、トランザクションを中断かつリトライする。

?対応しているDB/分離レベルは、PostgreSQLのrepeatable read、 Oracleのserializable、 SQL serverのスナップショット分離レベル。
MySQL/InnoDBのrepeatable readではこれを提供していない。

③ 書き込み時に明示的に行ロックを取得する。

SELECT * FROM users WHERE id=5 **FOR UPDATE **
? アプリケーションコードのどこかで必要なロックを追加し忘れる可能性がある

④ 分離レベルとしてSerializable levelを採用する。

在具有多个领导者和无领导者复制的数据库中，无法使用 ①②③。

幽灵引导导致的写入偏差

奇襲するパターンは、「①SELECT文?である条件を満たすか確認 -> ②アプリケーションで処理を続行するか判断 -> ③DBへ書き込み」で、最後の書き込みより前に?の条件が満たされなくなっている。
例

❶ 病院の当直システムにおいて、ある時間帯に他の医者の当直当番が入っていたらキャンセルができる。
❷ ユーザーがユーザー名を登録する際に、もしそれがユニークな名前でなければ作成失敗にする

解決方法

①のロック取得クエリでロック取得。つまり、SELECT ~ FOR UPDATE により関連するオブジェクト全てのロックを取る

? ❷のユニークなvalidationでは使用できない。なぜなら、条件を満たす行が存在しないことをチェックしているから。

②衝突の実体化 = 条件を満たす行が存在しないことをチェックのために、存在する全ての組み合わせを含むテーブルを用意する。

= ファントムをDB中の行の集合におけるロックの衝突に置き換える
? 並行性の制御の仕組みをアプリケーションのデータモデルに漏れ出してしまうのは望ましくない

③条件を満たす行が存在しないことをチェック
? PostgreSQLのrepeatable read、 Oracleのserializable、 SQL serverのスナップショット分離レベルでは自動検知できない。

可序列化等级

具备最强分离性能，可避免所有可能的数据库竞争条件。

複数のトランザクションがそれぞれ１つずつ順番に、並行でなく実行でされた場合と同じになることを保証する。

実装方法

①完全な逐次実行 = 単一スレッドで順次トランザクションを実行する

ただし、パフォーマンスが問題になるので、

OLTPトランザクションのように、小さくて高速(短く少数の読み書きしかしない)場合のみ使用する。
トランザクションのコード全体をストアドプロシージャとしてDBに登録しこれを実行する。これによって、アプリケーションのクエリ発行の待ち時間やネットワーク通信の待ち時間が不要になる。(ストアドプロシージャの言語は、VoltDbはJava、RedisはLua)
DBをパーティショニングする。ただし、アプリケーションが使用するデータ構造的にトランザクションが単一パーティションで実行できる場合のみ有効。

② two phase lock

❶sharedとexclusiveのモードを持つlock + ❷predicate lockかrange lockで実現する。

❶各オブジェクトは、shared/exclusiveの二つのモードを持つlockを持つ。

読み込み時には、shared modeのロックを取得する必要がある。shared modeのロックは複数のトランザクションが、同時に取ることができる。
書き込み時には、exclusive modeのロックを取得する必要がある。もし(いずれのモードだとしても)ロックが他のトランザクションによって取得されていたら、待つ。
ロックを取得したトランザクションはトランザクション終了までそのロックを保持し続ける。(つまり、shared mode lockを取得したまま待ち状態に入るトランザクションもありそう)
? 書き込みは他の書き込みも読み取りもブロックする。読み取りは他の書き込みのみブロックする。
デッドロックはDBによって自動検出され、いずれかのトランザクションが中断される。リトライはアプリケーションが明示的に行う。
⚠️ これだけだとファントムは発生しうる -> predicate/range lockで対応。

❷predicate lockかrange lockによってファントムの発生を防ぐ。

predicate lock(述語ロック)

トランザクションA内で読み込みのためにSELECT文によって検索をした場合、その検索条件にマッチする集合に対する共有ロック(=述語ロック)を取る。この集合が不変になることを保障したい。

そもそも、その集合内のオブジェクトの排他ロックがトランザクションBによって取られていたら、AはBの終了を待つ。
Cが挿入or更新or削除しようとしているオブジェクトがAの述語ロックにマッチしている場合、CはAの終了を待つ。

?パフォーマンスがよくない -> 多くのDBではrange lockを使用している

range lock(範囲ロック)

パフォーマンス向上のためにpredicate lockのマッチするオブジェクトの集合を大きくする。マッチを包含するインデックスエントリの共有ロックを取る。
(例) 読み込みのクエリが SELECT * FROM reservations WHERE room_id = 123 AND 22/08/15 < start_timeであり、room_idカラムにインデックスが貼られているとする。この時、rood_id=123のインデックスエントリのロックを取得する。
別のトランザクションの書き込みは、インデックスを辿って書き込み対象のエントリに辿り着き、それが共有ロックを取られていたら、解放されるまで待つ。
範囲ロックを与えるのに適したインデックスがない場合には、テーブルロックにfallbackする。

③Serializable Snapshot Isolation (2008~)

スナップショット分離に基づいている。トランザクション内の読み取りは一貫したDBのスナップショットから行われる。
楽観的ロックを取る= 潜在的に危険なことが生じても、トランザクションの実行をブロックせずにそのまま継続し、結局問題がなったことを期待する。問題があればabortされ、retryが必要になる。

c.f. two phase lockは悲観的ロック
潜在的に危険なことが生じる = premiseが覆る可能性がある状況 = あるトランザクションにおける読み取り後にDBのスナップショットが書き換えられる。(スナップショットは実際にバージョン数だけあるわけではないため)

潜在的な危険①あるオブジェクトの読み取り時に、そのオブジェクトの他のトランザクションによる未コミットのバージョンが存在する

「現在のトランザクションの読み取り後に書き込みをした」 && 「その未コミットの書き込みがコミットされたことをDBが検知された」場合には、実際にpremiseが覆っている。
読み取りだけの場合や、その未コミットの書き込みがコミットされなかった場合には、premiseは覆っていない。

潜在的な危険②あるオブジェクトの読み取り後に、その後の書き込みに影響する可能性のある他のトランザクションによる書き込みが検出された

略

?️ ライターはリーダーをブロックせず、リーダーもライターをブロックしない

第8章：分散系统的问题。

(以下结构简明扼要)

使用分散系统的目的是什么？

low latency (データを地理的にユーザーの近くにおける)

分散系统可能发生部分故障。其原因是，

stop-the-world GCによるもの
VMのsuspend and resumeによるもの
OSによるpreemptiveなスレッド切り替えによるもの
ディスクI/O待ちによるもの
OSのディスクへのスワッピング(ページング)処理によるもの

请将以下内容用中文进行同义转述，只需要一种选项：
“Can you please help me with this?”

プロセスの一時停止とリースとフェンシングサービスについてメモる

第9章一致性和共识

“合意”意味着

在达成共识(concensus)意味着

一様同意 uniform agreement (安全性)
整合性 integrity (安全性)
妥当性 validity (安全性)
終了性 termination (ライブ性)

半数未満のノードに障害があっても他のノードは決定に達する = 耐障害性を形式化したもの。

合意とは、様々なアプリケーションで再利用可能な概念分散システムで提供される以下の保障や抽象概念(詳細は後述?)は実際には合意と等価である。

線形化可能なcompare-and-setレジスタ
全順序ブロードキャスト
分散トランザクションにおけるアトミックなコミット
ロックとリース
レプリケーションされたDBにおけるリーダー選出
協調サービス(ZooKeeper等)における線形可可能でアトミックな処理
ユニーク制約
?シングルリーダーデータベースは書き込み時に合意アルゴリズムが不要！しかし、リーダーシップの管理や変更の対応のために必要である?
?リーダーレスやマルチリーダーレプリケーションのシステムは通常グローバルな同意を用いない -> 衝突が発生する。が問題ない。

?内部的なアルゴリズムはそれぞれの用途で見ていく。
?️合意には以下の限界がある

処理を行う上で厳密な過半数を必要とする。半数以下のノードからなるネットワークが分離されると、それらはブロックされる。
ノードの追加や削除は簡単に行えない。
ネットワークの問題により障害中のノードの検出を誤判定する可能性がある。この場合、リーダーの選出を繰り返し行うため、パフォーマンスが悪化する。

在分散系统中提供的保证和抽象概念是通过使用共识算法实现的。

レプリケーションされたデータ(オブジェクト)が、あたかもデータのコピーが一つしかないかのように見え、そのデータに対する操作がアトミックに働く。つまり、最新性の保証。
定義

ある読み込み/書き込み処理A -> Bの実行時間帯が被っていない場合、Bの操作はAが反映された状態のDBに対して行われる。
AとBの実行時間帯が被っている(並行している)場合には、それらの操作の順番は問われない。

具体的な用途は

リーダー選出のための分散ロック
DBのユニーク制約
クロスチャンネルタイミング依存関係

実装方法

?「レプリケーションを持たない」のは耐障害性が失われるのでなし。
略

線形化可能にすることのコスト

可用性(Availability)が失われる

CAP定理は「ネットワーク分断が発生したときにC(＝線形可能性)とAのいずれかしか担保できない」ことを表している。

パフォーマンスが落ちる

多くのDBでCを犠牲にする理由はAの担保ではなく、パフォーマンスの悪化防止

因果律は、弱い一貫性モデル

イベントに順序を持ち込む

バージョン履歴は分岐と合流をもつ時系列(並列に行われる処理もある)

「システムに必要なのは実は線形可能性ではなく、因果律における一貫性」だという場合も多い。
線形化可能性ほどの調整のためのオーバーヘッドを持たず、ネットワークの問題も線形化可能性ほど敏感ではない。
実装

バージョン管理のために、ランポートタイムスタンプ (counter, node id) を用いる

?️操作の全順序が決まるのは全ての操作が収集できた後である＝あるイベント発生時に他のノードでそこまでに発生したイベントの全てを得られる訳ではない → あるリクエストの受信時に即座に成功かの判断はできない。

❎結果整合性(eventual consistency)は弱い保証であり、これは合意アルゴリズムを必要としない(?)
全順序ブロードキャスト

ノード間のメッセージ交換プロトコル
以下の安全性が常に満たされる。

(信頼性)メッセージは厳密に一度だけ全てのノードへ配信される
(順序付け)全てのノードは、同じ順序でメッセージを受信する

メッセージが配信された時点で順序が確定される
使用される例

データベースのレプリケーション
ZooKeeperやetcd
serializableなトランザクション
フェンシングトークンを提供するロックサービスの実装
linearizableな、アトミックなcompare-and-set操作

全順序ブロードキャストをappendのみが行われるログとして使用⭐

実装方法

linearizableなシークエンス番号生成器で、各ノードは処理のシークエンス番号を発行してもらい、その順番に各ノードはメッセージ送信を行う。ただしその生成器の冗長化のためにはまた合意が必要である。

分散トランザクション

?多くのNoSQL分散DBではサポートされていないが、様々なクラスタ化されたRDBではサポートされている
アトミックなコミットを実現するために同意アルゴリズムが用いられている。
アトミックなコミットが有用なケースは

マルチオブジェクトトランザクション
セカンダリインデックスの作成時

アトミックなコミットの実装

クライアントのリクエストはコーディネータに渡る。コーディネータは各ノードへ以下のリクエストを行う。
①データの書き込み依頼

これを受け取った時点で各ノードはトランザクションを開始する。

②(P1)コミット可能か質問(いかなる場合でも可能ならノードはyesが返す)

ここでyesを返したノードはその後絶対にコミットを行う義務を追う。

ｰｰｰコミットポイントｰｰｰ

ここを越えた時点でコーディネータは絶対に全てのノードへコミット依頼を送り届ける(リトライ含める)義務を追う。
コーディネータは中断するかの判断をディスク上のトランザクションログに書き込む?

③(P2)コミット依頼

X/Open XAに準拠するDB, メッセージブローカーetcを用いることで、2つ以上の異なる技術を利用して分散トランザクションの2 phase commitを実現できる。
?️パフォーマンスが良くない。

?のディスク書き込み
ネットワークのラウンドトリップの増加

?️コーディネータがクラッシュした場合、各ノードは関係するレコードのロックを取り続けることになる。この場合、コーディネータのリカバリーを待つ必要がある。
?️コーディネータがレプリケーションをもたない場合、これが単一障害点になる。

ZooKeeperやetcd

インメモリデータベースの分散キーバリューストア。(ただし永続化のためにディスク書き込みは行われる)
データのレプリケーションは耐障害性を持つ全順序ブロードキャストアルゴリズムによって行われる。

提供する機能は以下。これらは分散協調に使用される。

ロック。?️linearizableでアトミックな操作を利用して実装される。 ⭐同意アルゴリズムを使用している。
ロック/リース×プロセスの一時停止に起因するレースコンディションを防ぐために使用されるフェンシングトークンの発行。?️操作の全順序付けを行うことで実現される。

zookeeperサーバーに接続中のクライアントの障害検出。?️クライアントから定期的に送信するハートビートのタイムアウトによって検知される。
他のクライアントの新たな参加や、他のクライアントでの障害発生等が、クライアントへ通知される。(クライアント自らポーリングする必要はない)

用途

協調及び設定サービスとしての使用。利用例は以下。(合意アルゴリズムを自分で実装しなくて良い)

リーダーの選出
パーティショニングされたリソースにおいて、どのノードにどのパーティションを割り当てるかの判断

サービスディスカバリのために利用

＝特定のサービスにアクセスするのに接続しないといけないIPアドレスを知るために使用。
これは合意を必要としない。

メンバーシップサービスとしての利用

＝アクティブでクラスタのメンバーとなっているノードを判断する。
合意と障害検出を組み合わせ、他のノードに障害が発生してきるかをノード間で同意する。

事务隔离的目的是为了避免由于并发进行事务而导致的竞争条件。分布一致性的目的是为了调整副本的状态，以应对延迟和故障。

第五章 复制

5.1 单一领导者(Note: This paraphrase assumes the phrase “シングルリーダー” is referring to a single leader in a specific context, such as a team or organization.)

对节点故障的应对措施

关于自动故障转移

领导者基于的复制方法

与复制滞后相关的问题

5.3 多主复制

5.4 无主复制

第六章 划分

索引的方法

分区和次要索引

重新平衡分区

第七章 交易

读取提交级别

快照隔离级别

写入排队问题

更新的丢失问题 de

幽灵引导导致的写入偏差

可序列化等级

第8章：分散系统的问题。

第9章 一致性和共识

“合意”意味着

在分散系统中提供的保证和抽象概念是通过使用共识算法实现的。

第五章复制

第六章划分

第七章交易

第9章一致性和共识