后端技术 by Tim Yang

Dynamo一个缺陷的架构设计(译)

Mar 1st, 2010 | 10 Comments
Filed under: data | Tags: dynamo, key value store

在云计算的时代，Dynamo可以说是一本实现分布式存储的红宝书，借鉴Dynamo实现的产品如雨后春笋般冒出。前段时间本人曾在Twitter上戏称

这年头，如果一个号称有“海量数据”的互联网公司，不做一个自己的Dynamo, 出去都不好意思跟人打招呼
(http://twitter.com/xmpp/status/8023241449)

另外一方面对于Dynamo设计思想也有不少反对的声音，比如2009/11/1在Hacker News上链接的一篇文章Dynamo: A flawed architecture引起不少争议，最后竟引起Amazon CTO Werner Vogels在Twitter上回应

Darn, someone figured out that Dynamo is a flawed architecture. Luckily its only use is storing hundreds of millions of shopping carts 🙂
(http://twitter.com/Werner/statuses/5345892061)
汗，有人发现Dynamo是一个缺陷的架构，幸运的是，我们只用它来存储了成百上亿的购物篮数据。:-)

以下是这篇批判Dynamo文章大部分中心观点，所翻译的观点并不代表Tim立场。

–译文开始–

Dynamo: A flawed architecture

在发表此文章之前，我也争论过Dynamo是否适合我们的系统。但是我很清楚这篇论文充满缺陷，它将错误的引导了读者让大家相信其设计，它的很多设计前后自相矛盾。下文会详细介绍这些缺陷。

Dynamo的最终一致性

首先，最终一致性对开发者意味什么呢？

写入的数据不能在后续的读操作中获取到。
写入的数据也有可能在后续的读操作中获取到，但读到后可能下一次又读不到。
因此对写操作后面的读取没有SLA(Service Level Agreement)保证。

举例说明，由于Dynamo是一个key value存储，我们假设value中存储的是一个list, 当list写入数据之后另外一个client却未读取到，这时候它需要写入数据的话只能重新构建一个新的list，添加要存的值并将新list存入，这就会导致老的list数据丢失。

(Update: 论坛上一些人指出，由于Vector Clock机制，数据丢失的场景不可能出现，我同意，不过我再提出几个其他问题。)

Cassandra未用vector clock, 而只用client timestamps也达到了同样效果。
Dynamo依赖合并冲突来解决此问题，一些场合下冲突很难解决。比如从list中错误的截取操作。(if deletion from the list is a valid operation – then how would one reconcile after mistaken truncation?)
另外一个场景，读取到脏数据后可能会影响后续的写入。(a stale read may end up affecting writes to other keys)

一般的常识是读取脏数据是需要避免的，但是Dynamo中无任何措施来避免读取脏数据以及避免读取脏数据的客户端再次写入，这个在单IDC环境其实是完全可以避免的。

Quorum一致性

(译者注：Quorum是Dynamo的一个核心特性，主要思想是写最小节点数W + 读最小节点数R > 所有节点数N)
Dynamo开始就提到系统按最终一致性设计，但是在4.5中却提出用Quorum的方法来实现一定程度的一致性，意思是如果R+W>N, 则读操作就具备(强)一致性了。明显是误导。由于节点会出现不可用的情况，尤其在跨IDC情况下，任一节点随时都有可能离开quorum组，当它离开再加入的时候，R个节点返回的数据就是不一致的，因为故障节点的数据只具备“最终一致性”，而在当时返回的只能是脏数据。

这就带来一个明显的问题，为什么要让未同步到最新数据的节点加入组？答案是Dynamo中无任何方法来判断一个节点是否数据同步，也无法判断有哪些数据不同步。因此只能做一个完全数据比较才能判断，Dynamo中用一种叫Merkle Tree的方法来实现，这个当然是一个代价昂贵且不灵活的操作，因为为了不影响Dynamo正常的读写业务，同步需要在后台执行。

实现强一致性也可以用读取所有节点(R=N)的方式来达到，不过有2个问题。

一旦有一个节点未同步，读取就会失败。
读取的代价极高。

我并不是第一个发现这些问题的人，比如另一知名的Cassandra产品Cassandra-225中就提到用一个中心commit log的方法来解决此问题。

WAN considerations 跨IDC的问题

值得指出的是，如果将Dynamo部署到多个机房，节点的断续情况会很容易发生。当一个节点连接不到，Dynamo的”hinted handoff”策略会使用一致性哈希算法将数据放入下一个节点。在多IDC环境下，下一节点通常在另一机房，因此会造成异地数据传输增加。当异地整个IDC都连不上网络分裂情况发生时，数据需要很长时间才能完全恢复。

Disaster Recovery 灾难恢复

Dynamo最终一致性及同步的设计对于是节点故障是有价值的，但是却无法估算有多少数据未同步。如果改用常规的commit log方式的话，很容易就能实现故障恢复并且计算未同步的数据量。

未使用时间一致性(译者：基于timestamp的合并？)在某些场合下很难合并冲突。

一致性还是可用性 Consistency versus Availability

一般认为Dynamo选择了CAP理论中的AP，而BigTable选择了CA。不幸的是，Dynamo并没有搞清什么是A(availability)和P(Partition Tolerance)。读者被误导只能在C和P中做一个取舍，这个当然是错的。我们很容易在单IDC实现一致性及高可用性。大部分商业数据库就是如此，HBase/HDFS也是如此。

很多人误以为即使在单IDC架构中，Dynamo方式比BigTable/GFS架构更合理。但Dynamo的优势其实是在多IDC。

中心化还是去中心化

Dynamo中提到

In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.
过去，中心化设计导致了很多灾难，我们意识到要远离中心化。去中心化后，系统会更简洁，更具有可扩展性及高可用性。

中心化确实会形成瓶颈，但是没有证据说明中心化就低可用性。大部分专业的存储系统通过双机热备的方式都具备高可用性。简单的说，只需要所有中心模块(电源，主板，RAID，交换机等)都按双份的方式来设计，只需要额外增加一点硬件成本，这些系统基本可以达到5个9的可用性。

值得讽刺的是Dynamo其实在部分情况下还是一个中心化的体系，如交换机故障发生了网络分片，服务器分成2个独立的小网，这时候Dynamo对客户端是不可用的，尽管客户端可以连接上Dynamo。

更讽刺的是我们看到Dynamo很多一致性问题都是去中心化设计所导致。

–译文完–

此文的讨论也非常精彩，对于想深入了解Dynamo的朋友是不可多得的资料。可参看 http://news.ycombinator.com/item?id=915212

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

Feb 2nd, 2010 | 18 Comments
Filed under: 分布式 | Tags: 2PC, 3PC, consensus, paxos, Three-phase commit, Two-phase commit

上个月跟某个朋友谈及多IDC数据同时读写访问的问题(tweet)，当时觉得有不少解决方案，但觉得思路还不够清晰。最近看了Google App Engine工程师Ryan Barrett介绍GAE后端数据服务的演讲稿Transactions Across Datacenters(视频)，用Ryan的方法来分析这个问题后就豁然开朗。

按Ryan的方法，多IDC实现有以下几种思路。

一、Master/slave

这个是多机房数据访问最常用的方案，一般的需求用此方案即可。因此大家也经常提到“premature optimization is the root of all evil”。
优点：利用mysql replication即可实现，成熟稳定。
缺点：写操作存在单点故障，master坏掉之后slave不能写。另外slave的延迟也是个困扰人的小问题。

二、Multi-master

Multi-master指一个系统存在多个master, 每个master都具有read-write能力，需根据时间戳或业务逻辑合并版本。比如分布式版本管理系统git可以理解成multi-master模式。具备最终一致性。多版本数据修改可以借鉴Dynamo的vector clock等方法。

优点：解决了单点故障。
缺点：不易实现一致性，合并版本的逻辑复杂。

三、Two-phase commit(2PC)

Two-phase commit是一个比较简单的一致性算法。由于一致性算法通常用神话(如Paxos的The Part-Time Parliament论文)来比喻容易理解，下面也举个类似神话的例子。

某班要组织一个同学聚会，前提条件是所有参与者同意则活动举行，任意一人拒绝则活动取消。用2PC算法来执行过程如下

Phase 1

Prepare: 组织者(coordinator)打电话给所有参与者(participant) ，同时告知参与者列表。
Proposal: 提出周六2pm-5pm举办活动。
Vote: participant需vote结果给coordinator：accept or reject。
Block: 如果accept, participant锁住周六2pm-5pm的时间，不再接受其他请求。

Phase 2

Commit: 如果所有参与者都同意，组织者coodinator通知所有参与者commit, 否则通知abort，participant解除锁定。

Failure 典型失败情况分析

Participant failure:
任一参与者无响应，coordinator直接执行abort
Coordinator failure:
Takeover: 如果participant一段时间没收到cooridnator确认(commit/abort)，则认为coordinator不在了。这时候可自动成为Coordinator备份(watchdog)
Query: watchdog根据phase 1接收的participant列表发起query
Vote: 所有participant回复vote结果给watchdog, accept or reject
Commit: 如果所有都同意，则commit, 否则abort。

优点：实现简单。
缺点：所有参与者需要阻塞(block)，throughput低；无容错机制，一节点失败则整个事务失败。

四、Three-phase commit (3PC)

Three-phase commit是一个2PC的改进版。2PC有一些很明显的缺点，比如在coordinator做出commit决策并开始发送commit之后，某个participant突然crash，这时候没法abort transaction, 这时候集群内实际上就存在不一致的情况，crash恢复后的节点跟其他节点数据是不同的。因此3PC将2PC的commit的过程1分为2,分成preCommit及commit, 如图。

(图片来源：http://en.wikipedia.org/wiki/File:Three-phase_commit_diagram.png)

从图来看，cohorts(participant)收到preCommit之后，如果没收到commit, 默认也执行commit, 即图上的timeout cause commit。

如果coodinator发送了一半preCommit crash, watchdog接管之后通过query, 如果有任一节点收到commit, 或者全部节点收到preCommit, 则可继续commit, 否则abort。

优点：允许发生单点故障后继续达成一致。
缺点：网络分离问题，比如preCommit消息发送后突然两个机房断开，这时候coodinator所在机房会abort, 另外剩余replicas机房会commit。

五、Paxos

Google Chubby的作者Mike Burrows说过， “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一种一致性算法，那就是Paxos”，所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC, Paxos算法的改进

P1a. 每次Paxos实例执行都分配一个编号，编号需要递增，每个replica不接受比当前最大编号小的提案
P2. 一旦一个 value v 被replica通过，那么之后任何再批准的 value 必须是 v，即没有拜占庭将军(Byzantine)问题。拿上面请客的比喻来说，就是一个参与者一旦accept周六2pm-5pm的proposal, 就不能改变主意。以后不管谁来问都是accept这个value。
一个proposal只需要多数派同意即可通过。因此比2PC/3PC更灵活，在一个2f+1个节点的集群中，允许有f个节点不可用。

另外Paxos还有很多约束的细节，特别是Google的chubby从工程实现的角度将Paxos的细节补充得非常完整。比如如何避免Byzantine问题，由于节点的持久存储可能会发生故障，Byzantine问题会导致Paxos算法P2约束失效。

以上几种方式原理比较如下

(图片来源：http://snarfed.org/space/transactions_across_datacenters_io.html)

后文会继续比较实践环境选取何种策略合适。

（PS: 写完后在Google Reader上发现本文跟王建硕最近发表的《关于两个机房的讨论》文章有点类似，特别是本文一、二方式。不过他的文章偏MySQL的实现，我的重点是一致性算法，大家可以有选择性的阅读。）

用Twitter的cursor方式进行Web数据分页

Jan 19th, 2010 | 16 Comments
Filed under: Web | Tags: mysql, performance, twitter

本文讨论Web应用中实现数据分页功能，不同的技术实现方式的性能方区别。

上图功能的技术实现方法拿MySQL来举例就是

select * from msgs where thread_id = ? limit page * count, count

不过在看Twitter API的时候，我们却发现不少接口使用cursor的方法，而不用page, count这样直观的形式，如 followers ids 接口

URL:
http://twitter.com/followers/ids.format
Returns an array of numeric IDs for every user following the specified user.

Parameters:
* cursor. Required. Breaks the results into pages. Provide a value of -1 to begin paging. Provide values as returned to in the response body’s next_cursor and previous_cursor attributes to page back and forth in the list.
o Example: http://twitter.com/followers/ids/barackobama.xml?cursor=-1
o Example: http://twitter.com/followers/ids/barackobama.xml?cursor=-1300794057949944903

http://twitter.com/followers/ids.format

从上面描述可以看到，http://twitter.com/followers/ids.xml 这个调用需要传cursor参数来进行分页，而不是传统的 url?page=n&count=n的形式。这样做有什么优点呢？是否让每个cursor保持一个当时数据集的镜像？防止由于结果集实时改变而产生查询结果有重复内容？
在Google Groups这篇Cursor Expiration讨论中Twitter的架构师John Kalucki提到

A cursor is an opaque deletion-tolerant index into a Btree keyed by source
userid and modification time. It brings you to a point in time in the
reverse chron sorted list. So, since you can’t change the past, other than
erasing it, it’s effectively stable. (Modifications bubble to the top.) But
you have to deal with additions at the list head and also block shrinkage
due to deletions, so your blocks begin to overlap quite a bit as the data
ages. (If you cache cursors and read much later, you’ll see the first few
rows of cursor[n+1]’s block as duplicates of the last rows of cursor[n]’s
block. The intersection cardinality is equal to the number of deletions in
cursor[n]’s block). Still, there may be value in caching these cursors and
then heuristically rebalancing them when the overlap proportion crosses some
threshold.

在另外一篇new cursor-based pagination not multithread-friendly中John又提到

The page based approach does not scale with large sets. We can no
longer support this kind of API without throwing a painful number of
503s.

Working with row-counts forces the data store to recount rows in an O
(n^2) manner. Cursors avoid this issue by allowing practically
constant time access to the next block. The cost becomes O(n/
block_size) which, yes, is O(n), but a graceful one given n < 10^7 and
a block_size of 5000. The cursor approach provides a more complete and
consistent result set.

Proportionally, very few users require multiple page fetches with a
page size of 5,000.

Also, scraping the social graph repeatedly at high speed is could
often be considered a low-value, borderline abusive use of the social
graph API.

通过这两段文字我们已经很清楚了，对于大结果集的数据，使用cursor方式的目的主要是为了极大地提高性能。还是拿MySQL为例说明，比如翻页到100,000条时，不用cursor，对应的SQL为

select * from msgs limit 100000, 100

在一个百万记录的表上，第一次执行这条SQL需要5秒以上。
假定我们使用表的主键的值作为cursor_id, 使用cursor分页方式对应的SQL可以优化为

select * from msgs where id > cursor_id limit 100;

同样的表中，通常只需要100ms以下, 效率会提高几十倍。MySQL limit性能差别也可参看我3年前写的一篇不成熟的文章 MySQL LIMIT 的性能问题。

结论

建议Web应用中大数据集翻页可以采用这种cursor方式，不过此方法缺点是翻页时必须连续，不能跳页。