• Feeds

  • Posts Tagged ‘PNUTS’


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

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

    Resource

    1. Ryan Barrett, Transactions Across Datacenters
    2. Jeff Dean, Designs, Lessons and Advice from Building Large Distributed Systems (PDF)
    3. PNUTS: Yahoo!’s Hosted Data Serving Platform (PDF)
    4. Thoughts on Yahoo’s PNUTS distributed database
    5. Cassandra – A Decentralized Structured Storage System (PDF)
    6. Yahoo!的分布式数据平台PNUTS简介及感悟

    Yahoo!的分布式数据平台PNUTS简介及感悟

    在分布式领域有个CAP理论(Brewer’s CAP Theorem) ,是说Consistency(一致性), Availability(可用性), Partition tolerance(分布) 三部分在系统实现只可同时满足二点,没法三者兼顾。所以架构设计师不要把精力浪费在如何设计能满足三者的完美分布式系统,而是应该进行取舍,选取最适合应用需求的其中之二。比如MySQL 5.1 cluster设计前显然不知道有CAP理论这样的经验, 所以MySQL cluster表面看来尽管可提供所有分布式特性,但实际大部分场合都无法提供稳定可靠的服务。

    Yahoo!的PNUTS是一个分布式的数据存储平台,它是Yahoo!云计算平台重要的一部分。它的上层产品通常也称为Sherpa。按照官方的描述,”PNUTS, a massively parallel and geographically distributed database system for Yahoo!’s web applications.” PNUTS显然就深谙CAP之道,考虑到大部分web应用对一致性并不要求非常严格,在设计上放弃了对强一致性的追求。代替的是追求更高的availability,容错,更快速的响应调用请求等。

    1. PNUTS简介及特点

    • 地理分布式,分布在全球多个数据中心。由于大部分Web应用都对响应时间要求高,因此最好服务器部署在离用户最近的本地机房。
    • 可扩展,记录数可支持从几万条到几亿条。数据容量增加不会影响性能。
    • schema-free,即非固定表结构。实际使用key/value存储的,一条记录的多个字段实际是用json方式合并存在value中。因此delete和update必须指定primary key。但也支持批量查询。
    • 高可用性及容错。从单个存储节点到整个数据中心不可用都不会影响前端Web访问。
    • 适合存相对小型的记录,不适合存储大文件,流媒体等。
    • 弱一致性保证。

    传统的数据库提供强一致性保证, 通常称为“serialization transaction”,保证调用时序的一致性。但在web应用中不是必须,比如用户A修改了自己的资料或上传了图片,他的好友B短时间不能立即看到并不是大的问题,通常的Web应用都可以接受。PNUTS像大部分分布式key/value系统类似,提供的是弱一致性的支持,也就是支持“最终一致性(eventually consistent)”。用户B最终会看到用户A的修改信息。

    未够!但最终一致性并非可以适应所有场合,比如用户A修改了相册的访问权限,设置用户C不能访问,然后用户A又上传了新的图片,如果用户C处于另外一个IDC访问,如果图片数据先同步成功,而权限记录后同步的话,C实际上违反了A设置的权限而看到图片了。因此对于部分场合最终一致性是不够的。

    2. PNUTS实现

    2.1 Record-level mastering 记录级别主节点

    每一条记录都有一个主记录。比如一个印度的用户保存的记录master在印度机房,通常修改都会调用印度。其他地方如美国用户看这个用户的资料调用的是美国数据中心的资料,有可能取到的是旧版的数据。非master机房也可对记录进行修改,但需要master来统一管理。每行数据都有自己的版本控制,如下图所示。

    pnuts-4

    2.2 PNUTS的结构

    pnuts-1
    每个数据中心的PNUTS结构由四部分构成
    Storage Units (SU) 存储单元
    物理的存储服务器,每个存储服务器上面含有多个tablets,tablets是PNUTS上的基本存储单元。一个tablets是一个yahoo内部格式的hash table的文件(hash table)或是一个MySQL innodb表(ordered table)。一个Tablet通常为几百M。一个SU上通常会存在几百个tablets。
    Routers
    每个tablets在哪个SU上是通过查询router获得。一个数据中心内router通常可由两台双机备份的单元提供。
    Tablet Controller
    router的位置只是个内存快照,实际的位置由Tablet Controller单元决定。
    Message Broker
    与远程数据的同步是由YMB提供,它是一个pub/sub的异步消息订阅系统。

    2.3 Tablets寻址与切分

    存储分hash和ordered data store。
    pnuts-31
    以hash为例介绍,先对所有的tablets按hash值分片,比如1-10,000属于tablets 1, 10,000到20,000属于tablets 2,依此类推分配完所有的hash范围。一个大型的IDC通常会存在100万以下的tablets, 1,000台左右的SU。tablets属于哪个SU由routers全部加载到内存里面,因此router访问速度极快,通常不会成为瓶颈。按照官方的说法,系统的瓶颈只存在磁盘文件hash file访问上。
    当某个SU访问量过大,则可将SU中部分tablets移到相对空闲的SU,并修改tablet controller的偏移记录。router定位tablet失效之后会自动通过tablet controller重新加载到内存。所以切分也相对容易实现。
    Tim也曾经用MySQL实现过类似大规模存储的系统,当时的做法是把每条记录的key属于哪个SU的信息保存到一个字典里面,好处是切分可以获得更大的灵活性,可以动态增加新的tablets,而不需要切分旧的tablets。但缺点就是字典没法像router这样,可以高效的全部加载到内存中。所以比较而言,在实际的应用中,按段分片会更简单,且已经足够使用。

    2.4 API访问

    支持多种级别的数据访问API:
    • Read-any 读取的版本有可能是旧的,返回本地IDC的数据,不检查最新版本,性能最好。
    • Read-critical(required_version) 读取指定版本,用户修改资料之后调用返回比当前版本更新的版本,以保证当前用户看到的不是修改前的记录。
    • Read-latest 强制读取最新,可能需要执行远程IDC调用。比如上面例子介绍的读取权限列表的调用。
    • Write 比如更新用户资料
    • Test-and-set-write(required version) 只有当记录属于指定的版本才执行write,比如更新用户积分等业务,这个调用有点类似以前介绍的atom操作

    Write调用示意图pnuts-3

    3. PNUTS疑问

    记录级别master的问题,比如master选取如何达到效率最佳,如何面对2个修改合并冲突?合并冲突据说是需要client自行来处理,

    这篇Details on Yahoo’s distributed database提到的平均调用latency 100ms的问题。web应用通常对每次数据的访问最好在10ms之内完成,因为每个web页面实际上不止一个数据访问的调用,经常调用10次以上db的访问的页面并不少见,因此如果平均latency在100ms以上那势必影响页面加载速度。不过yahoo!的开发人员回复paper中的数据实际是一个老版本的测试,目前的版本,在实际生产环境的pnuts的latency会在10ms以下。

    另外PNUTS为什么要用消息系统代替replication/undo log?有何优点?

    4. PNUTS感悟

    Web应用使用通用的存储服务是大势所趋,类似BigTable, Amazon Dynamo/SimpleDB这样的方案,但是目前除非使用Amazon提供的商用SimpleDB之外几乎没有通用的解决方案,每个公司甚至每个项目需要面对及考虑数据规模增大的问题。比如初步统计下国内研究可扩展数据存储及访问的项目就有

    • 手机之家的数据访问层封装DAL 2.0
    • 盛大陈思儒写的开源项目Amoeba,类似MySQL proxy
    • 国内的Erlang geek @litaocheng 曾经对Dynamo paper深有研究,正在开发开源的erlang Dynamo实现e2dynoma
    • 豆瓣的doubanDB,也是类Dynamo实现

    当然上面几个只是冰山一角,大部分互联网公司都有自己的数据层分布及访问实现,只不过没有对外公开而已。架构师、DBA、程序员具备这方面的实践经验及技能当然是好事,但是如果业界能够有通用稳定的解决方案来解决大家的重复工作则对整个业界更佳。PNUTS虽然声称会开源,但是一直没有进一步消息。而且即使开源是是开放核心代码还是全部可用于部署的程序(比如YMB等)这也是一个问题。

    当然,我不是第一个也不是最后一个考虑这个问题的,比如2006年Greg Linden就说I want a big, virtual database

    What I want is a robust, high performance virtual relational database that runs transparently over a cluster, nodes dropping in an out of service at will, read-write replication and data migration all done automatically.

    I want to be able to install a database on a server cloud and use it like it was all running on one machine.

    参考资料