存储云概念
存储云依我看就是一个被商业包装过的分布存储系统——只不过它对第三方用户公开存储接口，用户可买容量和带宽，且规模相当宏伟的分布存储系统。关于商业模式问题我们就不多作探讨了，大家可到其网站上仔细瞧瞧。我这里的重点是对用于存储云的分布存储系统作对比分析。（不过假如你对存储云完全不了解，那我建议在看下面内容之前，先去读读相关的论文什么的介绍吧！以便我们的讨论事半功倍。）
存储云结构比较——Dynamo VS Bigtable
比较典型的存储云基础系统有Amazon公司的Dynamo系统与Google公司的Bigtable系统，这两种系统不但已经开始是商用（参见S3 服务和 Google App Engine服务），而且都公开了比较详细的实现论文（尤其dynamo系统论文格外详尽——可见Amazon公司的无私和自信）。它们各自实现架构迥异，存储特性不一，但都结构优美，技术上各有可称道的地方，可谓各有千秋，却又殊途同归。
下面我们将针对它们两者存储数据的要求、体系架构、扩容、负载均衡、容错、数据存取及查询等我觉得重要的方面进行一些点到为止分析比较，以辨明良莠。
数据结构化问题
首先要提到的是两者存储数据属性上的区别，虽然两者都是以key/value形式进行存储，但Dynamo偏向存储原数据，因为其所存储的数据是非结构化数据，对value的解析完全是用户程序的事情，Dynamo系统不识别任何结构数据，都统一按照binary数据对待；而Bigtable存储的是结构化或半结构化数据（web数据特点就是介于结构化和非结构化之间，因此称为半结构化数据。我这里不展开说它了，不了解半结构化数据的赶紧去google一下吧！），其value是有结构的数据——就如关系数据库中的列一般，因而可支持一定程度的Query(比如可按单列进行）。这点上看Bigtable更接近数据库（接近而不是等价！至于和关系数据库的具体区别可去google 一下，网上论述可不少！）；另外, Bigtable所存储的数据都是以字符串格式实现，所以对主建或者列（以及其自动加上的时间戳）排序都是以字符序进行，而dynamo的键值并非以字符串存储，而是统一经过md5算法转后成16字节md5_key存储的，因此对数据的访问必须知道key才可进行，故而对扫表(用游标）或者query访问则无能为力。当然在dynamo的基础上，配合一些方式我们实现query也并不可能，一些具体方式我们后面慢慢探讨！
控制与存储架构比较
Dynamo是采用DHT（分布哈希表，请参看有关资料吧）作为基本存储架构和理念，这个架构最大特点是能让数据在环中“存储”均匀，各存储点相互能感知（因数据需要在环内转发，以及相互之间进行故障探测，因此需要节点之间的通讯），自我管理性强，因为它不需要Master主控点控制，有点是无热点，无单点故障危险——插一句，目前新浪的memcachedb(改造memcached，增加了持续化能力）其实可认为是这种架构的最简单代表（数据进入系统后，使用DHT算法均匀的发送到存储节点上，而最后存储引擎采用Berkelery DB，将数据持续化到本地硬盘）。
Bigtable的控制是采用传统的server farm形式，使用一个主控服务器＋多个子表服务器构成。而数据存储形式是采用多维Map的稀疏结构,可看成是由多个列表组成，所谓稀疏是说每条记录并非要求有全列。其数据（包括索引，日志，记录数据）最终是存储在分布文件系统DFS之上——数据被以DFS所特有的文件形式分布存储在各各节点之上。相比DHT的存储环自管理技术，它需要有master主控服务器来负责监控各客户存储节点（分配子表，失效检测，负载均衡等），另外索引文件的根也是集中存储，需要客户端首先读取（之后可以采用预读和缓存的技术减少读取索引表的次数）。这种集中控制的做法有一个缺陷就是系统存在单点故障 —— 因此单点需要高可用性，如记录恢复日志或双机备份等——但好处是更人为可控，方便维护，且集中管理时数据同步易于方便——显然，更新集中存储的原数据（如数据索引或节点路由等）相比DHT环中各个节点存储的原数据（如membership，即各点的路由关系）需要利用“闲谈机制”依次通知式地进行渐近更新要容易许多。
容错问题
Dynamo和Bigtable都不是实验室应付领导参观，或者是炫耀技术的Demo，而是要实实在在进行商业运营的产品，因此首先要考虑的是机器成本问题！最节约的方式就是采用普通PC服务器（目前市场价格大约2／3千元就能买到存储1T数据的机器——自然是没有显示器，声卡这些外设的）作为存储机器。但做过大数据处理的人都知道，IDE/STAT硬盘的稳定性和寿命是无法和真正服务器中的SCSI硬盘相媲美（除硬盘外的其余部件的稳定性和寿命也一样和服务器差距颇大），在压力下损坏那是家常便饭——据Google说，1000台机器的集群中，平均每天坏掉一台机器——因此设计之初就将硬件故障认为是常态的，也就是说容错成为设计优先考虑的问题了。
鉴于上述原因，Dynamo和Bigtable的数据都是冗余存放，也就是说一份数据会被复制成数份（副本数是可以根据数据要紧程度指定的），并被分散放在不同的机器上，以便发生机器宕机（偶然性宕机或网路不通属于临时故障，而硬盘坏掉则是永久故障，永久故障需要进行故障恢复——从副本恢复数据）时还有可用副本可继续提供服务——通常存放三个副本就已经可以高枕无忧了，因为要知道三个副本同期坏的可能性小到了1000*1000*1000分之一。
Dynamo 的冗余副本读写策略比较有趣，它定义了：N,W,R三个参数。其中N代表系统中每条记录的副本数，W代表每次记录成功写操作需要写入的副本数，R代表每次记录读请求最少需要读取的副本数。只要W+R >N就可以保证数据的一致性。因为W+R>N时读写总会有交集——必定最少有W＋R－N个读请求会落到被写的副本上，所以必然会读到“最后”被更新的副本数据（至于谁
“最后”的判断需采用时间戳或者时钟向量等技术完成——有逻辑关系先后由时钟向量判断，否则简单的用时间戳先后判断.详情去看dynamo论文吧）。这种做法相比我们最朴素的想法——我们直观的想法一定认为如果系统要求记录冗余N份，那么每次就写入N份，而在读请求时读取任意一份可用记录即可——要更安全，也更灵活。说其更安全是指数据一致性更能被保证：比如说客户写入一条记录，该记录有三个副本在三个不同点上，但是其中一个点临时故障了，因此记录没有被写入／更新。那么在对该记录再读取时，如果取两点（R=2）则必然会读取到最少一个正确的值（临时故障点有可能在读是恢复，那么读出的值则不存在或者不是最新的；若临时故障点还未恢复，则读请求无法访问其上副本）。而使用我们传统方法可能读到发生临时故障的那点，此刻就有可能读出现错误记录（旧的或者不存在），因此可以看到加大W,R可提高系统安全性；说其更灵活则是指可通过配置N,W,R这几个参数以满足包括访问方式、速度和数据安全等迥异需求的各种场景：比如对于写多读少的操作，可将W配低，R配高；想法对于写少读多的操作，则可将W配高，R配低。
Bigtable的容错问题论文中没有详细讲，我想它应该是将该任务交给其下的DFS处理了：DFS是在文件chunk（64M）写入chunk服务器时，将数据chunk传播给最近的N-1个chunk服务器，从而确保了系统中每个chunk存在多个副本，而这些chunk 的位置信息都会记录在master服务器的文件原数据中。再访问文件时，会先获得原数据，再从可用的chunk服务器中获取数据，因此一个chunk server发生故障不影响数据完整性，照样能读。另外DFS的故障的恢复等工作也是在master服务器监控下将某个副本chunk进行复制，以恢复故障机器上的数据副本。
最后值得提一下的是，Dynamo对于临时故障的处理方式是：找到一台可用机器，将数据暂时写到其上的临时表中，待临时故障恢复后，临时表中的数据会自动写回原目的地。这样做得目的是达到永远可写（那怕该云中只有一台机器可用，那么写请求的数据就不会丢失）。这个需求未见Bigtable提到，但从其架构上看DFS对写操作来说，应该也是能达到接近Dynamo的永远可写需求的（master会帮助选择一个可写的chunk server 作为写请求的接受者的，因此系统只要master不可用，最少再有一台可用chunk server机器就以满足。
扩容问题
对于一个存储可视为无限大的存储系统来说，扩容需求（扩容需求除了存储容量不足外，存储节点并发处理能力不足，也会要求扩容）自然无法逃避，而且对于在线服务系统扩容时期要尽量不停止服务或者尽可能短的停止服务，因此优美的扩容方案是存储云中最值得关注的要点之一。
我们还是先来说说Dynamo系统的扩容策略和实现。试想一下，将一个机器中的指定数据表扩容，首先需要将这个数据表劈开成两个表，然后再把其中一个转移到另外一台新机器上去。而这里的劈表动作说起简单，作起来则颇为费力，因为无论数据表是按照键值区间有序组织（如DHT环方式),或键值本身有序组织（如Bigtable方式)，都不可避免的需要扫描整个数据表（特耗资源的操作，绝对会影响其他服务的）才能从中挑选出一部分有序数据移到新表中，从而保证劈开后的两个表仍然维持有序结构。为了避免笨拙的扫表工作，Dynamo取巧了，它会将md5 key所围成的环行区间，尽量划分的粒度细一些，也就是多分成一些较小的区间／段（一个段对应存在硬盘上的一个数据表），但是要求一个物理机器不只存储一个段，而是存储连续区间的一组段表，这样以来在扩容时就能将劈大表的操作给回避了。比如将环分成1024段（存储数据上规模时，实际部署时段表要分的更细致得多），然后又规定每个存储点维护64个段表，那么全部数据起先可部署在 16个机器的存储环上。如果发现某个机器存储不下64个段表时（或者承受不了当前的并发请求量时），则将其中部分段表转移到新扩容的机器上去即可，比如从原机器上转移32个段表拷贝到新机器即可完成扩容——这种小表迁移避免了对大表拆分时的扫表、劈表动作。当然你会说这种扩容有限制，只能扩容6次。没错,因此在实际存储环之初,是需要估计数据总量,扩容次数等问题的,但这绝对值得。Dynamo除了段表思想值得学习外，还提出了扩容期间不停服务这种要求很是可爱。我们也尝试过这种高可用性扩容设计，其主要任务是要理清楚，从而细致处理扩容期间(包括数据扩容和路由更新)的访问请求的状态机。另外要说的是扩容时为了不影响正常请求访问, 都将扩容例程安排在低优先级进行, 让它在正常读写请求压力小时再偷偷进行！
对于Bigtable扩容问题Google本身的论文描述有些暧昧，但却可在另一个类Bigtable系统——hypertable——那里看到比较清晰的说法。Hypertable是Bigtable的开源C++实现。由于Hypertable中记录存储是被集合成固定大小的tablet（默认的最大值是每个200M）存在DFS上——而DFS本身具有可扩容性（允许在线添加新机器到server farm中）—— 因此Hypertable存储总空间的扩容不存任何问题。其要作的只是当子表（Range段)过大时，需要将其从中间key 劈开成两个新表，把包含后半段key范围的新字表迁移到别的range server上去。注意这种分子表的实现路数似乎仍然需要去扫描表，在这一点上我个人认为不如Dynamo做的聪明、利索。关于hypertable的表的管理值得大家去留心，但这里不多说了。(请看hyptertable 站点：
http://www.hypertable.org/documentation.html/)
负载均衡问题
负载均衡（意义在于数据存储均衡和访问压力均衡）对于Dynamo系统而言是天生的优势，因为它采用了DHT方式将数据都均匀存储到各个点了，所以没有热点在（或者说要热，则环中所有的点一起热），各点的数据存储量和访问压力应该都是均衡的（这点由md5算法特性决定）。 另外这里还要提一下Dynamo系统中的Virtual Node概念——VNODE 可看成一个资源容器（类似于虚拟机），存储作为一个服务运行于其中。引入VNODE 目的在于将资源管理粒度单元化。 比如一个VNODE 让你且只让你管理5G硬盘，500M内存等，那么你就只能使用这么多资源。这样有两个显而易见的好处：1 方便管理不同配置的异构机器，比如资源多的机器多部署一些VNODE ,而资源少的机器少不部署一些VNODE 。 2 对于扩容大有好处，因为DHT环中加入一个新节点，如果想保持数据均匀分布的特性，那么必须将全环的数据都要移动才有可能，这样无疑增加了网络震荡，因此最理想的方式是在环内每个点都进行扩容，这样就只需要移动旁边节点的数据了。那么单增加一个或几个机器显然不能均匀分配环的其他存储点旁，因此需要将一台物理机器划分成众多个VNODE ，这样才有可能能将这些VNODE 比较均匀的散布在环内其他节点旁了。随着逐步添加机器，那么数据均匀性逐步提高，可见这是一种逐渐式的数据均衡过程。
对于Bigtable的负载均衡是也是基于传统上server farm ：依靠一个master服务器监视子表 server的负载情况，根据所有子表服务器的负载情况进行数据迁移的，比如将访问很热的列表迁移到压力轻的子表服务器上(数据最终还是落在了chunk server —— DFS上的存储服务点，从层级结构上来说处于子表服务器之下）。具体做法你可参见他们的论文，总的来说有没有太多创新。
数据存取和查询问题
Dynamo和Bigtable两种体系都支持key/value形式的记录插入，而且也支持主建的随机查询。不过前面已经提到了如果需要按照列进行查询，或者需要range的query查询，则Dynamo就无能为力了，只能使用Bigtable架构（但要知道Bigtable并没有关系数据那么强，对于query的支持也仅仅是支持条件是单个列，不能以多列为目标进行复合条件查询，更别说join查询等）。从这点上说bigtable更接近数据库，而Dynamo则是一个简单的存储系统。
amazon在S3(可能基于Dynamo)之后，推出了支持query的Simpledb 系统。 该系统和Bigtable很类似，但似乎功能更强，它支持=, !=, <, > <=, >=, STARTS-WITH, AND, OR, NOT, INTERSECTION AND UNION等复杂的query 操作。这真是个出色的产品，不幸的是amazon并没有向对Dynamo那样慷慨的公开发表其实现的论文，因此大家只能猜测其实现，有的说是在Erlang上重写的，有的说在Dynamo基础上开发的，有的说是抛开Dynamo全新实现的,目前说法众多，无从得知。这里我仅仅就我个人的认知，谈谈假如在Dynamo上是如何实现Query功能类似的功能。
首先能想到的是为Dynamo增加schema，也就是将value划分成逻辑列，这样以来在存储时可以按列建立索引文件，那么就自然可以实现对列的 query。索引文件内容可以是列值到主建集合的映射，其存储以文件形式存在于分布文件系统之上。当对列进行query时，首先在索引文件中找到对应的主建集合，然后在以主建从Dynamo中获得记录。不过这样作有一定限制： 1 分布文件系统需要能支持并发修改文件能力（因为索引文件需要频繁改变），而大多数分布文件系统为了数据一致性和效率的考虑，都只能支持并发追加操作，因此要想实时的完成数据更新的同时支持查询操作有难度——简单的方法是定期更新索引文件，那么副作用就是查询的结果不是最新的；2 只能对预先建立索引的单列进行排序（当然可以建立联合索引），并不能支持对任列，或者任意的复合条件完成query查询——我是没想到什么好办法。
另外一个方法是使用关系数据库作Dynamo的存储引擎——如果你看过Dynamo的论文，可否记得它提到了实际的存储引擎可使用Berkelery DB或者mysql等 ——，那么在存储环中进行查询的操作可化整为零：将查询任务路由到各各存储节点上分别进行查询之后，再将结果收集起来，对于需要排序的请求则还要再集中进行排序一次。这种做法把索引等等的工作都交由关系数据库去作，我们作的只是需要汇总结果。 在这个思路上可以进一步结合数据分发Partition策略：不再按照md5 key那样在节点上均匀的存放数据，而是按照列作partition 篇分发数据，如地址属性中的Beijing,xi an等不同地名的数据路由到指定不同节点上，那么在按地名进行查询时，则可以直接将请求下发到对应存储节点，这样避免了全环下发查询人物，能更有效的完成以列为条件的复杂查询。除此外，还可以对列进行区间排序partation,如对年龄列，按照0－10岁一个区间，10－20一个区间，20－30一个区间，而每个区间存储在不同节点上，这种有序区间部署方法可支持按列排序查询要求。不过有得必有失，partition存放的缺点是数据不够均匀，因此负载不平衡，所以需要能把partation节点纵向扩容，比如把负责20－30区间的存储节点多搞几个以分担并发压力。
