声明:本文都是从AWS以及其他网上获取的知识整理笔记,不敢臆测Amazon内部的机制= =

Amazon位于N.Virginia的云计算数据中心于太平洋时间4月21日凌晨1点左右宕机,Service Health dashboard上写的是系统的连通性、延迟以及错误率等较高。其宕机影响了包括Quora、Foursquare、Reddit等众多的Web2.0明星应用,报道详情猛击这里,此外这篇评论也很有阅读价值(可能要翻墙,话说现在什么乱七八糟的网站都开始被墙了)。

报道中提到了Amazon没有解释为什么自己没有绕开出问题的AZ将服务转移,特意去关注了下AWS提供的服务在Failure Tolerance方面提供的一些特性。

Regions & Availablity Zones

Amazon EC2由Regions和Availablity Zones组成,按照其文档上的说明,Region由Availability Zones组成并分布在不同的地域甚至国家,AZs是Regions内部的可用区域,不同的AZ之间以工程设计的方式隔开以保证一个AZ的失效不会影响到其他AZ,同一个Region内部的不同AZ之间提供了inexpensive和low latency的通信。将自己的instance运行在多个独立的AZs中能避免自己的应用程序单点失效。Amazon目前有5个Region,分别位于N.Virginia、N.California、Ireland、Singapore以及Tokyo。

EC2的SLA协议中提到每个Region的可用性达到99.95%,EC2通过备份instance的快速启用以及预测启用提供高可靠的运行环境,These “availability zones” are supposed to ensure redundancy, but failed in this case。

Amazon Simple Storage(S3)

按照官方的说明,S3提供了高达99.999999999%的可用性,设计上可以容忍分布两个设备上数据同时丢失或者不可访问。同时利用数据版本策略对数据提供进一步的保护,用户可以保留、恢复不同的数据版本,读取中通过指定版本号可以读取较旧的数据进行恢复。此外,S3还提供了一种Reduced Redundancy Storage(RRS)的策略,RRS也会存储数据的多个副本,但副本个数会少于标准的S3服务,RRS主要用于一些敏感性不高、可再生的数据,提供的可用性为99.99%,话说这差距对一般个人使用估计也没啥吧,相对就便宜一点,支持单个设备上的数据丢失的情况。Amazon S3号称提供了一个高可靠、可扩展的安全策略用于数据的备份和隐私的归档,利用Amazon Import/Export进行大数据的导入导出,以使得从灾难中快速恢复。看了半天也就是S3说自己会对数据冗余复制在多个Facilites中,按照理解这个Facilities应该是不同的AZ。

Elastic Storage Block(EBS)

Amazon EBS是一个用于持久保存运行在instance上数据的存储块,可以创建类似未格式化的文件卷Volumn,并attach到位于同一Availability Zone的instance上,EBS本身的冗余复制到各个EBS Server都是位于同一个AZ内部的,因此并不能明显的提高可靠性。但EBS Volumn提供快照功能,可以创建数据的snapshot并存放在S3中,而S3的冗余备份会跨越多个AZ。

Elastic Load Balancing

按照AWS文档的描述,可以部署多个EC2 instance,将instances放置到Elastic Load Balancer后面,由Balancer自动的根据instance以及AZ的traffic info将请求转发到健康的instance来提高应用程序的Failure Tolerance。Elastic Load Balancer背后的多个EC2 instance既可以部署在同一个AZ中也可以跨越AZ部署,跨越AZ的instance会提供更好的可靠性。

Auto Scaling

Auto Scaling可以使得应用程序根据发展的需要动态的增加以及减少instance,因此也可以使用Auto Scaling来提高应用程序的可靠性,例如在Auto Scaling中设置条件,保证系统中健康的instance个数不会低于两个或者应用程序中任何一个EC2 instance的latency在一段时间内不能超过5秒。一旦这些条件被触发,系统就会自动的增加instance的个数从而提高服务的可用性。

从上面的一些Failure Tolerance的策略中可以看出,AWS一般提供跨Availability Zone的可靠性,数据会在AZ之间冗余,如果一个AZ中的服务不可用,会转移到另外一个AZ上继续提供服务,而N.Virginia的Region包含4个Availability Zone,这也是国外媒体质疑的地方,莫非Dashboard上写的connectivity影响到了整个Region。

AWS的EC2以及提供的EBS、Load balancing、Auto Scaling等特性确实很棒,特别适合start-up的公司,不需要投入大量资金和人力到硬件部署和升级上,报道硅谷最近的公司员工入职都是直接一台机器,上AWS编程,RoR应用很多,开发效率各种高,不过光看这次宕机影响的网站也就知道硅谷目前对于AWS的依赖程度了。不知道国内啥时候能开始接触和适应这种模式,阿里云到现在也没见到个影子啊。

之前看过一篇报道,当我们都在关注Google的技术、Apple的创造力、Facebook的影响速度时,是不是忽略了Amazon,甚至沃尔玛这样的公司对IT的影响力。

—————————————————————————————————————————–

Amazon在修复了事故之后给出了详细的报道,详情http://aws.amazon.com/message/65648/,看E文的就不用往下看了。

EBS由两个组件构成,EBS Clusters用来存储用户的数据,每一个Cluster运行在一个单独的AZ中,由多个Nodes 组成,每个Node有一个对应的备份node,当主节点感知备份node失效后,会向Cluster重新请求一个可用的Server做备份节点,进行re-mirroing过程,过程中数据访问被block;EBS Control panel则将用户请求发送到合适的EBS Cluster中,Control panel services分布在各个Region的各个AZ中。

同时EBS Cluster中的nodes通过两条网络链接。primary network具备较高的带宽,提供节点间的正常通信服务。而secondary network带宽较低,主要用于备份通信以及数据复制过程中额外的带宽,未被设计用于正常的网络服务。

N.Virginia的宕机是由于在升级过程中,网络切换错误导致产生的,本来应将primary network切换至另外一个router的primary network,结果切换到了一个secondary network上。由于secondary network低带宽无法承载系统的服务,造成了对应AZ的大量node无法连接到自己的back-up,认为back-up失效后请求cluster重新寻求备份,从而产生了re-mirroing strom。

re-mirroing storm耗尽对应的Cluster的可用空间,使得通过EBS Control panel的API进行volumn create的操作无法进行,而API的延迟设置相对较高,进而耗尽了EBS Control panel的thread pool,使得其他的API请求也无法进行,影响了其他AZ的服务。

,

前几天去吃葫芦头的路上,大飞哥给详细的讲解了他在比较文本相似度实验时对Google的simhash方法高效的惊叹,回来特意去找了原文去拜读。

Simhash

传统IR领域内文本相似度比较所采用的经典方法是文本相似度的向量夹角余弦,其主要思想是根据一个文章中出现词的词频构成一个向量,然后计算两篇文章对应向量的向量夹角。但由于有可能一个文章的特征向量词特别多导致整个向量维度很高,使得计算的代价太大,对于Google这种处理万亿级别的网页的搜索引擎而言是不可接受的,simhash算法的主要思想是降维,将高维的特征向量映射成一个f-bit的指纹(fingerprint),通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。

simhash算法很精巧,但却十分容易理解和实现,具体的simhash过程如下:

1. 首先基于传统的IR方法,将文章转换为一组加权的特征值构成的向量。

2.初始化一个f维的向量V,其中每一个元素初始值为0。

3.对于文章的特征向量集中的每一个特征,做如下计算:

利用传统的hash算法映射到一个f-bit的签名。对于这个f- bit的签名,如果签名的第i位上为1,则对向量V中第i维加上这个特征的权值,否则对向量的第i维减去该特征的权值。

4.对整个特征向量集合迭代上述运算后,根据V中每一维向量的符号来确定生成的f-bit指纹的值,如果V的第i维为正数,则生成f-bit指纹的第i维为1,否则为0。

simhash

simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复,但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果,而simhash对相似的文本的哈希映射结果也相似。Google的论文中取了f=64,即将整个网页的加权特征集合映射到一个64-bit的fingerprint上。

比起simhash,整片文章中Google所采用的查找与给定f-bit的fingerprint的海明距离(Hamming Distance)小于k的算法相对还稍微难理解点。

fingerprint的Hamming Distance

问题:一个80亿的64-bit指纹组成的集合Q,对于一个给定64-bit的指纹F,如何在a few millionseconds中找到Q中和f至多只有k(k=3)位差别的指纹。

思想:1. 对于一个具有2^d个记录的集合,只需要考虑d-bit hash。2. 选取一个d’使得|d’-d|十分小,因此如果两fingerprint在d’-bits上都相同,那么在d-bits也很可能相同。然后在这些d-bit match的结果中寻找整个f-bit的Hamming Distance小于k的fingerprint。 简单的说,就是利用fingerprint少量特征位数比较从而首先缩小范围,然后再去确定是否差异小于k个bit。

算法:

1. 首先对于集合Q构建多个表T1,T2…Tt,每一个表都是采用对应的置换函数π(i)将64-bit的fingerprint中的某p(i)位序列置换换到整个序列的最前面。即每个表存储都是整个Q的fingerprint的复制置换。

2.对于给定的F,在每个Ti中进行匹配,寻找所有前pi位与F经过π(i)置换后的前pi位相同的fingerprint。

3.对于所有在上一步中匹配到的置换后的fingerprint,计算其是否与π(i)(F)至多有k-bit不同。

算法的重点在于对于集合Q的分表以及每个表所对应的置换函数,假设对于64-bit的fingerprint,k=3,存储16个table,划分参考下图:

HammingTable

将64-bit按照16位划分为4个区间,每个区间剩余的48-bit再按照每个12-bit划分为4个区间,因此总共16个table并行查找,即使三个不同的k-bit落在A、B、C、D中三个不同的区块,此划分方法也不会导致遗漏。

以上方法是对于online的query,即一个给定的F在集合中查找相似的fingerprint。如果爬虫每天爬取了100w个网页,快速的查找这些新抓取的网页是否在原集合中有Near-duplication,对于这种batch-query的情况,Map-Reduce就发挥它的威力了。

batch-query

不同的是,在batch-query的处理中,是对待查集合B(1M个fingerprint)进行复制置换构建Table而非8B的目标集合,而在每一个chunkserver上对Fi(F为整个8B的fingerprint)在整个Table(B)中进行探测,每一个chunkserver上的的该Map过程输出该Fi中与整个B的near-duplicates,Reduces过程则将所有的结果收集、去重、然后输出为一个sorted file。

Haffman编码压缩

上述的查询过程,特别是针对online-version的算法,可以看出需要对8B的fingerprint进行多表复制和构建,其占据的容量是非常大的,不过由于构建的每一个置换Table都是sorted的,因此可以利用每一个fingerprint与其前一个的开始不同的bit-position h(h∈[0,f-1]) 来进行数据压缩,即如果前一个编码是11011011,而自身是11011001,则后一个可以编码为(6)1,即h=6,其中6表示从第6位(从0开始编号)开始和上一个fingerprint不相同(上一个为1,这个必然为0),然后再保存不相同位置右侧的编码,依次生成整个table。

Google首先计算整个排序的fingerprint表中h的分布情况,即不同的h出现次数,依据此对[0,f-1]上出现的h建立Haffman code,再根据上述规则生成table(例如上面的6就表示成对应的Haffman code)。其中table分为多个block,每一个block中的第一个fingerprint保存原数据,后面的依次按照编码生成。

将每一个block中所对应的最后一个fingerprint保存在内存中,因此在比对的时候就可以直接根据内存中的fingerprint来确定是哪一个block需要被decompress进行比较。

8B个64-bit的fingerprint原占据空间大约为64GB,利用上述Haffman code压缩后几乎会减少一般,而内存中又只对每一个block保存了一个fingerprint。

 

每次看Google的论文都会让人眼前一亮,而且与很多(特别是国内)的论文是对未来进行设想不同,Google的东西都是已经运行了2,3年了再到WWW,OSDI这种顶级会议上灌个水。再次各种羡慕能去这个Dream Company工作的人,你们懂得。

参考:

Detecting Near-Duplicates for Web Crawling(Paper)

Detecting Near-Duplicates for Web Crawling(PPT)

, ,

当前NoSQL的分布式存储系统的资料(包括Paper以及各大Blog上的内容),大部分都是关于分布式Key-Value存储下的读写操作、数据一致性、节点失效与修复等问题上,很少有系统的提及有关Load Balance的处理。不过既NoSQL指导型原则是CAP原理,而系统在实现时无论偏重AP还是CP,P都是必选的,因此对于分布式的各个节点的负载均衡也应该是要面对的问题,不过很遗憾,在BigTable, Dynamo以及Cassandra的Paper中对于Load Balance基本都没有提及,都只是很简单的进行了说明。特地花了几天去找了一些资料,总结记录于此。

1. Dynamo

Dynamo的论文上对于Load Balance的提及基本就是一个关键词”uniform hashing”,”A uniform key distribution can help us achieve uniform load distribution assuming the access distribution of keys is not highly skew“。即通过均匀的hash函数,保证将所有的key以及node都可以均匀的分布到同一哈希地址空间上,从而实现负载的均衡,此类常用的函数包括MD5 hash函数和SHA-1 hash函数。

除了利用哈希函数使得整个存储的item被均匀的分配到整个地址空间上,此外Dynamo的Virtual Node机制也对负载均衡进行一定的帮助,根据机器的性能指标不同划分不同的VNode即可。

此外,当新的VNode启动以及离开时,需要将某个VNode的数据迁移至邻居节点,而此种迁移有时会带来比较大的计算量(Merkle Tree等),因此Dynamo又采用了一个将整个地址空间划分成段的策略(如下图所示),然后每个VNode只能在一个段边界位置进行添加,即每一个VNode管理段长的整数倍的地址空间,此种方式对于节点的启动以及恢复,数据的归档等都有好处。

由于Dynamo虽然是NoSQL数据库的雏形以及类white paper,但由于工业界基于此模型构建实际针对业务数据库并是特别认可,因此资料也较少。

2.  Cassandra

Cassandra首先包含了两种Partitioner,这两种Partitioner对负载均衡的影响完全不同。

RandomPartitioner: RandomPartitioner采用均匀的hash函数,将负载均匀的划分到Key space空间上。RandomPartitioner gives you pretty good load balancing with no further work required。不过由于hash函数会将连续的Key映射到不同的环上地址,缺点就是无法进行range query.
OrderPreservingPartitioner:OrderPreservingPartitioner会使得连续的key映射到环上的地址空间后也是连续的,因此支持range query. OrderPreservingPartitioner let u perform range queries on the keys, but requires choosing node tokens carefully and active load balancing.

也就是说RandomPartitioner几乎是不需要进行Load Balancing的,但对于后者,就需要在Load Balancing上下一点功夫。

阅读全文…

, , , ,