持续可用与CAP理论 – 一个系统开发者的观点

持续可用

本文主要针对金融数据库,认为金融数据库的持续可用包含两点:一个是强一致性;另外一个是高可用性。

数据库系统必须是强一致性的系统,这是因为数据库系统有事务ACID的基本要求,而弱一致系统无法做到。业内也有一些流行的NOSQL系统,例如各种类Dynamo系统,如开源的Cassandra,对同一个最小数据单位(同一行数据)允许多台服务器同时写入,虽然采用NWR机制处理冲突,但是由于不可能解决多台服务器之间的时序问题,而只能支持弱一致语义。弱一致语义的问题很多,例如无法支持复杂功能,无法构建严谨的测试体系,无法应用到核心场景。虽然弱一致性系统也有一定的应用场景,但本文认为其不符合核心业务持续可用的要求,不予讨论。

高可用性可以有很多种解释,实践中最常见的解释为:在一台服务器,一个交换机,一个机房,或者一个地区整体故障后,系统能够在多长时间内恢复服务。当然,这里的恢复服务是以保证强一致性作为前提条件的。如果能够在秒级(10秒左右)恢复服务,本文认为这个系统是高可用的,绝大部分应用系统都能够容忍硬件故障导致的秒级不可用。

CAP理论

CAP理论网上传了很多版本,大致的意思是:一致性,可用性和分区可容忍性三者只能取其二,不可兼得。由于分区可容忍性是不可选择的,因此,系统设计时只能在一致性和可用性之间权衡。这就带来了一个很悲观的结论:持续可用无法实现。然而,事实是这样吗?

首先,我们回到CAP理论的原始定义:

  • C(Consistency):A read is guaranteed to return the most recent write for a given client
  • A(Availability):A non-failing node will return a reasonable response within a reasonable amount of time (no error or timeout)
  • P(Partition Tolerance):The system will continue to function when network partitions occur.

CAP理论的证明也比较直观,如下:

左图中,假设有两个节点N1和N2,N1和N2之间发生了网络分区(P),N1写入新值y,N2一直是老值x,为了保证一致性(C),读取N2总是返回失败,违反了可用性(A)要求:任何一个没有发生故障的节点必须在有限时间内返回结果,不允许为Error或者Timeout,系统只能保证CP。

右图中,从另外一个角度看,假设总是要保证可用性(A),那么,读到N2中的老值x,由于x和最新写入的y不同,违反了一致性(C)的要求,系统只能保证AP。

CAP理论本身毋庸置疑,证明可以参考Gilbert和Lynch合著的论文

CAP中的A与高可用的HA

请读者会到CAP理论中关于A的定义:CAP中的A要求任何一个没有发生故障的节点必须在有限的时间内返回结果。然而,如果系统能够做到当某个节点发生网络分区后,将它从系统中剔除,由其它节点继续提供服务。虽然没有满足CAP中A的要求,但是,只要恢复时间足够快,也符合高可用的要求。而高可用才是系统设计的本质需求,CAP中的A只是个理论上的需求。

CAP理论的作者Eric Brewer后来确实也写过一篇文章来说明这个问题:<<CAP twelve years later>>:当发生网络分区时,系统可以进入分区模式,将网络不通的节点从系统中剔除后分区恢复,系统继续运行。

Paxos与持续可用
Paxos是图灵奖获得者Lamport的经典之作,第一个版本的论文叫做:<<The Part-time Parliament>>。Lamport奠定了很多分布式系统的理论基础,比如:<<Time, Clocks and the Ordering of Events in a Distributed System>>。据传(八卦,不确信)Lamport通过讲故事的方法讲”拜占庭将军”问题,尝到了甜头,于是在最初的Paxos论文中也讲了一个考古的故事,不过论文提交上去没人能看懂,后来不知道从哪个犄角旮旯里面被人翻了出来。Lamport后来也意识到讲的故事太难懂,于是又整理了第二个版本叫做:<<Paxos Made Simple>>。这个版本的初始协议很容易理解,不过如果想深入理解,例如协议中最难理解的Multi-Paxos,难度相比第一个版本一点都没有降低。与Lamport同时期还有一篇类似的论文,叫做<<Viewstamped Replication>>,最近还有一篇<<Raft>>。建议理解Paxos遇到困难的看后面这两篇论文,尤其是Raft,在牺牲很少可用性的情况下,对Paxos做了极大的简化,称得上业界良心。

八卦完了Paxos,下面进入正题。Lamport和Jim Gray分别是分布式系统和数据库领域的代表任务,同属微软研究院,不过也是共事多年才坐在一起聊两个领域的问题。高可用是分布式系统的长项,为了实现高可用,首先必须至少写三份数据(一主两备)。这是因为,如果只写两份数据,当一份数据出现故障的时候,另外一份数据永远无法证明自己是对,也无法证明自己是错。这就是选举的价值,类Paxos选举协议允许在超过半数(Majority)节点正常的情况下提供服务。因此,当某台服务器,某个交换机,某个IDC甚至某个地区整体故障的时候,只要不超过整个系统的半数,系统都能够很快从错误中恢复过来,而且完全自动,无需人工干预。

强一致性是数据库的长项,做法就是强同步,Oracle,MySQL 5.7,国内的MySQL定制版本,例如阿里、网易的MySQL版本都支持强一致性。强同步的问题在于性能损耗,例如传统数据库的执行模型(非线程池模型)一般为一个连接对应一个工作线程/进程,采用强同步模式后事务的延时必然延长,从而导致工作线程/进程数增多,高并发情况下日志线程唤醒工作线程导致的上下文切换开销也非常大。另外,为了实现高可用,必须同步至少两个备库,使得情况进一步恶化。

采用Paxos协议的持续可用系统有两种常见的部署方式:

第一种部署方式比较简单,也最为常见。有一个全局Paxos服务,例如Zookeeper,它和其它机器之间保持租约。Master和两个Slave之间保持强同步,事务至少要写入到Master和其中一个Slave才可以返回成功。同一时刻对于同一份数据只有一个Master,全局Paxos服务负责选举,当Master出现故障时,选举日志号最大的Slave接替原来的Master继续提供服务。

第二种部署方式比较纯粹,只出现在少量的分布式数据库中,例如Google Spanner,OceanBase 1.0。Leader(相当于Master)和Follower(相当于Slave)之间直接采用Paxos协议进行数据同步和选举,相比第一种方案,这种方式实现复杂度要高很多,换来的好处是宕机恢复时间更短,系统更优雅。

共享存储与硬件解决方案

数据库领域经常采用共享存储来解决强一致性问题,主库将redo日志持久化到共享存储,如果主库故障,假设共享存储是持续可用的,备库可以从共享存储中读取日志恢复系统。共享存储与share-nothing架构的强同步有何区别呢?共享存储模式下只需要部署一个主库和一个备库,而share-nothing架构下强同步至少需要一个主库加两个备库。为什么呢?假设share-nothing架构只部署了一个主库和一个备库,只要任何一台机器,即使是备库宕机,为了保证强一致性,整个系统都无法提供服务。显然,这样的系统在互联网业务中几乎没有应用场景。

共享存储本质上是硬件解决方案,相比Paxos解决方案,优势是简单成熟,在商用数据库中广泛使用。问题在于成本高,且依赖硬件本身高可靠和高性能,也无法跨IDC部署,只能容忍单台服务器故障,无法容忍单个IDC故障。

强同步性能

数据库的性能分为两个方面:

  • 单个事务的延时:由于多了一次同步操作,单个事务提交的延时加长了。设计系统时能够做的事情是将同步两个备库和主库写磁盘这三个操作完全并行起来,使得增加的额外延时只是三个操作的最大值,而不是三个操作之和。
  • 系统的吞吐量:本质上看,强同步是否影响吞吐量取决于主备之间的网络带宽是否成为瓶颈。在采用万兆网卡或者两块千兆网卡的情况下,吞吐量基本没有影响。

理想的系统应该是一个全异步的系统,避免强同步占用线程/进程等执行资源,且不应该带来额外的上下文切换。日志同步的优化有一些关键点,例如:组提交(Group Commit),减少日志缓冲区的锁冲突,异步化,避免不必要的上下文切换,数据库提前解行锁避免热点。具体可以参考论文:<<Aether:A Scalable Approach to Logging>>。我参与实现的OceanBase系统强同步对单个事务带来的额外延时只是一次网络同步,同一个机房内在0.5ms左右,同城的多个机房之间只有1ms左右,对系统吞吐量的影响也只有5% ~ 10%左右。也就是说,如果实现做到极致,强同步的性能不会是问题。当然,这就要求将持续可用看成数据库架构的核心目标,针对这个需求重构数据库的执行引擎。

与性能相关联的一个问题是成本。前面已经提到,基于Paxos的持续可用方案至少需要一主两备,如果数据总是有三份,确实比较浪费。一个做到极致的系统应该能够只需要两个副本,第三个副本只存储redo日志即可。

引入选举的难点

假设在关系数据库的基础上引入全局Paxos服务,是否能够解决高可用问题呢?理论上确实是可以的,不过实施起来难度也不小。这是因为,即使是Zookeeper这样成熟的选举服务,使用过程中总是会遇到各种各样的问题,如果期望应用到核心业务,需要对Zookeeper系统完全的掌控力。也就是说,假设Zookeeper这样的服务出现问题,需要能够Fix Bug,而不是简单重启解决。另外,也需要做一套模拟各种异常的测试系统,确保不会在异常的情况下出现一些严重的问题,例如Zookeeper选出双主导致数据不一致。总而言之,做一个持续可用的选举服务并不是简单地使用开源软件,这是一个全局服务,要么不做,要么就深入下去做到完全掌控。

跨机房问题

跨机房问题分为两类:同城以及异地。前面已经提到,无论如何实现,强同步方案中单个事务至少增加一次网络同步延时。对于同城场景,如果网络环境比较好,例如公司的数据库服务有专用的光纤或者带宽比较高,那么,增加的延时在1~2ms(光折射传播的时间 + 交换机处理时间),业务是完全可以接受的。因此,可以做到同城持续可用,单个IDC故障时,能够在保证强一致的前提下很快恢复服务。

对于异地场景,由于网络延时较大,例如100ms左右,业务往往不可接受。因此,无法做到跨地域持续可用,整个地区故障时,要么牺牲一致性,要么牺牲可用性,如果选择可用性时可能会丢失最后几秒内的数据。当然,实际上业务上往往会组合使用各种柔性解决方案,例如涉及到钱的业务停服务,其它业务容忍极端情况下的数据丢失;或者在外部系统中记录一些信息,例如记录哪些用户的数据不一致,出现问题是禁止这些用户的写服务,其它用户正常提供服务;或者DBA采用各种办法补数据,等等。

小结

总而言之,在金融数据库中,由于强一致性是必选项,因此,要做到持续可用比较困难,但也并不是不可能,CAP和持续可用并不矛盾。成熟的商业数据库都是基于共享存储的,不过基于Paxos的持续可用方案开始越来越多地应用到核心场景,例如Google Spanner,Microsoft SQL Server云版本,Amazon DynamoDB,而Aliababa OceanBase也在金融核心场景得到了验证。同时,笔者认为,采用Paxos协议,虽然工程难度很高,但是,只要在实现上做到极致,在同城的情况下,可以容忍单个IDC故障,且性能损耗非常小;而在异地的场景,考虑到光速不可突破,往往由业务在一致性和可用性之间权衡。越来越多的云数据库将会采用Paxos来实现持续可用。

AWS云平台系列介绍(一):AWS平台与EC2介绍

AWS整体介绍

Amazon平台的产品分为几个部分:

  • 计算类:包含弹性计算云(EC2)和弹性MapReduce(Elastic MapReduce)这两个产品。EC2几乎可以认为是迄今为止云计算领域最为成功的产品,通俗地将,就是提供虚拟机。EC2的创新在于允许用户根据需求动态改变虚拟机实例的类型及数量,技术上支持容错并在收费模式上支持按使用量付费,而不是预付费。弹性MapReduce将Hadoop MapReduce搬到云环境中,大量EC2实例动态地成为执行大规模MapReduce计算任务的工作机。
  • 存储类:存储类产品较多,包括弹性块存储EBS,简单消息存储SQS,Blob对象存储S3,表格存储系统Simpledb和DynamoDB以及分布式数据库系统RDS。其中,EBS相当于一个分布式块设备,可以直接挂载在EC2实例上,用于替代EC2实例本地存储,从而增强EC2可靠性。另外,S3中的Blob对象能够通过CloudFront缓存到不同地理位置的CDN节点,从而提高访问性能。Simpledb和DynamoDB是分布式表格系统,支持单表的简单操作;RDS是分布式数据库,目前支持Mysql以及Oracle两种数据库。SQS主要用于支持多个任务之间的消息传递,解除任务之间的耦合。
  • 工具支持:AWS支持多种开发语言,提供Java、Rupy、Python、PHP、Windows &.NET 以及Android和iOS的工具集。工具集中包含各种语言的SDK,程序自动部署以及各种管理工具。另外,AWS通过CloudWatch系统提供丰富的监控功能。

AWS平台引入了区域(Zone)的概念。它将区域分为两种:地理区域(Region Zone)和可用区域(Availability Zone),其中地理区域是按照实际的地理位置划分的,而可用区域一般是按照数据中心划分的。

如上图,假设用户的网站MyWebSite.com托管在AWS平台的某个可用区域中。用户将Web应用上传到EC2实例中,EC2一般分成多个自动扩展(Auto Scaling)组,并通过弹性负载均衡(Elastic Load Balancing)组件进行负载均衡。用户的Web应用可以访问AWS平台上的存储类服务,包括EBS,S3,Simpledb,DynamoDB,RDS以及SQS。网站上的Blob数据,如视频,图片将通过DNS定位到Amazon CloudFront。CloudFront首先在本地缓存节点查找Blob对象,如果不存在,将请求源站获取S3中存储的Blob对象,这一步操作称为回源。AWS CloudWatch对AWS平台上运行的所有服务及应用程序进行监控。

Amazon EC2

相比传统的虚拟机托管,EC2的最大特点是允许用户根据需求动态调整运行的实例类型和数量,实现按需付费。为了支持这种灵活性,EC2需要在技术上支持容错以及更好的安全性。

架构

Amazon EC2平台主要包含如下部分:

  • EC2实例

AMI(Amazon Machine Image)是Amazon虚拟机镜像文件,它是一个可以将用户的应用程序、配置等一起打包的加密机器镜像。用户创建好AMI后,部署在EC2平台上运行,称为一个EC2实例。每个实例自身包含一个本地存储模块(Instance Local Store),临时存放用户数据。如果EC2实例运行过程中出现故障或者实例被终止,存储在其中的数据将会丢失。因此,Amazon建议将重要的数据保存在EBS中以增强可靠性。

  • 弹性块存储

弹性块存储(EBS)映射为EC2实例上的块设备,与EC2配合使用。EBS允许用户创建卷(Volume),每个卷可以作为一个设备挂载到EC2实例上。数据在EBS中存储多份,从而保证高可靠性。另外,EBS提供了增量快照功能,可以将当前卷的状态快照增量备份到S3中。假设EBS卷有100G数据,其中只有5GB的数据从上次快照操作以后产生了变化,那么,仅仅需要将这5GB变化的数据备份到S3。

  • 弹性负载均衡

弹性负载均衡自动地将流量分发给多个EC2实例,并且在一定程度上支持容错。弹性负载均衡功能可以识别出应用实例的状态,当某个实例出现故障时,它会自动将流量路由到健康的实例上。

EC2存储

EC2本地存储是实例自带的磁盘空间,但它并不是持久的,也就是说这个实例所在的节点出现故障时,相应的磁盘空间也会随之清空,本地存储上的数据随时有丢失的风险。

为了解决本地存储不可靠问题,EC2推出了EBS,数据在EBS中自动在同一个可用区域内复制多份。EBS通过卷来组织数据,每个EBS卷只能挂载到一个EC2实例。EBS卷并不与实例绑定,而是与用户帐号绑定。当EC2实例发生故障时,用户可以在新启动的EC2实例上重新挂载EBS卷。另外,EBS能够以快照的形式将数据增量备份到S3,而S3的数据分布在多个可用区域,进一步增强了可靠性。EBS的设计原理如下:

如上图,EBS包含两个部分:EBS控制层(EBS control plane)及EBS存储节点。EBS客户端通过EBS control plane创建逻辑卷,获取逻辑卷每个副本所在的EBS存储节点位置,然后请求EBS存储节点读写逻辑卷数据。每个逻辑卷存储在多个EBS节点上,多个副本之间数据强同步,其中有一个副本为Primary,其它的为Secondary。当Primary往Secondary传输数据失败时,将请求EBS control plane选取新的EBS节点增加副本,这个过程称为重新镜像(re-mirroring)。EBS control plane负责每个逻辑卷的Primary副本选取,如果Primary出现故障,将选择某个Secondary副本为新的Primary。EC2实例通过EBS客户端访问EBS系统,它们之间遵守一定的协议,比如网络块设备(Network Block Device,NBD)协议,从而EC2实例访问远程EBS节点上的逻辑卷与访问本地的块设备没有差别。

自动缩放

自动缩放(Auto Scaling)可以根据用户自定义的条件,自动调整EC2的计算能力。多个EC2实例组成一个自动缩放组(Auto Scaling Group),当组内的实例负载过高,比如CPU平均使用率超过70%时,可以定义缩放规则自动增加EC2实例;同样地,当组内的实例负载过低时,可以自动缩小EC2实例规模以降低成本。

EC2根据计算能力将实例分为多种类型,如下表:

资源

Small

Large

Extra Large

High-CPU Medium

High-CPU Extra Large

平台

32位

64位

64位

64位

64位

CPU

1ECU

4ECU

8ECU

5ECU

20ECU

内存

1.7GB

7.5GB

15GB

1.7GB

7GB

存储容量

160GB

850GB

1690GB

350GB

1690GB

EC2的一个计算单元称为一个ECU(EC2 Compute Unit),其计算能力相当于1个1.0GHz 2007 Xeon处理器。EC2平台不支持虚拟机实例在线迁移,如果用户需要调整实例类型,EC2内部实现时逻辑上分为两步:a) 终止原有的EC2实例;b) 根据一定的策略(比如负载)动态选择新的服务器节点启动新的EC2实例。自动缩放功能一般会配合弹性负载均衡功能一起使用,弹性负载均衡组件能够自动将流量转发给新实例。

网络路由

通过自动缩放技术,当EC2平台检测到某个实例出现故障时,将动态选择新的节点启动新实例,每个实例重新启动后它的公共IP地址都会发生变化。Internet用户通过域名访问EC2实例,然而,需要一段比较长的时间才能更新公共IP地址与DNS之间的映射关系。为了解决这个问题,EC2提供了两种方式:

  1. 弹性负载均衡:EC2新实例重启后通知弹性负载均衡组件,弹性负载均衡组件能够自动将流量切换到新实例。
  2. 弹性IP地址:弹性IP地址和用户账号而不是和某个特定的实例绑定,EC2用户可以将DNS域名设置为指向弹性IP地址。新实例启动时,EC2用户只需要使用管理工具将弹性IP地址与新的实例关联起来,Internet用户感觉不到任何差异。

2011年度总结

技术杂谈

10年定下近几年的技术方向:

1, 精通架构:深入理解线上,线下分布式存储&计算并能够形成完整的知识体系;

2,理解系统:理解系统,网络,IDC,虚拟化等相关知识;

3,掌握应用:通过应用证明和修正分布式知识体系;

11年做了一些事情:

1, 思考并讨论Google,Amazon,Microsoft,Yahoo,Facebook内部云存储系统的架构及实现,在云存储方向形成了初步的知识体系;

2, 读了一些系统和网络方面的博客和书籍,如褚霸同学的博客,<<Unix网络编程>>,等等;

3, 通过推广OB学习了很多应用的入门知识,主要包括数据库应用,OLAP应用,搜索广告应用;

12年准备做一些事情:

1, 整理一本云存储技术资料;

2, 深入学习并实践系统优化相关知识,重点是CPU&内存优化;

3, 理解淘宝数据库OLTP应用访问模式,深入理解OLAP应用业务知识;

云存储观点

1, 根据应用模式及实现难度,可以大致将云存储系统分为四类:Blob存储系统(淘宝TFS,Facebook Haystack),分布式KV系统(淘宝Tair,Dynamo),分布式表格系统(Bigtable,Megastore,Azure Table Storage)以及分布式数据库(SQL Azure,Amazon RDS)。

2, 云存储直接提供对外服务时机还不成熟,创业者期望的只是一个服务稳定的,花费低的虚拟主机而已。云存储服务需要与业务打包捆绑销售,比如Dropbox,腾讯开放平台。

3, 线上线下融合还比较难,几年之内的方式还是线下计算好的数据Push到线上系统,而不是线上线下完全共用。线下系统大局已定,Hadoop一统江湖,机会与挑战主要在线上系统,实时化。

4, 云存储的主要优势在于节省成本,来源于几个方面:a, 系统优化,普遍有2~3倍性能提升,对于某些特殊应用或一些特殊压缩算法,单节点优化可以有数量级的性能提升;b, 机器Buffer。为了防止异常,线上系统一般需要一半以上的机器Buffer,大量线上系统利用率<20%,通过提高存储服务能力,能够节省2~3倍成本;c, 硬件量产带来的低采购成本。总而言之,云存储带来的成本节省在5倍以上。

5, 云存储系统有两个目标:一个是高可扩展性,终极目标是线性扩展,完全自动化,宕机恢复时间极短;一个是强功能,终极目标是强一致性,关系型数据库SQL功能集。可扩展性与功能需要取舍,但支持绝大部分SQL功能集的线性可扩展云存储系统将出现并成为主流。

感悟

1, 权利与责任对等。有什么样的权利,就应该有什么样的责任。主管有带人的权利,就有考虑其他人如何成长的责任;业务方说话声音大,是因为要背业务KPI。技术驱动业务是不现实的,除非技术背负业务KPI。

2, 保持乐观。这个世界有太多的不公平,尤其是在天朝。然而,社会总是不断朝着公平这个方向发展的,在互联网这个小圈子里面还是相对公平的。做好自己能够控制的,忽略自己不能控制的,多想想你有什么,你想要什么,最重要的是,你还需要并且能够做什么?

3, 技术与业务。技术只有与业务相结合才能产生价值,从无到有做好一件事情,最重要的一点就是是否精通业务;然而对于技术产品,比如存储产品,这件事情能够做到多大,技术的深度会起重要甚至决定性作用。业务是从0做到10的能力,技术是从10做到1000的能力。

4, 坚持与执行力。一个人最重要的能力是把规划好的事情用最有效的方式执行下去,拿到结果。规划是从多条路里面选一条路,既然是选择,而且这个选择过程可能很痛苦,那么这些让人纠结的选择之间投入产出比一定是相当的。选择了就坚持下去,只要执行得好,往往都能拿到好的结果,即使选择不是最优的。

生活

1, 英孚没有达到8级的目标,只到6级就没有坚持下来了,没有明确目的的学习往往很容易被其它事情打断;

2, 2011年没有学车,2012年必须学完;

3, 上下班时间太长,健身计划有些中断,2012年目标比较现实,每周去健身房跑步一次就可以了。

GFS架构分析

Google文件系统(Google File System,GFS)是构建在廉价的服务器之上的大型分布式系统。它将服务器故障视为正常现象,通过软件的方式自动容错,在保证系统可靠性和可用性的同时,大大减少了系统的成本。

GFS是Google云存储的基石,其它存储系统,如Google Bigtable,Google Megastore,Google Percolator均直接或者间接地构建在GFS之上。另外,Google大规模批处理系统MapReduce也需要利用GFS作为海量数据的输入输出。

系统架构

GFS将整个系统的节点分为三种角色:GFS Master(总控服务器),GFS Chunkserver(数据块服务器,简称CS)以及GFS Client(客户端)。

GFS文件被划分为固定大小的数据块(Chunk),由Master在创建时分配一个64位全局唯一的Chunk句柄。CS以普通的Linux文件的形式将Chunk存储在磁盘中。为了保证可靠性,Chunk在不同的机器中复制多份,默认为三份。

Master中维护了系统的元数据,包括文件及Chunk名字空间,GFS文件到Chunk之间的映射,Chunk位置信息。它也负责整个系统的全局控制,如Chunk租约管理,垃圾回收无用Chunk,Chunk复制,等等。Master会定期与CS通过心跳的方式交换信息。

Client是GFS提供给应用程序的访问接口,它是一组专用接口,不遵守POSIX规范,以库文件的形式提供。Client访问GFS时,首先访问Master节点,获取与之进行交互的CS信息,然后直接访问这些CS,完成数据存取工作。

需要注意的是,GFS中的客户端不缓存文件数据,只缓存Master中获取的元数据,这是由GFS的应用特点决定的。GFS最主要的应用有两个:MapReduce与Bigtable。对于MapReduce,GFS客户端使用方式为顺序读写,没有缓存文件数据的必要;而Bigtable作为云表格系统,内部实现了一套缓存机制。另外,如何维护客户端缓存与实际数据之间的一致性是一个极其复杂的问题。

下面讨论GFS架构中的几个关键问题。

Lease机制

GFS数据追加以记录为单位,每个记录的大小为几十KB到几MB,如果每次记录追加都需要请求Master,那么Master显然会成为系统的性能瓶颈,因此,GFS系统中通过Lease机制将chunk写操作授权给Chunk Server。获取Lease授权的Chunk Server称为Primary Chunk Server,其它副本所在的Chunk Server称为Secondary Chunk Server。Lease授权针对单个chunk,在Lease有效期内,对该chunk的写操作都有Primary Chunk Server负责,从而减少Master的负担。一般来说,Lease的有效期比较长,比如60秒,只要没有出现异常,Primary Chunk Server可以不断向Master请求延长Lease的有效期直到整个chunk写满。

假设有Chunk A在GFS中保存了三个副本A1,A2,A3,其中,A1是Primary。如果副本A2所在Chunk Server下线后又重新上线,并且在A2下线的过程中,副本A1和A3有新的更新,那么,A2需要被Master当成垃圾回收掉。GFS通过对每个chunk维护一个版本号来解决,每次给Chunk进行Lease授权或者Primary Chunk Server重新延长Lease有效期时,Master会将Chunk的版本号加1。A2下线的过程中,副本A1和A3有新的更新,说明Primary Chunk Server向Master重新申请Lease并增加了A1和A3的版本号,等到A2重新上线后,Master能够发现A2的版本号太低,从而将A2标记为可删除的chunk,Master的垃圾回收任务会定时检查,并通知Chunk Server将A2回收掉。

一致性模型

GFS主要是为了追加(Append)而不是改写(Overwrite)而设计的。一方面是因为是改写的需求比较少,或者可以通过追加来实现,比如可以只使用GFS的追加功能构建分布式表格系统Bigtable;另一方面是因为追加的一致性模型相比改写要更加简单有效。考虑Chunk A的三个副本A1,A2,A3,有一个改写操作修改了A1,A2但没有修改A3,这样,落到副本A3的读操作可能读到不正确的数据;相应地,如果有一个追加操作往A1,A2上追加了一个记录但是追加A3失败,那么即使读操作落到副本A3也只是读到过期而不是不正确的数据。

我们只讨论追加的一致性。如果不发生异常,追加成功的记录在GFS的各个副本中是确定并且严格一致的;但是如果出现了异常,可能出现某些副本追加成功而某些副本没有成功的情况,失败的副本可能会出现一些可识别的填充(padding)记录。GFS客户端追加失败将重试,只要返回用户追加成功,说明在所有副本中都至少追加成功了一次。当然,可能出现记录在某些chunk副本中被追加了多次,即重复记录;也可能出现一些可识别的填充记录,应用层需要能够处理这些问题。

另外,由于GFS支持多个客户端并发追加,那么多个客户端之间的顺序是无法保证的,同一个客户端连续追加成功的多个记录也可能被打断,比如客户端先后追加成功记录R1和R2,由于追加R1和R2这两条记录的过程不是原子的,中途可能被其它客户端打断,那么GFS的chunk中记录的R1和R2可能不连续,中间夹杂着其它客户端追加的数据。

GFS的这种一致性模型是追求性能导致的,这也增加了应用程序开发的难度。对于MapReduce应用,由于其批处理特性,可以先将数据追加到一个临时文件,在临时文件中维护索引记录每个追加成功的记录的偏移,等到文件关闭时一次性将临时文件改名为最终文件。对于上层的Bigtable,有两种处理方式,后续将会介绍。

追加流程

追加流程是GFS系统中最为复杂的地方,而且,高效支持记录追加对于基于GFS实现Bigtable是至关重要的。追加流程大致如下:

  1. 客户端向Master请求chunk每个副本所在的Chunk Server,其中Primary Chunk Server持有修改Lease。如果没有Chunk Server持有Lease,说明该chunk最近没有写操作,Master会发起一个任务,按照一定的策略将chunk的Lease授权给其中一台chunk Server。
  2. Master返回客户端Primary和其它Chunk Server的位置信息,客户端将缓存这些信息供以后使用。如果不出现故障,客户端以后读写该chunk都不需要再次请求Master。
  3. 客户端将要追加的记录发送到每一个副本。每一个Chunk Server会在内部的LRU结构中缓存这些数据。GFS中采用数据流和控制流分离的方法,从而能够基于网络拓扑结构更好地调度数据流的传输。
  4. 当所有副本都确认收到了数据,客户端发起一个写请求控制命令给Primary。由于Primary可能收到多个客户端对同一个chunk的并发追加操作,Primary将确定这些操作的顺序并写入本地;
  5. Primary把写请求提交给所有的Secondary副本。每一个Secondary会根据Primary确定的顺序执行写操作;
  6. Secondary副本成功完成后应答Primary;
  7. Primary应答客户端,如果有副本发生错误,将出现Primary写成功但是某些Secondary不成功的情况,客户端将重试。

GFS追加流程有两个特色:流水线及分离数据流与控制流。流水线操作用来减少延时。当一个ChunkServer接收到一些数据,它就立即开始转发。由于采用全双工网络,立即发送数据并不会降低接收数据的速率。抛开网络阻塞,传输B个字节到R个副本的理想时间是B/T + RL,其中T是网络吞吐量,L是亮点之间的延时。假设采用千兆网络,L通常小于1ms,传输1MB数据到多个副本的时间小于80ms。分离数据流与控制流主要是为了优化数据传输,每一个机器都是把数据发送给网络拓扑图上”最近”的尚未收到数据的数据。举个例子,假设有三台ChunkServer S1,S2和S3,S1与S3在同一个机架上,S2在另外一个机架,客户端部署在机器S1上。如果数据先从S1转发到S2,再从S2转发到S3,需要经历两次跨机架数据传输;相对地,按照GFS中的策略,数据先发送到S1,接着从S1转发到S3,最后转发到S2,只需要一次跨机架数据传输。

分离数据流与控制流的前提是每次追加的数据都比较大,比如MapReduce批处理系统,而且这种分离增加了追加流程的复杂度。如果采用传统的Primary/backup复制方法,追加流程会在一定程度上得到简化。

  1. 同GFS追加流程;
  2. 同GFS追加流程;
  3. Client将待追加数据发送到Primary Chunk Server,Primary Chunk Server可能收到多个客户端的并发追加请求,需要确定操作顺序,并写入本地;
  4. Primary将数据通过流水线的方式转发给所有的Secondary;
  5. 每个Secondary Chunk Server收到待追加的记录数据后写本地,所有副本都在本地写成功并且收到后一个副本的应答消息时向前一个副本回应,比如上图中A需要等待B应答成功且本地写成功后才可以应答Primary。
  6. Primary应答客户端。如果客户端在超时时间之内没有收到Primary的应答,说明发生了错误,需要重试。

当然,实际的追加流程远远没有这么简单。追加的过程中可能出现Primary Lease过期而失去chunk修改操作的授权,Primary或者Secondary机器出现故障,等等。由于篇幅有限,追加流程的异常处理留作读者思考。

容错机制

Master的容错与传统的方法类似,通过操作日志加checkpoint的方式进行,并且有一台称为”Shadow Master”的实时热备。

Master上保存了三种元数据信息:

(1) 命名空间(Name Space),也就是整个文件系统的目录结构以及chunk基本信息;

(2) 文件到chunk之间的映射;

(3) Chunk副本的位置信息,每个Chunk通常有三个副本;

GFS Master的修改操作总是先记录操作日志,然后再修改内存,当Master发生故障重启时,可以通过磁盘中的操作日志恢复内存数据结构;另外,为了减少Master宕机恢复时间,Master会定期将内存中的数据以checkpoint文件的形式转储到磁盘中,从而减少回放的日志量。为了进一步提高Master的可靠性和可用性,GFS中还会执行实时热备,所有的元数据修改操作都必须保证发送到实时热备才算成功。远程的实时热备将实时接收Master发送的操作日志并在内存中回放这些元数据操作。如果Master宕机,还可以秒级切换到实时备机继续提供服务。为了保证同一时刻只有一个Master,GFS依赖Google内部的Chubby服务进行选主操作。

Master需要持久化前两种元数据,即命令空间及文件到chunk之间的映射关系;对于第三种元数据,即Chunk副本的位置信息,Master可以选择不进行持久化,这是因为ChunkServer维护了这些信息,即使Master发生故障,也可以在重启时通过ChunkServer汇报来获取。

GFS采用复制多个副本的方式实现Chunk Server的容错,每一个Chunk有多个存储副本,分别存储在不同的Chunk Server上。对于每一个Chunk,必须将所有的副本全部写入成功,才视为成功写入。如果相关的副本出现丢失或不可恢复的情况,Master自动将给副本复制到其它Chunk Server,从而确保副本保持一定的个数。

另外,Chunk Server会对存储的数据维持校验和。GFS以64MB为Chunk大小来划分文件,每一个Chunk又以Block为单位进行划分,大小为64KB,每一个Block对应一个32位的校验和。当读取一个Chunk副本时,Chunk Server会将读取的数据和校验和进行比较,如果不匹配,就会返回错误,客户端将选择其它Chunk Server上的副本。

Master内存占用

Master维护了系统中的元数据,包括文件及chunk名字空间,文件到chunk的映射,chunk副本的位置信息。其中前两种元数据需要持久化到磁盘,chunk副本的位置信息不需要持久化,可以通过Chunk Server汇报获取。

内存是Master的稀有资源,下面估算Master的内存使用量。Chunk的元信息包括全局唯一的ID,版本号,每个副本所在的Chunk Server编号,引用计数等。GFS系统中每个chunk大小为64MB,默认存储3份,每个chunk的元数据小于64字节。那么1PB数据的chunk元信息大小不超过1PB * 3 / 64MB * 64 = 3GB。另外,Master对命名空间进行了压缩存储,例如有两个文件foo1和foo2都存放在目录/home/very_long_directory_name/中,那么目录名在内存中只需要存放一次。压缩存储后,每个文件在文件名字空间的元数据也不超过64字节,由于GFS中的文件一般都是大文件,因此,文件名字空间占用内存不多。这也就说明了Master内存容量不会成为GFS的系统瓶颈。

负载均衡

GFS中副本的分布策略需要考虑多种因素,如网络的拓扑,机架的分布,磁盘的利用率等等。为了提高系统的可用性,GFS会避免同一个chunk的所有副本都存放在同一个机架的情况。

系统中有三种需要创建chunk副本的情况:chunk创建,chunk重新复制(re-replication)以及重新平衡(rebalancing)。

当Master创建了一个chunk,它会根据如下因素来选择chunk副本的初始位置:(1) 新副本所在的Chunk Server的磁盘利用率低于平均水平;(2) 限制每个Chunk Server”最近”创建的数量。(3)每个chunk的所有副本不能在同一个机架。第二点容易忽略但却很重要,因为创建完chunk以后通常需要马上写入数据,如果不限制”最近”创建的数量,当一台空的Chunk Server上线时,由于磁盘利用率低,可能导致大量的chunk瞬间迁移到这台机器从而将它压垮。

当Chunk的副本数量小于一定的数量后,Master会尝试重新复制一个chunk副本。可能的原因包括Chunk Server宕机或者Chunk Server报告自己的副本损坏,或者它的某个磁盘故障,或者用户动态增加了Chunk的副本数,等等。每一个chunk复制任务都有一个优先级,按照优先级从高到低在Master排队等待执行。例如,只有一个副本的chunk需要优先复制,又如,有效文件的chunk复制优先级比最近删除的文件的chunk高,最后,GFS会提高所有阻塞客户端操作的chunk复制任务的优先级,例如客户端正在往一个只有一个副本的chunk追加数据,如果限制至少需要追加成功两个副本,那么这个chunk复制任务会阻塞客户端写操作,需要提高优先级。

最后,Master会定期扫描当前副本的分布情况,如果发现磁盘使用量或者机器负载不均衡,将执行重新平衡操作。

无论是chunk创建,chunk重新复制,还是重新平衡,它们选择chunk副本位置的策略都是相同的,并且需要限制重新复制和重新平衡任务的拷贝速度,否则可能影响系统正常的读写服务。

垃圾回收

GFS采用延迟删除的机制,也就是说,当文件被删除后,GFS并不要求立即归还可用的物理存储,而是在元数据中将文件改名为一个隐藏的名字,并且包含一个删除时间戳。Master定时检查,如果发现文件删除超过一段时间(默认为3天,可配置),那么它会把文件从内存元数据中删除,以后Chunk Server和Master的心跳消息中,每一个Chunk Server都将报告自己的chunk集合,Master会回复在Master元数据中已经不存在的chunk信息,这时,Chunk Server会释放这些Chunk副本。为了减轻系统的负载,垃圾回收一般在服务低峰期执行,比如每天晚上凌晨1:00开始。

另外,Chunk副本可能会因为Chunk Server失效期间丢失了对Chunk的修改操作而导致过期。系统对每个Chunk都维护了版本号,过期的Chunk可以通过版本号检测出来。Master仍然通过正常的垃圾回收机制来删除过期的副本。

快照

快照(Snapshot)操作是对源文件/目录进行一个”快照”操作,生成该时刻源文件/目录的一个瞬间状态存放与目标文件/目录中。GFS中使用标准的copy-on-write机制生成快照,也就是说,”快照”只是增加GFS中chunk的引用计数,表示这个chunk被快照文件引用了,等到客户端修改这个chunk时,才需要在Chunk Server中拷贝chunk的数据生成新的chunk,后续的修改操作落到新生成的chunk上。

为了对某个文件做Snapshot,首先需要停止这个文件的写服务,接着增加这个文件的所有chunk的引用计数,以后修改这些chunk时会拷贝生成新的chunk。对某个文件执行Snapshot的大致步骤如下:

1, 通过Lease机制收回对文件每一个chunk写权限,停止对文件的写服务;

2, Master拷贝文件名等元数据生成一个新的Snapshot文件;

3, 对执行Snapshot的文件的所有chunk增加引用计数;

例如,对文件foo执行快照操作生成foo_backup,foo在GFS中有三个chunk C1,C2和C3。Master首先需要收回C1,C2和C3的写Lease,从而保证文件foo处于一致的状态,接着Master复制foo文件的元数据生成foo_backup,foo_backup同样指向C1,C2和C3。快照前,C1,C2和C3只被一个文件foo引用,因此引用计数为1;执行快照操作后,这些chunk的引用计数增加为2。以后客户端再次往C3追加数据时,Master发现C3的引用计数大于1,通知C3所在的Chunk Server本次拷贝C3生成C3’,客户端的追加操作也相应地转向C3’。

ChunkServer

ChunkServer管理大小均为64MB的chunk,存储的时候需要保证chunk尽可能均匀地分布在不同的磁盘之中,可能考虑的因素包括磁盘空间,最近新建chunk数,等。另外,Linux文件系统删除64MB大文件消耗的时间太长,且没有必要,删除Chunk可以只将对应的chunk文件移动到每个磁盘中的回收站,以后新建chunk的时候可以重用。

ChunkServer是一个磁盘和网络IO密集型应用,为了最大限度地发挥机器性能,需要能够做到将磁盘和网络操作异步化,这会增加代码实现的难度。

跨机房问题

跨机房问题一直都是一个老大难的问题,先看传统数据库的跨机房方案。

Master/Slave方案

这是最常用的方案,适用于大多数需求。Master将操作日志实时地发送到Slave,Slave当成Master的一个Hot Backup。Master宕机时,服务切换到Slave,需要修改客户端逻辑使得Master失效时自动寻找新的Master。

这个方案有一个问题就是数据库的Master和Slave一般不是强同步的,所以,切换到Slave后可能丢失宕机前的少量更新。如果将Master和Slave做成强同步的,即:所有的数据必须同时写成功Master和Slave才成功返回客户端,这样又带来了另外一个问题:Master和Slave中任何一台机器宕机都不允许写服务,可用性太差。因此,Oracle有一种折衷的模式:正常情况下Master和Slave是强同步的,当Master检测到Slave故障,比如Slave宕机或者Master与Slave之间网络不通时,Master本地写成功就返回客户端。采用这种折衷的同步模式后,一般情况下Master和Slave之间是强同步的,Master宕机后切换到Slave是安全的。当然,为了确保数据安全后,宕机的Master重启后可以和新的Master(原有的Slave)对比最后更新的操作日志,如果发现不一致可以提醒DBA手工介入,执行数据订正过程。

Master和Slave之间强同步还有一个问题就是跨机房延时,对于关键业务,同城的机房可以部署专用光纤,在硬件层面上解决这个问题;异地的机房一般用来做备份,与主机房之间的数据同步一般是异步的,可能有秒级延时。

Bigtable跨机房方案

Bigtable跨机房部署两套集群,每个机房有各自的GFS存储和Bigtable Master。机房之间的数据同步方式为异步,类似Master/Slave方案。Bigtable Tablet Server将操作日志Flush到GFS成功后返回客户端,并生成异步任务将操作日志同步到备机房。这里的难点在于Tablet Server宕机时,某些操作日志还没有完成同步,因此,操作日志同步点也需要记录到GFS中,当其它Tablet Server加载宕机Tablet Server原先服务的tablet时,将继续发送没有同步完成的操作日志到备机房。如果主机房整体发生故障,比如机房停电,可以手工将服务切换到备机房,这时会丢失最后的一部分更新操作,需要人工执行订正操作。

Bigtable跨机房方案还有一个问题,为了提高压缩率,Bigtable跨机房的同步是按列进行的,而Bigtable保证行事务,这样就可能出现某些行的部分列同步成功,部分列同步失败,破坏行事务。早期的Google App Engine底层存储为Bigtable,这个问题没有给出自动化的解决方案。

Megastore跨机房方案(基于Paxos)

一般来说,实际中使用的方案都是Master/Slave方案,Megastore中基于Paxos的方案理论上是目前最优的,但是实现过于复杂,只有Google在工程上做了实现。Master/Slave方案的问题在于Master宕机时切换到Slave需要时间,为了保证不会同时出现两个Master的情况,这个时间一般比较长,比如30s ~ 1分钟,而且不能做到自动化。Paxos的好处在于允许多个机房同时做Master,同时提供写服务,Paxos协议将通过Quorum-Based的策略保证达成一致。一般情况下,主机房作为Paxos协议的Leader提供写服务,当Leader发生故障时,备机房的节点可以被选为新的Leader提供写服务。即使多个机房认为自己是Leader,Paxos协议也能保证同一时刻只有一个Leader的写操作被大家同意并生效,并且做到了宕机切换的自动化。只要超过一半的机房没有出现故障,Paxos协议就能够保证不停写服务。

Google App Engine目前依赖于Google Megastore,解决了机房宕机可能破坏行事务的问题。Amazon Dynamo也给出了一种Vector Clock的做法解决多点同时写入的问题,这是一种事后验证的做法,理论上很有意思,但由于弱一致性,实践上没有特别成功的案例。

需要注意的是,Megastore中的复制方案在理论上很完美,但实现过于复杂,基本没有可行性。另外,无论采用怎样的跨机房同步和切换方案,都不能解决强同步写操作延时较长的问题,一般来说,这个延时将达到几十到几百毫秒。

一种回避Paxos的切换方案

选主一般可以通过引入开源的Zookeeper做到,不过Zookeeper本身的稳定性尚待考验,有一种回避Paxos的切换方案比较有意思。机房宕机切换自动化成本太高,但是对于很多单点服务,机房内部宕机切换的自动化很有必要。Oceanbase采用Linux的一个开源方案:Pacemaker,通过heartbeat和虚IP漂移的方式实现机房内部宕机自动切换。由于主备切换本质上是一个选主问题,理论上只有Paxos或者类似协议可以解决,而Pacemaker没有采用复杂的Paxos协议,它对硬件是有依赖的,比如要求主备节点之间通过直连线保证网络不会发生故障,而这在机房内部是可以做到的。机房之间采用前面提到的Master/Slave方案,可以写一个脚本ping主机房的Master,当确认主机房Master宕机时(比如一分钟不通)将服务切换到备机房并报警。

”云存储系统“赏析系列分享三:SQL与NOSQL

8月2日(下周二)内部分享的ppt,分为几个部分:

1, 单机存储引擎看SQL与NOSQL;

2, NOSQL从单机扩展到多机的关键点;

3, 从Megastore看SQL与NOSQL的融合;

4, 设计实现的一些Work around方法及技巧;

ppt比较简单,这几天将针对其中的”单机扩展到多机“问题写一篇博客。

缓存设计的一些思考

互联网架构中缓存无处不在,某厂牛人曾经说过:”缓存就像清凉油,哪里不舒服,抹一下就好了”。高品质的存储容量小,价格高;低品质存储容量大,价格低,缓存的目的就在于”扩充”高品质存储的容量。本文探讨缓存相关的一些问题。

LRU替换算法

缓存的技术点包括内存管理和替换算法。LRU是使用最多的替换算法,每次淘汰最久没有使用的元素。LRU缓存实现分为两个部分:Hash表和LRU链表,Hash表用于查找缓存中的元素,LRU链表用于淘汰。内存常以Slab的方式管理。

上图是Memcache的内存管理示意图,Memcache以Slab方式管理内存块,从系统申请1MB大小的大块内存并划分为不同大小的Chunk,不同Slab的Chunk大小依次为80字节,80 * 1.25,80 * 1.25^2, …。向Memcache中添加item时,Memcache会根据item的大小选择合适的Chunk。

Oceanbase最初也采用LRU算法,只是内存管理有些不同。Oceanbase向系统申请2MB大小的大块内存,插入item时直接追加到最后一个2MB内存块的尾部,当缓存的内存量太大需要回收时根据一定的策略整块回收2MB的内存,比如回收最近最少使用的item所在的2MB内存块。这样的做法虽然不是特别精确,但是内存管理简单,对于系统初期很有好处。

缓存锁

缓存需要操作两个数据结构:Hash表和LRU链表。多线程操作cache时需要加锁,比较直接的做法是整体加一把大锁后再操作Hash表和LRU链表。有如下的优化思路:

1, Hash表和LRU链表使用两把不同的锁,且Hash表锁的粒度可以降低到每个Hash桶一把锁。这种做法的难点是需要处理两种数据结构不一致导致的问题,假设操作顺序为read hash -> del hash item -> del lru item -> read lru item,最后一次read lru item时item所在的内存块可能已经被回收或者重用,一般需要引入引用计数并考虑复杂的时序问题。

2, 采用多个LRU链表以减少LRU表锁粒度。Hash表的锁冲突可以通过增加Hash桶的个数来解决,而LRU链表是一个整体,难以分解。可以将缓存的数据分成多个工作集,每个item属于某个工作集,每个工作集一个LRU链表。这样做的主要问题是可能不均衡,比如某个工作集很热,某些从整体上看比较热的数据也可能被淘汰。

3, 牺牲LRU的精确性以减少锁。比如Mysql中的LRU算法变形,大致如下:将LRU链表分成两部分,前半部分和后半部分,如果访问的item在前半部分,什么也不做,而不是像传统的LRU算法那样将item移动到链表头部;又如Linux Page Cache中的CLOCK算法。Oceanbase目前的缓存算法也是通过牺牲精确性来减少锁。前面提到,Oceanbase缓存以2MB的内存块为单位进行淘汰,最开始采用LRU策略,每次淘汰最近最少使用的item所在的2MB内存块,然而,这样做的问题是需要维护最近最少使用的item,即每次读写缓存都需要加锁。后续我们将淘汰策略修改为:每个2MB的内存块记录一个访问次数和一个最近访问时间,每次读取item时,如果访问次数大于所有2MB内存块访问次数的平均值,更新最近访问时间;否则,将访问次数加1。根据记录的最近访问时间淘汰2MB内存块。虽然,这个算法的缓存命中率不容易评估,但是缓存读取只需要一些原子操作,不需要加锁,大大减少了锁粒度。

4, 批量操作。缓存命中时不需要立即更新LRU链表,而是可以将命中的item保存在线程Buffer中,积累了一定数量后一次性更新LRU链表。

LIRS思想

Cache有两个问题:一个是前面提到的降低锁粒度,另一个是提高精准度,或者称为提高命中率。LRU在大多数情况下表现是不错的,但是有如下的问题:

1, 顺序扫描。顺序扫描的情况下LRU没有命中情况,而且会淘汰其它将要被访问的item从而污染cache。

2, 循环的数据集大于缓存大小。如果循环访问且数据集大于缓存大小,那么没有命中情况。

之所以会出现上述一些比较极端的问题,是因为LRU只考虑访问时间而没有考虑访问频率,而LIRS在这方面做得比较好。LIRS将数据分为两部分:LIR(Low Inner-reference Recency)和HIR(High Inner-reference Recency),其中,LIR中的数据是热点,在较短的时间内被访问了至少两次。LIRS可以看成是一种分级思想:第一级是HIR,第二级是LIR,数据先进入到第一级,当数据在较短的时间内被访问两次时成为热点数据则进入LIR,HIR和LIR内部都采用LRU策略。这样,LIR中的数据比较稳定,解决了LRU的上述两个问题。LIRS论文中提出了一种实现方式,不过我们可以做一些变化,如可以实现两级cache,cache元素先进入第一级cache,当访问频率达到一定值(比如2)时升级到第二级,第一级和第二级均内部采用LRU进行替换。Oracle Buffer Cache中的Touch Count算法也是采用了类似的思想。

SSD与缓存

SSD发展很快,大有取代传统磁盘之势。SSD的发展是否会使得单机缓存变得毫无必要我们无从得知,目前,Memory + SSD + 磁盘的混合存储方案还是比较靠谱的。SSD使用可以有如下不同的模式:

1, write-back:数据读写都走SSD,内存中的数据写入到SSD即可,另外有单独的线程定期将SSD中的数据刷到磁盘。典型的代表如Facebook Flashcache。

2, write-through:数据写操作需要先写到磁盘,内存和SSD合在一起看成两级缓存,即cache中相对较冷的数据在SSD,相对较热的数据在内存。

当然,随着SSD的应用,我想减少缓存锁粒度的重要性会越来越突出。

总结&推荐资料

到目前为止,我们在SSD,缓存相关优化的工作还是比较少的。今后的一年左右时间,我们将会投入一定的精力在系统优化上,相信到时候再来总结的时候认识会更加深刻。我想,缓存相关的优化工作首先要做的是根据需求制定一个大致的评价标准,接着使用实际数据做一些实验,最终可能会同时保留两到三种实现方式或者配置略微有所不同的缓存实现。缓存相关的推荐资料如下:

[1] Touch Count Algorithm. http://youyus.com/wp-content/uploads/resource/Shallahamer%20TC4a.pdf

[2] LIRS. http://portal.acm.org/citation.cfm?id=511340

GDB的两个技巧

分享两个GDB的小技巧:

1, GDB失效时手工得到stack;

2, GDB执行用户命令脚本;

调试内存型服务程序的有时会遇到core dump或死锁问题,且gdb或者pstack都无法显示调用栈(call stack)。这是因为线程的调用栈被破坏了,而调用栈存放了函数的返回地址,gdb解析函数返回地址(根据地址查找符号表)失败,gdb也没有进行容错处理,只要有一处地址解析失败就无法展开调用栈。然而幸运的是,调用栈往往只是部分被破坏,RSP堆栈寄存器中保存的值往往也是正确的,可以通过手工的方法恢复。具体做法如下:

(gdb) set logging on
Copying output to gdb.txt.
(gdb) x /2000a $rsp
0x426cb890: 0x0 0x4
0x426cb8a0: 0x426cb8c0 0x100
0x426cb8b0: 0x3e8 0x552f59 <_ZN5tbnet16EPollSocketEvent9getEventsEiPNS_7IOEventEi+41>
0x426cb8c0: 0x1823c8a000000011 0x0
0x426cb8d0: 0x0 0x0
0x426cb8e0: 0x0 0x0
...

如上图,类似”0x552f59 <_ZN5tbnet16EPollSocketEvent9getEventsEiPNS_7IOEventEi+41>”这样的代码符号看起来是有效的。通过所有看似有效的程序代码符号基本能够得出core dump时的调用栈。

当然,有可能出现core dump线程的调用栈被完全破坏的情况,通过上述方法恢复的信息仍然是无效的。由于每个线程堆栈地址空间的大小为10M,因此,线程之间互相破坏调用堆栈的可能性几乎是不存在的,此时,可以通过其它线程的调用栈分析其行为,往往也能找到线索。如果所有线程的调用栈都“看似被破坏”,那么,往往有两种可能:

a, 可执行程序和core文件对不上,被摆乌龙了,如发现core dump问题的时候可执行程序已经更新到最新版本,老版本没有保存;

b, 磁盘满了或者ulimit设置太小,导致core dump文件信息不全;

如果core文件对不上或者信息不全的问题,还可以通过dmesg命令找到程序core dump时的指令寄存器RIP的值,再通过addr2line获取程序最后执行的代码行。如:

[rizhao.ych@OceanBase036040 updateserver]$ dmesg | grep updateserver
updateserver[8099]: segfault at 0000000000000000 rip 0000000000500fbf rsp 000000004c296e30 error 4

[rizhao.ych@OceanBase036040 updateserver]$ addr2line -e updateserver 0000000000500fbf
/home/rizhao/dev/oceanbase/src/common/ob_base_server.cpp:222

另外一个用得比较多的功能是GDB执行用户命令脚本。我们组无施同学有一个例子:Oceanbase系统有一个ObGetParam的类,是一个数组,里面的每个元素是一个ObCellInfo,ObGetParam中可能包含成百上千个ObCellInfo,现在需要在GDB调试的时候输出数组中所有的ObCellInfo对象信息。脚本如下:


define dumpGetParam
set $cell_list = ($arg0)
set $cell_num = ($arg1)
set $cell_idx = (0)
while ($cell_idx < $cell_num)
  printf "cell_idx:%d,table_id:%llu,column_id:%llu\n", $cell_idx, 
    $cell_list[$cell_idx].table_id_, $cell_list[$cell_idx].column_id
  set $cell_idx = $cell_idx + 1
end
end

上面的代码定义了一个命令叫dumpGetParam,其第一个参数$arg0是cell数组的地址,第二个参数$arg1是数组大小,代码的功能就是打印所有cell的信息。
把上面的代码写入一个文本文件dump_get_param.txt,在gdb中执行source dump_get_param.txt,然后就可以使用dumpGetParam命令了。

Microsoft Azure Storage架构分析

Microsoft云存储服务分为两个部分,SQL Azure和Azure Storage。云存储系统的可扩展性和功能不可兼得,必须牺牲一定的关系数据库功能换取可扩展性。Microsoft实现云存储的思路有两种:

1, 做减法。SQL Azure直接在原有的SQL Server上引入分布式的因素,在满足一定可扩展性的前提下尽可能不牺牲原有的关系型数据库功能。SQL Azure的可扩展性是有限的,单个SQL Azure实例不允许超过50GB,这是因为SQL Azure不支持子表动态分裂,单个SQL Azure实例必须足够小从而可以被一个节点服务。具体信息可以参考我以前的一篇文章:Microsoft SQL Azure架构设计

2, 做加法。Azure Storage先做好底层可扩展性,然后再逐步加入功能,这与Google GFS & Bigtable的思路比较一致。Azure Storage分为Blob, Queue和Table三个部分,其中Azure Table Storage最具有代表性,由于底层系统支持子表分裂,单个用户的最大数据量可以达到100TB。然而Table Storage支持的功能有限,甚至不支持索引功能。具体信息可以参考msdn的一篇文章:Azure Storage架构介绍

Microsoft Azure Storage 逻辑上分为三层:

1, 前端(Front-End Layer):类似互联网公司的Web服务器层,可采用LVS + Nginx的设计,主要做一些杂事,比如权限验证。由于前端服务器没有状态,因此很容易实现可扩展。

2, 存储层 (Partition Layer):类似Bigtable,分为Partition Master和Partition Server两种角色,分别对应Bigtable Master和Tablet Server。每一个Partition(相当于Bigtable中的Tablet)同时只能被一个Partition Server服务,Partition Master会执行负载均衡等工作。Bigtable中分为Root Table, Meta Table和User Table,Azure Table Storage可能会为了简单起见消除Meta Table,所有的元数据操作全部放到Partition Master上。

3, 文件系统层(DFS Layer):类似GFS,数据按照extent(相当于GFS中的chunk)划分,每个extent大小在100MB ~ 1GB之间。数据存储三份,写操作经过Primary同步到多个Secondary,读操作可以选择负载较轻的某个Primary或者Secondary副本。当发生机器故障时,需要选择其它机器上的Secondary切换为Primary继续提供写服务,另外需要通过增加副本操作使得每个extent的副本数维持在安全值,比如三份。为了简单起见,DFS Layer对上层Partition Layer可以不提供文件系统接口,只提供类似块设备的访问方式。

Azure Storage的主键包括Partition Key + Row Key两部分,其中,Partition Key用于数据划分,规定相同的Partition Key只属于同一个Partition,从而被一台Partition Server服务,这就使得Partition Key相同的多个行之间能够支持事务。与SQL Azure不同,Azure Storage的并发操作通过乐观锁的方式实现。Azure Storage包含三个不同的产品,其中Azure Table Storage支持用户设置Schema,支持byte[], bool, DataTime, double, Guid, Int32, Int64, String这几种列类型;Azure Blob Storage将Blob数据存放到底层的DFS Layer中,Blob过大时可能存放到多个extent中,Partition Layer存储每个Blob的编号到Blob所在的多个extent位置之间的映射关系;Azure Queue Storage将Partition Key设置为Queue的编号,Row Key设置为消息的编号,从而保证属于同一个Queue的消息连续存放。

总之,Microsoft Azure Storage和早期的Bigtable总体架构是很类似的,可能做了一些简化,这也间接说明了一点:如果不发生重大硬件变革,工程上要实现高可扩展的分布式B+树,将云存储系统分成文件+表格两层还是比较靠谱的。开发人员更多地需要在实现细节上下功夫,落实到线上的每行代码上。

Oceanbase – 千亿级海量数据库

我在数据库大会有一个报告:<<Oceanbase – 千亿级海量数据库>>,ppt已上传到Slideshare上。有一些同学问我,Oceanbase的创新点在哪里?

从大学的数据结构课程可以知道,数据量比较大时,有两种数据结构很常用:哈希表和B+树,分布式系统也是类似的。如下图:

云存储系统.png

Amazon的系统实现了一个分布式哈希表,而Google Bigtable, Yahoo PNUTS,Microsoft SQL Azure实现了一颗分布式B+树。分布式哈希表实现相对简单,但只支持随机读取;而分布式B+树支持范围查询,但实现比较复杂,主要有两个难点:

1, 状态数据的持久化和迁移。更新操作改变系统的状态,数据库系统中更新操作首先以事务提交日志(MySQL称为binlog, NOSQL称为commit log)写入到磁盘,为了保证可靠性,commit log需要复制多份并保证它们之间的一致性。另外,机器宕机时需要通过commit log记录的状态修改信息将服务迁移到集群中的其它节点。

2, 子表的分裂和合并。B+树实现的难点在于树节点的分裂与合并,在分布式系统中,数据被顺序划分为大小在几十到几百MB大小的数据范围,一般称为子表,相当于B+树结构中的叶子节点。由于每个子表在系统中存储多份,需要保证多个副本之间的分裂点是一致的。由于子表在分裂的同时也有更新操作,保证多个副本之间一致是比较困难的。

对于这两个问题,不同的系统有不同的解决方法:

1, 状态维持。Google Bigtable将状态数据写入到GFS中,由GFS提供可靠性保证,但GFS本身是一个巨大的工程;Yahoo PNUTS将状态数据写入到分布式消息中间件,Yahoo内部称为Yahoo Message Broker;Microsoft SQL Azure直接通过网络将数据复制到多机,由于一台机器服务多个子表,这些子表的副本可能分布在整个集群中,因此,任何两台机器都可能建立数据复制的网络通道,需要处理与这些通道有关的异常情况。

2, 子表分裂。由于底层有GFS保证可靠性,Google Bigtable设计时保证每一个子表同时只被一台机器(Tablet Server)服务;Yahoo PNUTS通过引入复杂的两节点提交(Two-phase commit)协议协调多个副本之间的一致性,使得他们的分裂点相同;Microsoft SQL Azure干脆不支持子表分裂,牺牲一部分扩展性从而简化系统设计。

淘宝Oceanbase设计之初对淘宝的在线存储需求进行分析发现:淘宝的数据总量比较大,未来一段时间,比如五年之内的数据规模为百TB级别,千亿条记录,另外,数据膨胀很快,传统的分库分表对业务造成很大的压力,必须设计自动化的分布式系统;然而,在线存储每天的修改量很小,大多数情况下单机的内存就能存放下。因此,我们采用将动态数据和静态数据分离的办法。动态数据的数据量小,采用集中式的方法解决,这样,状态数据维持从一个分布式的问题转化为单机的问题;静态数据的数据量大,采用分布式的方法解决,因为静态数据基本不变,实现时不需要复杂的线程同步机制,另外,保证静态数据的多个副本之间一致性是比较容易的,简化了子表的分裂和合并操作。通过这样的权衡,淘宝Oceanbase以一种很简单的方式满足了未来一段时间的在线存储需求,并且还获得了一些其它特性,如高效支持跨行跨表事务,这对于淘宝的业务是非常重要的。另外,我们之所以敢于做这样的权衡,还有一个重要的原因:我们内部已经思考了很多关于动态数据由集中式变为分布式的方案,即使我们对需求估计有些偏差,也可以很快修改原有系统进一步提高可扩展性。