Azure Cosmos DB 是什么?

这是微软在2017年5月10日（美国时间）宣布的新数据库服务。与以往的数据库服务不同的是，它不仅提供了传统的分布式级别（限于数据中心），还支持越过数据中心的级别（被称为全球级别）。这意味着托管的数据可以随意增大（可伸缩性），而不仅仅是多个地理上相距较远的数据中心，可以部署并访问同一数据集。此前谷歌发布的Spanner也是一个能够实现全球分布的服务（多地区支持在本文编写时尚未提供）对吧。

微软公司宣布推出以“星球规模”扩展的“Azure Cosmos DB”。

Azure Cosmos DB除了支持全球范围的分布式环境外，还具备以下特点。

• Multi-Data: テーブル、Document、グラフ、Key-Valueといった様々なデータに対応

それぞれ DocumentDB API, MongoDB API, Table API,Graph API(Gremlin対応)といったAPIでアクセス可能

ペタバイトレベルまでスケール可能
5つの一貫性レベルに対応(Strong, Bounded Staleness, Session, Consistent Prefix, Eventual Consistency)

我有。

在本文中，我们将关注于Cosmos DB支持的5种一致性级别中的一种，即有界陈旧度。我们将重点介绍这个概念提供了何种一致性，以及如何通过概率性多数方式实现该一致性级别。

为什么要关注其中之一呢，因为有两个个人原因。

• 個人的に、Strong、いわゆるLinearizabileと呼ばれるような「強い一貫性」と、Eventual Consistentと呼ばれる、いつかは整合が取れるけどそれがいつかは保証しませんよ、という「弱い一貫性」の中間の定義は、恥ずかしながらこれを見るまで知らなかったため、この定義を見た時には、非常に新鮮で興味がそそられた

 

• 最近ずっと、Quorum呼ばれる概念とその応用について大変興味を持っていて2、５つのレベルの中でBounded Stalenessと呼ばれる整合性を実現する手段としてProbabilisic QuroumというQuorumの一種が利用可能であることがわかった

 

この不思議な性質と構成法は、Quroumの応用としてとてもシンプルかつ実用的だと感じた

这是为了。

请参考以下内容，了解其他有关Cosmos DB的信息。

• 米MS、「惑星規模」でスケールする「Azure Cosmos DB」を発表

 

• A technical overview of Azure Cosmos DB

 

Azure Cosmos DB Documentation(公式ドキュメント)

让我们首先来看一下Azure Cosmos DB所支持的五个一致性级别。

在 Azure Cosmos DB 中引入的5个一致性级别。

我们可以参考官方文档中的一节来了解五种一致性级别。

从左边走，整体性越强，从右边走，整体性就越弱。我觉得比起在这里详细解释”整体性”，更容易理解的方法是边解释各个整体性水准，边掌握感觉。我将简单地按照整体性较弱的顺序进行解释。

在阅读以下完整性级别时，最好将“如何管理多个数据副本？”放在脑海中以便于理解。在分布式数据库中，为了提高可用性和可扩展性，不可能只将数据写入一个地方。因此，必须在几个位置上保留数据的副本，而如何管理这些副本的方法变得非常重要。

• Eventual

読み込めるデータが 最新である保証はない

読み込むプロセスによって(同一プロセスであっても)は 先祖返りするかもしれない

でも、すべてのreplicaが いつか同じ状態に収束する

これは5つの内一番整合性が弱いかわりに読込書込がとても速い

Consistent Prefix

読み込めるデータが最新である保証はない,先祖返りするかもしれない, いつか同じ状態に収束する　のはEventualと同じ

それに加えてreplicaに適用される書込リクエストの順序は同じ

例えば、A, B, Cという書込リクエストが複数のreplicaに適用されるとすると、クライアントからみると、A, A,B, A,B,Cと書込リクエストが処理されたデータは読み込まれる可能性はあるが、

A,Cとか、B,A,Cという風な順で書込がなされたデータが見える可能性はない

Session

Consistent Prefixは、先祖返りが起きたり, 読込リクエストごとに見えるデータの世代が違う、ことが起きるけれど、
Sessionでは、いわゆるMonotonic Read, Monotonic Write, Read Your own Write(RYW)を保証する
Monotonic Read: あるプロセスから見て読み込めるデータは先祖返りしない

Monotonic Write: あるプロセスからなされるデータXへの書込順序は保存される

Read Your own Write(RYW): あるプロセスが書込処理を行ったら、そのプロセスはすぐその書込処理完了後のデータが読める

Bounded Stalenss

読み込めるデータは古いことはあるが、t単位時間以降はK世代以内のデータが読めることを保証する
ユーザはこのK, tをチューニングできる。
この整合性レベルは、強い整合性を求めたいけどデータのavailabilityが99.99%でよくて、かつ低レイテンシが欲しい場合に有効

Strong

いわゆるLinearizabileを保証する、あるプロセスが書き込めたら、どのプロセスが読んでも常に最新の値が読める。
majority quorumで実装できる

虽然稍显粗鲁，但总结起来应该如下所示。

• Eventual: 読み込めるデータはどれだけ古いかわからないけどいつか最新になります(読み込み時先祖返りOK, 書込リクエストの適用順序バラバラもOK)

 

• Consistent Prefix: いつか最新になればOK(先祖返りも許す)だけど、replicaへの書込リクエストの適用順序は統一

 

• Session: 自分から見ると先祖返りしない、自分の書込は順序が保たれる、自分の書込は自分からは即読込可能。全体でみるとはConsistent Prfix。

 

• Bounded Staleness: どのプロセスから見ても、書込後t時間立てば、読めるデータの古さの上限(K世代)が保証される。K, tはチューニング可能。

 

Strong: 誰かが書き込んだら、どのプロセス絡みても常に最新の値が見える(K=1, t=0のBounded Stalenessと言える)

概念本身并不是新的翻译选项为。

看到这个演讲时，我觉得非常新鲜和有趣。但稍作了解后，除了Bounded Staleness以外，并不是所有的定义都是非常新的。

维基百科：在查看一致性模型时，这些一致性级别是在2007年由Andrew Tanenbaum博士提出的。

2008年，Amazon.com的首席技术官Werner Vogels在他的文章《最终一致性 – 重审》中提到了这个问题。

非常有趣的一种一致性级别，名为有界陈旧度的Bounded Staleness。

现在，终于到了正题。Bounded Staleness 可一致性级别。

无论从哪个进程来看，经过t个时间单位后，可以保证读取的值是K代以内的数据。

这就是所谓的。

如前所述，具有所谓的强一致性（在此模型中是针对t=0，k=1的情况）的复制品的更新是通过使用仲裁系统来管理复制的方法来介绍的。

在读取和写入操作中定义一个共同的仲裁系统。
在写入时和读取时，从中选择一个仲裁组，并将写入/读取操作应用于属于该组的所有节点（如果有任何一个失败，则报错）。

如果这样做的话，那就可以了。

你觉不觉得”K世代前”或者”t时间过后”这样的表达非常有趣呢？

在我以前的理解中，只有在quorum相互重叠的情况下，才能称之为quorum。如果读取和写入的quorum没有重叠，就会导致读取到旧数据，所以我们必须想办法让读取的quorum在某个时刻与最新的数据（即使是K代之前的数据）的写入quorum发生冲突。选择quorum的方式不能是随机的。

例如，将N个副本分成N/k个组，写入时选择N/k个副本进行轮询更新，读取时从任意一个副本读取，那么副本的世代确实只存在k世代之前，所以k世代之前是可以保证的。但是，关于$t$时间之后的限制，我暂时想不到。

但是，即使在某些部分缺少重叠的quorum系统中，只要按照这种方式和创意进行操作，或许可以设计出更好的write quorum，以确保在全read quorum中至少存在一个不超过K代的数据。

重要的论文

这个答案是从Azure Cosmos DB的官方文档中引用的。

Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein, Ion Stoica所著。
《实用偏好随机一致性（PBS）用于部分法定人数》。
http://vldb.org/pvldb/vol5/p776_peterbailis_vldb2012.pdf

是的。

用中国语言进行再述：从这里开始，将从这篇论文中摘录一部分，并尽可能地简明易懂，

使用概率性仲裁系统实现Probabilistic Bounded Staleness的方法。

我想要对…进行解说。

Partial/Probabilistic Quorum即为部分/概率性法定人数。

如上所述，正常的quorum系统（在这里我们称之为严格quorum系统，以与概率/部分quorum系统相对比）符合该定义。

以中文为母语的选项，将以下内容进行释义：

将集合 V 的定义为节点的集合，即 $V = \{ v_1, v_2, …, v_n \}$。Strict Quorum System 是指集合 $\mathcal{S} \subset 2^V$，其中 $\mathcal{S}$ 是 V 的子集合，并满足以下条件。$\mathcal{S}$ 的元素被称为 Quorum。

任意两个 Quorum $Q_1$ 和 $Q_2$ 必须有交集($Q_1 \cap Q_2 \neq \emptyset$)。

然而，如果我们尝试放宽这个交叉判定标准，自然而然地可以定义出下一个部分关照概念。

Parial Quroumであるための条件: 少なくとも2つのQuorum $Q_1, Q_2$が共通部分を持たない($Q_1 \cap Q_2 = \emptyset$)

为了实际应用而言，如果完全不重叠会造成困扰，而且重叠的可能性也无法讨论，因此在部分仲裁系统中引入了一种所谓的”访问策略”，决定哪些仲裁会被选择以及选择的数量。在这种访问策略下，也定义了一种概率仲裁，以确保仲裁之间的重叠概率。

• $\epsilon$-Probabilistic Qurorumであるための条件: $Pr_\omega [Q \cap Q’ \neq \emptyset]\geq 1-\epsilon $

$\omega$はquorum systme上のaccess strategy

概率上有边界的陈旧度（PBS）

在本论文中，我们定义了三种概率有界陈旧度，即PBS k-陈旧度、PBS t-可见度和PBS -陈旧度。

• PBS $k$-staleness: 確率的に$k$世代以内が読める

 

• PBS $t$-vibibility: 確率的に$t$時間以降は最新世代が読める

 

PBS $<k,t>$-staleness: 確率的に$t$時間以降は$k$世代以内が読める

是的。

Probabilistic Bounded Staleness可以翻译成中文为「概率性保证数据不新鲜」。

在定义这个PBS时，我们的前提假设是不是使用一个共享的读写quorum系统，而是分别为读quorum和写quorum提供不同的模型。此外，在定义可见性时，我们的前提是在写入操作后执行反熵处理的扩展quorum。

让我们按顺序来看一下定义和构建方法。

PBS k-新陈代谢

k-新鲜度的定义如下。

定义仲裁系统满足PBS k-陈旧一致性的条件是指，读取仲裁至少包含有$1-p_{sk}$概率的数据，该数据在$k$代以内。

法律构成

考虑一种所谓的Dynamo风格的读/写Quorum系统。作为$\mathcal{S}=2^V$上的访问策略，

• 読込時: $\mathcal{R} = \{ s \in \mathcal{S} \,|\, |s| = R \}$からrandomに選択 (N replicaからrandomに$R$個選ぶ）

 

書込時: $\mathcal{W} = \{ s \in \mathcal{S}| \,|\, |s| = W \}$からrandomに選択 (N replicaからrandomに$W$個選ぶ)

在这种情况下，我们考虑没有任何限制的R和W。

在这种访问策略的基础上，如何计算在读取时最新版本不包含的概率$p_s$（即不新鲜度s）？只需要计算用于写入的特定的$W$个节点未被选作读取Quorum的概率即可。

$p_s = \frac{直前写入W节点的受调查总体中读重要性覆盖的数量}{|\mathcal{R}|} = \frac{N-W \choose R}{N \choose R}$

$p_s = \frac{直前写入W节点的调查母体中满足读取Quorum的数量}{|\mathcal{R}|} = \frac{N-W \choose R}{N \choose R}$

$p_s = \frac{根据之前写入W节点的所属群体内的读取Quorum数量}{|\mathcal{R}|} = \frac{N-W \choose R}{N \choose R}$

(Note: The translation may vary depending on the specific context)

当我们通过一些给定的$N, W, R$来研究这个值会发现一些有趣的事情。

• $N = 3, R = W = 1 \Rightarrow p_s = 2/3 $

 

$N = 100, R = W = 30 \Rightarrow p_s = 1.88 \times 10^-6$

一般情况下，通常不会为每个键创建100个副本，所以常用的是 $N=3, R=W=1$。在这种情况下，有 $2/3$ 的概率无法读取到最新的数据。反过来说，有 $1/3$ 的概率可以读取到最新的数据。

您是否已经注意到了呢？最新的（第一代前）的不可读的概率为2/3，但如果我们将允许看到前k代的话，那么完全不能读取前k代的概率可以用Ps^k来计算，因此，最终选择能够看到k代以内的概率会不断增加。

• $N=3, R=W=1$の場合、$k=10\Rightarrow 1-p_{sk} > 0.98$

 

• $N=3, W=2, R=1$(逆でも同じ)の場合、$k\geq5 \Rightarrow 1-p_{sk} > 0.995$

 

$N=5, W=2, R=2$の場合$p_{s1}=3/10$, $k\geq5 \Rightarrow 1-p_{sk}>0.997$

就是这样。也就是说。

• N=5(replica数=5)

 

• R=2(Read時replicaからランダムに2個読んで新しい方を返す)

 

• W=2(Write時もreplicaを2個ランダムに選んで更新)すると、

 

99.7%の確率で5-stalenessを満たす

我明白了。即使是这么简单的逻辑，只要是在5代以内的条件下，有99.7%以上的概率，这真是非常有趣呢。

PBS 可见性

如果使用Read/Write Quorum来管理副本，那么在处理写请求时，我们需要将数据写入到W个副本中（在将数据写入W个副本后，将处理完成的消息返回给客户端），然后通常会执行一个称为反熵（anti-entropy）的异步操作，将写请求传播给另外N个副本。这个过程经常被称为扩展Quorum（expanding quorum），因为Write Quorum的规模在逐渐扩大。

在T-visibility中，在扩展投票模型上，我们定义了一个被称为“不一致窗口”的指标，用于表示最新一代可以被读取的时间间隔。

在中文中将以下内容进行改述：一个Quorum系统满足PBS t-visibility一致性，意味着至少在$t$个时间单位之后，所有读取法定人数中至少有一个数据以$1-p_{sk}$的概率包含最新一代的数据。

構成法 is a legal term which refers to the “constitution” or the “fundamental law” of a country.

让我们再次确认使用扩展法定人数的副本管理算法。

• Write時:

N個のreplicaからランダムにW個選び書き込む(Write Qurorumに書き込む)
clientはW個書込完了時点で成功を受け取る
その後残りのreplicaに順に値を伝播させていく(anti-entropy処理)

Read時:

N個のreplicaからランダムにR個から読み込んで一番新しい世代を返す

是的。

为了评估这个简单算法有多少不一致性窗口，我们将使用累积概率函数来评估特征化最新一代副本数量的反熵过程。

• $t$単位時間後に$w$個のreplicaが最新である確率を $P_\omega(w,t)$　とする

expanding quorumの書込処理の定義から $\forall c\in[0,W],\,P_{\omega}(c,0)=1$ことに注意

这样做，$p_{st}$（表示在过去t个时间单位后，被访问到不包含最新一代的读副本的概率）可以按以下方式计算。

\begin{align}
p_{st}  &= (t=0で書き込まれたWrite Quromにアクセスできない確率) \\&\quad + (t単位時間後に最新版を持っているreplicaにアクセスできない確率) \\
&= \frac{N-W \choose R}{N \choose R} + \sum_{c\in(W,N]}\frac{N-c \choose N}{N \choose R} (P_\omega(c+1,t)-P_\omega(c,t))
\end{align}

如果在t小时后进行准确的read操作，并且在进行了W次无延迟的write操作后开始了anti-entropy处理，则这个概率是实际处理过程中$p_{sk}$的上界（也就是说，实际上无法访问最新一代的概率将小于这个值）。

此外，由于$P_\omega$是依赖于反熵过程本身的，因此不能进行进一步的分析。实用性部分将展示具体的反熵过程的模拟结果。

PBS K，T-新鲜度

使用具有$t$-可见性的扩展共识机制的系统中，结合了$k$-不新鲜度概念的是$<k,t>$-不新鲜度。换句话说，当进行了$k$次写入并在$t$个时间单位后出现读取请求时，它以概率保证可以从最新版本中访问到$k$代以内的数据。

当请求在进行k次写入操作后的t个时间单位后发送时，并且定义的quorum系统满足PBS＜k,t＞-stalness的一致性时，即使这时的概率为1-p_{skt}，所有的read quorum中至少存在一个数据来自最新世代并包含在k世代之内。

构成法 fǎ)

可以使用与t-visibility完全相同的扩展配额。使用这个模型，可以计算出在$t$小时后能够在$k$代之内进行读取的概率。如果要进行精确计算，还可以考虑$k$个写操作之间的时间差，但在这里我们假设所有写操作同时发生，就像在计算$k$-staleness时那样，可以简单地计算如下：

$$
p_{skt} = p^k_{st} = \left(\frac{{N-W \choose R}}{{N \choose R}} + \sum_{c\in(W,N]}\frac{{N-c \choose N}}{{N \choose R}} (P_\omega(c+1,t)-P_\omega(c,t))\right)^k
$$

$$
p_{skt} = p^k_{st} = \left(\frac{{从N中选择W个不包含在N中的元素的组合数}}{{从N中选择R个元素的组合数}} + \sum_{c\in(W,N]}\frac{{N-c 中选择 N个元素的组合数}}{{从N中选择R个元素的组合数}} (P_\omega(c+1,t)-P_\omega(c,t))\right)^k
$$

在这种情况下，最终还是与$t$-visibility时一样，取决于反熵过程的$P_\omega$的概率。

Probabilistic Bounded Staleness的可行性

在論文中，透過模擬展示了基於常用的Dynamo擴展論証系統（WARS模型）的管理方法能夠滿足多少程度的$$-延遲性。

Dynamo风格的quorum系统：WARS模型

Dynamo风格的quorum系统采用了之前介绍的基于扩展quorum的副本管理算法。在这个算法中，不明确选择quorum，而是将请求发送给所有副本，并使用最快的副本返回的响应来回复客户端。

• Write時: N個のreplica全てにwriteリクエストを送る。W個の返答が返ってきた時点でclientに完了返答

 

Read時: N個のreplica全てにreadリクエストを送る。R個の返答が返ってきた時点で最新版をclientに返答

如果用图示来表示这个，会变成下图的样子。

在WARS模型中的t-visibility

在这篇论文中，著者通过将各个复制体（replica）单独设置具有不同值的概率分布$\mathbf{W_i},\mathbf{A_i},\mathbf{R_i},\mathbf{S_i}$来评估$t$-visibility。由于$t$-visibility取决于反熵（anti-entropy）过程，因此可以根据$t$-visibility的概率来计算$<k,t>$-staleness。他们使用MonteCalro模拟进行了评估。

在该实验中，我们使用LinkedIn、Yammer等大型企业的生产延迟数据作为基础，使用帕累托分布对上述概率分布进行建模，并进行了模拟。具体条件请参考论文中的图5。我们对四种延迟模型进行了比较，每种模型都具有以下特点。

• LNKD-SSD: Voldmortベースのproduction latencyモデル。SSDベースでディスクアクセスは高速。network boundなのでW=A=R=Sを想定

 

• LNKD-DISK: Voldmortベースのproduction latencyモデル。A=R=SはLNKD-SSDと同じで,Writeだけ遅い

 

• YMMER: Basho Riackベースのproduction latencyモデル、W, A=R=SというモデルではLNKD-DISKと同じ傾向だが、全体的にLNKD-SSDより遅い。Longtailが太いのが特長で、99.99%tileでは10秒くらいという値もでる

 

WAN: readとwriteは異なるdatacenterからくるものと想定。replica requestの一つはdatacenterを跨ぎことを想定。datacenter跨ぎのリクエストはLNKD-SSDモデルに75ｍｓを上乗せしている

論文概括中提到了以下内容。

• $t$-visibilityは総じてwrite latencyに大きく依存する

 

• LNKD-SSDでは、書込完了直後(t=0)で97.4%, 5ms後には99.999%を達成

 

• LNKD-DISKでは、writeの遅さが影響し、書込直後では43.99%しか無く、10msたっても92.5%しかなかった

 

• YMMRでも同じ傾向だが、書込直後で89.3%。99.9%を達成するのに13.64秒かかっていた

 

WANモデルは75ms以上立たないとinconsistency windowを抜けないので予想通り遅い。write直後は33%しかない

另外，由于在$N=3$的情况下，已经提供了可以实现99.99%的$t$-visibility的$t$值，以及在每个latency模型中计算出的读取延迟和写入延迟，因此在这里将它们列出。

看到这个，

• SSDを使ってディスクアクセスが高速かつ均一な場合、N=3, R=W=1のWARSモデルでは、1.85ms-visilibityが99.99%の確率で達成できる

 

DISKでもR=2, W=1としておけば13.6ms-visibilityが99.99%の確率で達成できる

只要考虑当前的硬件配置，我们就可以知道，即使不具备强一致性（R+W>N），也可以以相当实际的概率实现t-visibility。

更多不同的情况

这篇论文所使用的仿真可以通过网页进行尝试。通过调整下方的滑块，可以实时绘制$<k,t>$-陈旧度的图表。

• qurorumの構成: $N, R, W$

 

• WARSのlatencyモデル: W,A,R,S

 

• k-staleness: “Tolerable Staleness”と表現されています

 

simulationするためのiteration回数

根据这个图，
– 当$N=3, R=W=1$，设置为$3$-staleness。
– 写入后，有75.27%的概率达到$3$-staleness。
– 10ms后，有90.94%的概率达到$3$-staleness。
– 100ms后，有99.99%的概率达到$3$-staleness。
– 我们可以看到已经实现了这个目标。

最后

本篇文章将解释Azure Cosmos DB所支持的一种数据一致性级别概念——有界陈旧度。

在这篇论文中，我参考了论文来解释了Probabilistic Bounded Staleness这一概念的形式化以及它可以通过使用扩展型投票系统来实现。

另外，我们在参考文献中论证了一种名为WARS模型的Dynamo风格的法定人数系统——这是一种简单的算法，它在交互式模拟演示中也被证实能够在非常实用的程度上满足概率有界陈旧度。

就我个人而言，我非常有兴趣的是，即使是简单的read/write quorum + 反熵模型，在概率上确实，但实际上可以期望强一致性，在 Azure Cosmos DB 生产中采用了这种模型，这一点令人非常感兴趣。

阅读《Azure Cosmos DB的技术概述》时，发现其中提到了微软过去客户的趋势。

约73%的我们的客户使用会话一致性，20%的客户更喜欢有界陈旧度。我们观察到，大约3%的客户在最初尝试不同的一致性级别后才为他们的应用选择一个特定的一致性选项。我们还观察到，平均只有2%的客户会根据每个请求的情况覆盖原有的一致性级别。

选择Bounded Staleness的人似乎并不多。同样，人们也很少选择它。

为了向客户报告一致性 SLAs 的任何违规行为，我们使用线性一致性检查器，该检查器在我们的服务遥测上持续运行。对于有界陈旧性，我们监控并报告任何违规 k 和 t 边界。对于所有四个弛化一致性级别，除了其他度量标准外，我们还跟踪并报告概率有界陈旧性 (PBS) 度量。

因为被记录下来了，所以当设置了强一致性时，确保了线性可操作性；当设置了有界新鲜度时，也可能存在警报，以确保$k$和$t$没有偏离期望值。这看起来非常有趣。

我实际上不知道自己会不会使用Azure Cosmos DB，但接下来我想调查一下”Session”、”Consistent Prefix”这样的一致性级别是如何实现的。

由于我一边勉强写一边完成，可能会有些错误。欢迎大家纠正和提供反馈。