分散データベースにおける整合性とアンチ・エントロピーについて理解できていますか？

# はじめに

## Apache Cassandraについて

Apache Cassandraとは、一言でいうなら、オープンソースの分散データベース管理システムです。

他の分散データベース管理システム同様、複数の汎用サーバーを用いて、ひとつのデータベースを構築します（開発などの目的のため、一つのサーバーのみで構成することも可能です）。

ここでは、詳しい説明は割愛し、興味のある方へのご紹介の役割は、公式サイトやWikipediaに譲ります。

https://cassandra.apache.org/_/index.html

https://en.wikipedia.org/wiki/Apache_Cassandra

# 分散データベースにおける整合性とアンチ・エントロピーについて、理解できていますか？

## 整合性(Consistency)の二つの意味

Cassandraの欠点として、データの整合性に難あり、ということがまことしやかに言われたりします。
その根拠として、CAP定理が用いられたりします。

一方で、そのような混同の指摘自体も珍しいものではなく、CAP定理のConsistencyとACIDのConsistencyの違い、という情報も世の中にはそれなりに出回っているという気がします。ここでは、区別されるべき、という指摘に止め、詳細はそれらの情報に譲ります。

以下では、異なる切り口での情報を提供します。

## アンチエントロピー

Cassandraの用語の中で、他のデータベースではあまり耳にすることのないものの一つに「アンチエントロピー」があります。元々は、Dynamoで用いられた用語であり、Dynamoの設計を多く引き継いでいるCassandraでも、同じ用語が使われています。

https://io.typepad.com/glossary.html

https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html

Dynamo論文の「4.7 Handling permanent failures: Replica synchronization」の章で扱われています。

### 本来の意味

エントロピーについては、ほとんどの人が感覚的に理解できており、説明不要、とも思われますが、あらずもがなの注釈を少しだけ（どちらかといえば、ここでの「アンチ」の意味の方を捉え難いという気がするため、その補助線として）。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%B3%E3%83%88%E3%83%AD%E3%83%94%E3%83%BC

Wikipediaによるとエントロピーのそもそもの意味は以下のようなものです。

>エントロピー（英: entropy）は、熱力学および統計力学において定義される示量性の状態量である。熱力学において断熱条件下での不可逆性を表す指標として導入され、統計力学において系の微視的な「乱雑さ」[注 1]を表す物理量という意味付けがなされた。統計力学での結果から、系から得られる情報に関係があることが指摘され、情報理論にも応用されるようになった。

情報理論への応用については、次のように言われています。

>情報理論においてエントロピーは確率変数が持つ情報の量を表す尺度で、それゆえ情報量とも呼ばれる。

エントロピーとは「（エネルギーが）拡散しきった状態、無秩序、乱雑さ」と言えます。
よく耳にするフレーズとしては、「エントロピー増大の法則」というものだと思います。
つまり、放置しておけば、エントロピーは自然に増大する、ということですね。ただし、エントロピー増大は、あくまで、孤立系に対する法則であることにも注意が必要です。
現実界では、多くの場合、外部からの干渉（エネルギー、物質）によって、エントロピーの際限のない増大は妨げられるものと見られます。


### 分散システムにおけるエントロピーの意味

分散システムにおけるエントロピーについて、Alex Petrovの「Database Internals」（「詳説データベース」オライリー）に一章（Anti-Entropy and Dissemination）が設けられています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176567/03211d06-3c34-6fef-d366-f066b3a0167d.png)

>他のすべてのプロセスにメッセージをブロードキャストすることは、クラスター内のノード数が少ない場合にうまく機能する最も簡単なアプローチですが、大規模なクラスターでは、ノード数のためにコストがかかり、単一のプロセスに過度に依存するために信頼性が低くなる可能性があります。 . 個々のプロセスは、ネットワーク内の他のすべてのプロセスの存在を常に認識しているわけではありません。さらに、ブロードキャスト プロセスとその各受信者の両方が起動している時間にオーバーラップが必要であり、場合によってはこれを達成するのが難しい場合があります。

>これらの制約を緩和するために、一部の更新が伝播に失敗する可能性があると想定します。コーディネーターは**最善を尽くし**、利用可能なすべての参加者にメッセージを配信します。その後、障害が発生した場合にアンチエントロピー メカニズムがノードを同期に戻します。このように、メッセージを配信する責任はシステム内のすべてのノードで共有され、**プライマリ配信**と**事後的な同期**(primary delivery and periodic sync*)の2 つのステップに分割されます。

注： 一般的にperiodicは、「定期的な」と訳すのが自然かもしれませんが、ここでの文脈においては、別の意味を強く生じるため、ここでは採用しませんでした。かといって、必ずしも、元の単語の意味を全く変えているのではなく、掉尾文、つまり「文尾に至って初めて文意が通じる文章」という意味でのperiodic sentenceの用法に則って、このように訳した方が、適切という判断をしています。

>エントロピーはシステムの無秩序の尺度を表すプロパティです。分散システムでは、エントロピーはノード間の状態の相違の程度を表します。このプロパティは望ましくなく、その量を最小限に抑える必要があるため、エントロピーを処理するのに役立つ多くの手法があります。

>通常、アンチエントロピーは、プライマリ配信メカニズムが失敗した場合にノードを最新の状態に戻すために使用されます。他のノードが情報を拡散し続けるため、ある時点でコーディネーターに障害が発生した場合でも、システムは正しく機能し続けることができます。言い換えれば、反エントロピーは、**結果整合性を採用したシステムで収束時間の境界を引き下げる**ために使用されます。

エントロピー修復、つまりアンチ・エントロピーのプロセスには、以下のタイミングがあります。

 - 書き込みリクエスト時
 - 読み込みリクエスト時
 - マニュアル（通常のリクエストとは分離した操作、という意味で。システム的に自動化される場合も当然あります）

アンチエントロピー操作は、DBaaS (Database-As-A-Service)では、意識せずに済むとはいえ、分散データベース（のあるカテゴリー、CAP定理で言えばAPデータベース、Cassandraが含まれる）においては、必ずついてくるものという理解が、データベースエンジニアとしては、大切だと言えるでしょう。

# 最後に

以前、下記の記事を執筆しました。

https://qiita.com/yoshiyuki_kono/items/98d41b3dbc2e9f1a70e5

これらの記事のタイトルの「理解できていますか？」という問いかけは、まず第一に自分自身に向けられたものですが、この記事が他の方にとって何らかの役に立つようであれば、幸いです。