多IDC的数据分布设计(二)

标签： data consensus dynamo paxos PNUTS | 发表时间：2010-03-25 02:21 | 作者：Tim crystal

出处：http://timyang.net/

在前文《多IDC的数据分布设计(一)》中介绍了多IDC数据一致性的几种实现原理，遗憾的是，目前虽然有不少分布式产品，但几乎都没有开源的产品专门针对IDC来优化。本文从实践的角度分析各种方法优缺点。

背景资料 Latency差异

Jeff Dean提到不同数据访问方式latency差异

Numbers Everyone Should Know
L1 cache reference                           0.5 ns
Branch mispredict                            5 ns
L2 cache reference                           7 ns
Mutex lock/unlock                           25 ns
Main memory reference                      100 ns
Compress 1K bytes with Zippy             3,000 ns
Send 2K bytes over 1 Gbps network       20,000 ns
Read 1 MB sequentially from memory     250,000 ns
Round trip within same datacenter      500,000 ns
Disk seek                           10,000,000 ns
Read 1 MB sequentially from disk    20,000,000 ns
Send packet CA->Netherlands->CA    150,000,000 ns

这个数据对于我们设计多IDC数据访问策略具有关键的指导作用，我们可以用这个数据来衡量数据架构来如何设计才能满足高并发低延迟的目标。
这份数据实际上对所有网络应用及分布式应用开发者都具有很大借鉴作用，数据需要根据访问频率尽量放在latency小的地方。

1. 2PC/3PC/Paxos模式

在上文中提到，2PC/3PC相比Paxos有明显的缺点，因此最好不用于生产环境，这里就不再详述。
Paxos选择了CAP理论中的”Consistency, Partition”, 需要牺牲availability。它可以在多个IDC之间实现强一致性复制。

Paxos缺点

IDC之间需要高速稳定网络
一个2f+1个节点的网络中，需要f+1个节点完成事务才能成功。
Throughput低，不适合高请求量的场合。所以大部分分布式存储产品并不直接使用Paxos算法来同步数据。

2. Dynamo模式

Dynamo论文中并未专门描述Dynamo算法是否适合多IDC场景，只有少量文字提到

In essence, the preference list of a key is constructed such that the storage nodes are spread across multiple data centers. These datacenters are connected through high speed network links. This scheme of replicating across multiple datacenters allows us to handle entire data center failures without a data outage.

从上文看到，前提条件是“high speed network links” 可能对国内的情况不太适用。假如IDC之间网络不稳定，那会发生哪些情况呢？

Quorum 算法中，如果要考虑高可用性，则数据需要分布在多个机房。双机房如NRW=322由于单机房故障后可能会发生3个点中2个点都在故障机房，导致出现数据不可用的情况，所以合适的部署是NRW=533，需要3个机房。大部分请求需要2个机房节点返回才能成功，考虑到多IDC的带宽及latency，性能自然会很差。

Quorum算法在读写的时候都要从quorum中选取一个coordinator，算法如下

A node handling a read or write operation is known as the
coordinator. Typically, this is the first among the top N nodes in
the preference list. If the requests are received through a load
balancer, requests to access a key may be routed to any random
node in the ring. In this scenario, the node that receives the
request will not coordinate it if the node is not in the top N of the
requested key’s preference list. Instead, that node will forward the
request to the first among the top N nodes in the preference list.

如果严格按照Dynamo协议，coodinator一定要在N中第一个节点，那在3个机房中将有2/3的请求需要forward到异地机房的 coordinator执行，导致latency增大。如果对coodinator选择做优化，让client选取preference list中前N个节点中在本地机房的一个节点作为coordinator，这样会一定程度降低latency，但是会存在相同的key选择不同节点作为 coordinator的概率增大，导致数据conflict的概率增大。

同时在多机房模式下，Failure detection容易产生混乱。Dynamo并没有使用一致性的failure view来判断节点失效。而是由每个节点独自判断。

Failure detection in Dynamo is used to avoid attempts to
communicate with unreachable peers during get() and put()
operations and when transferring partitions and hinted replicas.
For the purpose of avoiding failed attempts at communication, a
purely local notion of failure detection is entirely sufficient: node
A may consider node B failed if node B does not respond to node
A’s messages (even if B is responsive to node C’s messages).

而最近非常流行的Cassandra基本上可以看作是开源的Dynamo clone, 它在Facebook Inbox Search项目中部署在150台节点上，并且分布在美国东西海岸的数据中心。

The system(Facebook Inbox Search) currently stores about 50+TB of data on a 150 node cluster, which is spread out between east and west coast data centers.

虽然在它的JIRA中有一个提案 CASSANDRA-492 是讲”Data Center Quorum”，但是整体看来Cassandra并没有特别的针对对IDC的优化，它的paper[5]中提到

Data center failures happen due to power outages, cooling
failures, network failures, and natural disasters. Cassandra
is configured such that each row is replicated across multiple
data centers. In essence, the preference list of a key is con-
structed such that the storage nodes are spread across mul-
tiple datacenters. These datacenters are connected through
high speed network links. This scheme of replicating across
multiple datacenters allows us to handle entire data center
failures without any outage.

跟Dynamo中的描述几乎是相同的。

3. PNUTS模式

PNUTS模式是目前最看好的多IDC数据同步方式。它的算法大部分是为多IDC设计。

PNUTS主要为Web应用设计，而不是离线数据分析（相比于Hadoop/HBase）。

Yahoo!的数据基本都是用户相关数据，典型的以用户的username为key的key value数据。
统计数据访问的特征发现85%的用户修改数据经常来源自相同的IDC。

根据以上的数据特征，Yahoo!的PNUTS实现算法是

记录级别的master, 每一条记录选择一个IDC作为master，所有修改都需要通过master进行。即使同一个表(tablet)中不同的记录master不同。
master上的数据通过Yahoo! Message Broker(YMB)异步消息将数据复制到其他IDC。
master选择具有灵活的策略，可以根据最新修改的来源动态变更master IDC，比如一个IDC收到用户修改请求，但是master不在本地需要转发到远程master修改，当远程修改超过3次则将本地的IDC设成master。
每条记录每次修改都有一个版本号(per-record timeline consisitency)，master及YMB可以保证复制时候的顺序。

Yahoo!的PNUTS实际可理解为master-master模式。
一致性：由于记录都需通过master修改，master再复制到其他IDC, 因此可达到所有IDC数据具有最终一致性。
可用性：

由于所有IDC都有每条记录的本地数据，应用可以根据策略返回本地cache或最新版本。
本地修改只要commit到YMB即可认为修改成功。
任一IDC发生故障不影响访问。

论文中提到的其他优点

hosted, notifications, flexible schemas, ordered records, secondary indexes, lowish latency, strong consistency on a single record, scalability, high write rates, reliability, and range queries over a small set of records.

总之，PNUTS可以很好的适合geographic replication模式。

记录publish到本地YMB则认为成功，免除Dynamo方式需要等待多个Data Center返回的latency。
如果发生master在异地则需要将请求forward到异地，但是由于存在master转移的策略，需要forward的情况比较少。

极端情况，当record的master不可用时候，实现上似乎有些可疑之处，读者可自行思考。

Under normal operation, if the master copy of a record fails, our system has protocols to fail over to another replica. However, if there are major outages, e.g. the entire region that had the master copy for a record becomes unreachable, updates cannot continue at another replica without potentially violating record-timeline consistency. We will allow applications to indicate, per-table, whether they want updates to continue in the presence of major outages, potentially branching the record timeline. If so, we will provide automatic conflict resolution and notifications thereof. The application will also be able to choose from several conflict resolution policies: e.g., discarding one branch, or merging updates from branches, etc.

初步结论

低带宽网络
PNUTS record-level mastering模式最佳。
高带宽低延迟网络
(1Gbps, Latency < 50ms)
1. 用Dynamo Quorum, vector clock算法实现最终一致性
2. 用Paxos实现强一致性

后记

本文从开始准备到发布时间较长，由于在多IDC数据访问方面目前业界并无统一的成熟方案，相关资料和文献也相对较少，而且对这方面有兴趣且有相应环境的人不多，短时间要提出自己成熟独立的见解也具有一定难度，本文仅包含一些不成熟的想法的整理，由于自己对文中的观点深度也不是满意，所以一直没有最终完稿发布。但考虑到最近工作较忙，暂时没有精力继续深入研究，所以希望公开文章抛砖引玉，同时也欢迎对这方面课题有兴趣者进一步交流探讨。