由于单一的服务器无法存储数百TB的数据，无法每秒处理百万级的并发请求，分布式存储系统应运而生。例如截至08年09月，eBay存储了超过2PB的数据,每天需要处理25PB数据，执行480亿次SQL查询。另外，出于规模经济的原因，大的数据中心比小的数据中心有显著的成本优势：在一个5万台服务器的数据中心和1千台服务器的数据中心相比较，平均网络带宽和管理成本前者是后者的1/7.1，而平均存储成本则只有后者的1/5.7。存储系统中数以万计的服务器，使得任何组件出现短暂或永久性故障都成为常态，网络的时延、带宽、成本约束，应用对高性能、高可用、高延展性、易于管理的要求，都对分布式存储系统的设计提出了严峻的挑战。
问题的来源
为了应对各种失效情况，提高可用性和性能，降低通讯成本，通常采用数据的冗余策略，而副本（采用多台失效相互独立的服务器）和纠删码是两种常用的方式。这样即使其中一些复本失效或出现网络分隔(Network Partition)的情况，用户也可以访问到一些服务器，从而继续操作。通过服务器复本以及协调客户端与服务器复本间的交互,复本状态机（Replication State
machine）成为实现容错服务的通用方法。Chubby[OSDI'06,PODC'07], ZooKeeper[Apache]和Boxwood
[OSDI’04]等服务都使用了复本状态机。这种方式也提供了用来理解和设计复本管理协议的架构。许多协议都包含了数据或软件的复本,用于屏蔽错误或者在没有中心控制的情况下协作。确定性(Deterministic)是一种理想可以提供容错的性质。直观上，如果一个系统有多个复本存在，错误很容易因不同复本的状态或输出不同而被发现。通常需要2F+1的节点来纠正F个错误节点的情况。特别的，如果失效复本不产生输出，则只需要F+1个复本。拜占庭错误是指错误节点会向不同节点产生不同输出，错误节点可以产生随机、伪造的错误或者恶意、有智能的攻击。这种情况至少需要3F+1才能纠正F个错误节点产生的错误信息，也即著名的Byzantine-Fault
Tolerance (BFT)问题。对于一个确定的服务，服务器状态和要执行的功能都复制到一个服务器集合中每台服务器复本，复本间使用协商协议（consensus protocols）就要执行的命令达成一致。常用的协商协议有Paxos、Fast Paxos[Distributed Computing'06]和CoReFP，Mencius[OSDI'08]是一种来源于Paxos的用于广域网的多领导状态机复本协议，以达到在高负载时达到高吞吐率、低负载时低时延的目的，自适应变化的网络和负载状况。近年，如OSDI’06、OSDI’08、NSDI‘09都有关于复本状态机相关的论文。特别对于BFT问题，SOSP'07、NSDI’08、NSDI'09都设有专题讨论，ICDCS'08和USENIX’09也有相关论文。MIT、CMU、RICE、德克萨斯大学、Intel、Microsoft都有学者从事相关研究，成为近年学术前沿的研究热点问题。例如，Zeno[NSDI'09]通过弱化一致性，来提高BFT的性能和可用性。德克萨斯大学奥斯汀分校的Allen Clement等人在NDSI'09的论文中发现现有BFT协议无法有效应对客户端的恶意请求，由此提出容忍拜占庭错误的BFT系统。
根据CAP理论（Consistency, Availability, and Partition-tolerance），数据一致性，数据的可用性和网络分隔容忍三者最多只能满足其中的两个。数据的一致性是指用户总是得到正确的数据；数据的可用性是指用户总是能够得到相应；网络分割容忍是指允许网络丢失节点间的任意消息。当网络分裂时，从一个网络分区节点发往另一网络分区中节点的消息都会丢失。对于只读存储系统，数据一致性很容易得到保障；而对于可以执行更新操作的存储系统，为保证业务逻辑的正确性，必须设计恰当的数据一致性模型，使一致性得到某种程度的保证。传统的关系性数据库通过提供我们熟知的串行化事务来提供并发操作的数据一致性。但是对于分布式系统，提供串行化事务在性能和可用性上是不可行的。而根据Yahoo!的许多Web应用的经验，这些应用倾向于每次操作一条记录，通用的事务机制通常并不需要；例如，用户更改个人形象，上传一张图片，邀请若干好友发起会议，即使新的个人形象对于一个好友没有马上可见，也是没有多少影响的。事实上许多分布式复本系统只提供了最终一致性（eventual consistency）：客户端每次更新时，只需更新该对象的任一复本；系统只保证该对象的所有更新最终会应用到每个复本，而对于不同复本，更新顺序可能不同。但是，这种最终一致性通常太弱，而不适用于例如Web等应用。例如Amazon的Dynamo利用Vector clocks 在读取时重新排列更新以解决某些更新冲突，而Yahoo!的PNUTS，提供每记录的时间轴一致性模型来提供不同等级的一致性。而WheelFS允许应用程序通过语义线索（semantic cues）控制数据一致性。
分布式存储系统的分类
按照系统功能可以划分为：归档/备份、通用文件系统、发布/共享、高性能等等。按照存储架构：Client/Server、P2P;其中P2P架构又可划分为全局中心架构、本地中心架构和纯P2P架构。也可以按照操作环境，使用模式，对于数据一致性的要求，安全性，自动管理，路由策略和网络环境等进行分类。总的来说，根据应用场景，可以分为由广域网、非信任节点组成的存储系统和面向数据中心的存储系统。不同存储系统提供的接口也不同，有分层（文件系统）命名空间和扁平（P2P）命名空间；有的提供复杂的结构化查询，有的只提供简单的key-value查询。另外存储系统的节点规模、类型（PC或Server）、地理分布及网络连接方式也可以做为分类依据；有的提供开放的协议，而有的完全私有。另外，不同存储系统的业务需求，I/O模式也千差万别：有的是只读系统，有的则要求支持更新操作；不同应用对I/O时延的要求也不相同；例如对于电子商务，为了良好的用户体验，必须提供“总是可写”的方式，并且用户的请求必须在数百毫秒内的得到相应。下面就近年出现的工业界和学术界的存储系统大致归类：
广域网、非信任节点
Oceanstore, CFS, PAST, Ivy[OSDI’02],Glacier[NSDI'05],TFS[FAST'07],WheelFS
[NSDI'09,MIT]，CA-NFS [FAST’09]
数据中心
分布式虚拟磁盘: Petal [lee’96]
分布式文件系统 : CEPH [OSDI'06], Farsite [Microsoft]
集群文件系统 : Sorrento [Supercomputing'04], Panasas [FAST'08], GoogleFS
[SOSP'03]
集群存储系统 : Ursa Minor [FAST '05], RADOS [PDSW '07], and FAB [SIGOPS'04].
Dynamo (SOSP’07,Amazon)，PNUTS (VLDB'08,Yahoo!)
次级存储系统
归档:Venti
[FAST '02], EMC Centera, Pergamum [FAST'08]
备份:
Pond[FAST'03],DataDomain [FAST'08] ,Cumulus[FAST’09]，SafeStore[USENIX’07],
归档+备份
: HYDRAstor [FAST'09]
其他：
Antiquity (EuroSys‘07, Berkeley),TieStore [FAST‘08] , Carbonite
[NSDI’06],Cimbiosys(NSDI'09)，BitVault[SIGOPS'07]
主要存储系统简介
Coda：支持离线操作，C/S模式
CFS : 只读文件系统, CHORD,文件分块，存储数据块到负责节点及K个后继节点.
PAST：只读文件系统，Pastry，根据文件ID，存储文件到负责节点及K个后继节点
Low-Bandwidth File System (LBFS)：改进ＮＦＳ协议以降低带宽需求，关注一致性而不是在网络分割存在时的可用性
Farsite：创建一个可扩展的无服务器的分布式文件系统来提供中心化的NTFS文件服务器语义，并用POSIX协议严格兼容。Farsite的节点由同一大型组织的桌面计算机组成，基于高速低时延的网络环境，并能处理拜占庭失效问题。
TieStore（FAST’08,Berkeley）面向带宽受限、间断连接，利用DTN（Delay Tolerant Networking）的存储-转发网络组织覆盖网。
WheelFS 广域网文件系统，通过坚持“全局读，本地写”来降低通讯成本，提供语意线索由应用定制对时延、一致性等的需求。
Antiquity（EuroSys '07）使用安全日志结构来保证数据完整性，将每条日志复制到多台服务器来提供数据持久性，使用拜占庭容错协议来保证数据一致性，使用quorum修复协议来替代丢失的复本。在有超过quorum (threshold)数目的复本可用时允许用户执行写操作。
OceanStore 提供全局的、事务的、持久存储服务，并支持广域的复本数据串行化更新。采用冲突消除策略来降低事务被丢弃的数目。OceanStore基于Tapestry后缀路由算法设计，同时支持纠删码和完整复本两种冗余策略，不同于CFS和PAST。文件碎片及其复本能够自由的存储在任意节点上。为此OceanStore在文件ID对应的根节点处维护碎片位置信息，此外根节点负责通过心跳检测碎片所在的节点状态，当出现节点错误的时候，数据的多个根节点联合决定修复数据的策略。通过数据多版本化来支持数据更新，即数据的每次更新都不会覆盖原有数据，而是产生数据的一个新版本，从而绕开复杂的数据一致性维护问题。
GoogleFS
系统由价格低廉的服务器构成，分步式文件系统，由一台主服务器管理所有元数据，数据被切分成Chunk存储在Chunk服务器。设计用于应对大量的读操作，而基本不改写数据。
======================================
节点的成员管理和失效恢复，Gossip
连接、节点的异构性
问题分类：
CAP问题
广域网P2P存储
数据中心p2p存储:Dynamo
安全性
弱一致性存储系统
Weakly Consistent Storage Systems (i.e. Eventual Consistency)
Replication and Fault Tolerance
Scalability and Fault Tolerance
Wide-area file systems
Eventual Consistency：最终一致性
分布的，多复本，以及支持并发访问都是挑战一致性的因素，性能，可用性，架构选择与一致性之间的权衡。
reading notes for <<Above the Clouds: A Berkeley View of Cloud Computing>>
不知道在那里存这些技术笔记，索性先放在这里。将来再找更合适的地方。
今天读了《云之上》，还是有不少启发。看到Berkeley 和David Patterson的名头就进去了。顺便提一下，Randy的那本讲体系结构的书一直没有找到时间看，看到Patterson，又想了起来。
主要的东西原来也陆陆续续看到了一下，所以启发还是来自于细节。
1) 首先看到的一个规模经济的比较，可以看出来大的DC比小的DC还是有显著的优势（7X)，可以预见，如果云计算普及，势必会是相当集中的行业，而现在
大型DC具有不可忽视的先发优势，这恐怕也是大公司拼命忽悠的主要原因。
Table 2: Economies of scale in 2006 for medium-sized datacenter (~=1000 servers) vs. very large datacenter (~=50,000
servers). [24]
|Technology | Cost in Medium-sized DC | Cost in Very Large DC |Ratio |
|Network | $95 per Mbit/sec/month | $13 per Mbit/sec/month |7.1 |
|Storage | $2.20 per GByte / month | $0.40 per GByte / month |5.7 |
|Administration | ~=140 Servers/Administrator | >1000 Servers/Administrator | 7.1 |
2）电力价格差距还是很大的，这样对于中国西部倒是一个机会，不知道电力占成本的比例。粗略的算一下，一台普通台式机，负载100%，一天大致3度电，一度电大约0.45元（上海峰谷平均），这样一年1000元，好像跟我们公司大体一致。这样，大致与一台计算机的一年折旧费用大体相当。这样，电费是运营成本中不可忽视的因素。
Table 3: Price of kilowatt-hours of electricity by region [7].
|Price per KWH | Where | Possible Reasons Why |
|3.6¢ | Idaho | Hydroelectric power; not sent long distance |
|10.0¢ | California | Electricity transmitted long distance over the grid;limited transmission lines in Bay Area; no coal
fired electricity allowed in California. |
|18.0¢ | Hawaii | Must ship fuel to generate electricity |
3） 毫无疑问，最为稀缺的资源是带宽。这跟我们平常计算一致。就我这次对我们cluster的性能简单评估的经验来看，瓶颈也是网络速度。可是这也是云计算所不能解决的问题。当然，如果数据也产生于云里，这个问题倒还好办。所以，云计算首先也解决的是云存储，一旦数据进了云里，很多问题就好说了。同时意味着数据的迁移成本也是巨大的。换句话说，还是巨大的先发优势。
Table 5: We update Gray’s costs of computing resources from 2003 to 2008, normalize to what $1 could buy in 2003
vs. 2008, and compare to the cost of paying per use of $1 worth of resources on AWS at 2008 prices.
| | WAN bandwidth/mo. | CPU hours (all cores) | disk storage |
| Item in 2003 | 1 Mbps WAN link | 2 GHz CPU, 2 GB DRAM | 200 GB disk, 50 Mb/s
transfer rate |
| Cost in 2003 | $100/mo. | $2000 | $200 |
| $1 buys in 2003 | 1 GB | 8 CPU hours | 1 GB |
| Item in 2008 | 100 Mbps WAN link | 2 GHz, 2 sockets, 4
cores/socket, 4 GB DRAM |
1 TB disk, 115 MB/s sustained
transfer |
| Cost in 2008 | $3600/mo. | $1000 | $100 |
| $1 buys in 2008 | 2.7 GB | 128 CPU hours | 10 GB |
| cost/performance improvement | 2.7x | 16x |10x
| Cost to rent | $1 | $0.27–$0.40 | $2.56 | $1.20–$1.50 |
4）值得注意的是，Amazon EC2并没有停运过，我想这会不会意味着EC2用户相比S3还是少？ 大多数付费用户还是用云存储？ EC2用的认证服务与S3不同？ 相比较公司内部IT的故障，这个故障时间还是可以忍受的。
Table 7: Outages in AWS, AppEngine, and Gmail
Service and Outage Duration Date
S3 outage: authentication service overload leading to unavailability [39] 2 hours 2/15/08
S3 outage: Single bit error leading to gossip protocol blowup. [41] 6-8 hours 7/20/08
AppEngine partial outage: programming error [43] 5 hours 6/17/08
Gmail: site unavailable due to outage in contacts system [29] 1.5 hours 8/11/08
5）文中还讨论个老问题，皮鞋传输和网络传输的比较。就是用快递，可以达到1500 Mbit/sec的速度，而用网络，却是20 Mbit/sec。因此如果发展云计算，估计数据中心可以养活一大批快递。
BTW, how to create a table here?
Reference links:
http://www.hpcwire.com/features/Berkeley-Releases-Cloud-Computing-Study-39502692.html?page=1
http://www.amazon.com/Computer-Systems-Programmers-Randal-Bryant/dp/013034074X/ref=sr_1_1?ie=UTF8&s=books&qid=1235294059&sr=1-1
没有评论:
发表评论