分布式系统初步研究

SN架构下数据分布策略不当，会导致部分节点很忙，而其他节点很闲。 缓存利用 SD架构存在不同节点重复缓存相同内容，并且随系统规模扩大会导致节点缓存基本失效。 (ORALCE采用Cache Fusion来解决该问题，但导致了大量inter-node间通讯，以及并发控制问题)。 HA 工程实践 SD在单纯节点Failover比SN强 SN架构要求数据分布策略要求与存储空间和节点处理能力匹配，SD则不存在该问题，所以SD比SN扩容方便。 SD架构需要配合Cluster软件，安装和配置比较复杂。 系统可维护性 SN架构系统可维护性比SD强(例如当磁盘故障时，SN架构只对部分节点有影响，SD架构对所有节点都会产生影响) 三 分布式Key-Value存储系统

1. Key-Value存储系统

Key-value存储系统也常常被称为Key-value数据库。该系统存储记录为对，并且只提供简单访问API:Put(Key,value)，Get(Key)。Key-value系统由于简单，性能非常高,在只需要按主键访问场景下可以利用Key-Value存储系统，充分发挥key-value系统高并发与高性能优势(Key-value数据库系统与利用ORACLE数据库系统模拟key-value的对比测试表明key-value数据库在数据插入速度方面比ORALCE快30多倍。为保证公平测试时ORACLE插入客户端和ORALCE数据库运行在同一台服务器上)。

著名Key-value存储系统包括:Memcache、Berkeley DB、Tokyo Cabinet、BigTable、Dynamo、Cassandra、Voldemort、HyperTable等。Memcache是基于内存的key-value系统,Berkeley DB和Tokyo Cabinet是单机版的嵌入式key-value系统，BigTable(Google)、Dynamo(Amozon)、Cassandra(Facebook)、Voldemort(LinkIn)、HyperTable(Baidu)是分布式的Key-value系统。

目前大部分流量非常大web网站都采用Memcache作为查询缓存，极大减轻

数据库系统压力。

虽然目前很多大型网站有将传统关系型数据库系统(Mysql、Oracle)等转换Key-value数据库系统，特别是分布式Key-value数据库系统的趋势。当由于Key-value数据库提供API比较简单，因此对于一些需要做复杂的分析和查询场景下，还是无法替代传统关系数据库系统。

分布式key-value存储系统两种典型的代表是Bigtable和Dynamo，它们采取了两种截然不同技术路线，是分布式系统经典之作。 其他所有分布式key-value存储系统基本上都采取这两种技术路线中的一种。

2. BigTable a) BigTable简介

BigTable是Google公司开发用来存储海量结构化(严格讲是半结构化)数据的存储系统。BigTable在Google公司典型应用包括：存储Google公司网络爬虫从网上抓回来海量原始网页(key为到排URL)、存储Google Earth中卫星照片( key为物理地区上编号)。

BigTable属于Key-value存储系统。下表详细描述了传统Key-Value系统、BigTable、关系数据库的区别： 比较标准 数据模型 Key-Value BigTable 关系数据库 整个系统一张1多张表，每张表是三维结构1多张表，每张表表，该表记录。 是二维结构只有。 value>两个字以不同。 段。 3不支持表与表之间关系。 2 同一张表每行列数量必须相同。 4 每行都有一个字符串的3表之间可以定义row key,并且存储时按key严格的外键引用关字母顺序排序。 系,以及级连删除5 多个列组成一个列族等。 (ColumnFamily)，定义表结构时,只要定义列族。 API Get(key) Put(key,value) CreateTable DeleteTable CreateColumnFamily DeleteColumnFamily 通过SQL语言支持表的创建和修改，列添加和删除，表之间的引用关系。 根据Key来修改指定和访问支持对任何列的复指定行。 支持某个子集查找与遍历 事务 杂的查询和统计功能。 支持对单行访支持对单行访问支持整个数据库范问原子性。不(read-modify-write)原子围内的事务。 支持跨行事务 性。 不支持跨行事务。 b) BigTable体系结构

BigTable是建立Google File System之上，利用Google File System来存储BigTable的数据文件和LOG。BigTable的体系结构如下:

Tablet Server1Master控制/调度Tablet Server2基于GFS的全局存储池[Tablet1、tablet2、tablet3][tablet4、tablet5、tablet6][Tablet7、tablet8、tablet9]控制/调度控制/调度Tablet Server3读写ClientBigTable体系结构说明： ?

水平切分

BigTable将Table采取按Key进行水平切分，将一个Table切分为多个

Tablet，每个Tablet一般为100~200MB，存储一段范围行。

切分方式为自动分裂：最开始时Table只包含一个Tablet，随Tablet变大，每个Tablet会从中间分裂成两个Tablet。

每个Tablet由存储在GFS中多个文件(SSTable格式)与一个位于TabletServer内存中memtable组成。 ?

全局查找表

将Table水平切分后，读写操作需要定位出行所在Tablet以及Tablet被分配Tablet服务器。BigTable采用全局查找表方式实现该功能。

BigTable全局查找表是一个三级结构：

在Chubby(参考后面对Chubby描述)中存储Root Tablet的位置(即负责Root Tablet的TabletServer,Master在启动时第一件事情是将Root Tablet分配给某台Tablet Server)。

Root Tablet则存储MetaTable表(类似数据库系统中的系统表)所有Tablet位置。(Root Tablet是Meta Table第一个Tablet)。

MetaTable则存储User Tablets的位置信息。MetaTable中的RowKey为包含该Tablet所属Table 的name和该Tablet结束行key一个编码。

BigTable启动后将位置信息加载到内存(即负责管理MetaTable的TabletServer内存中中，同时Client会缓存部分位置信息，同时采集查询某个Tablet位置信息时会同时查询相邻的Tablet。

RootTalet不分裂，一般MetaTablet大小为128MB,每个UserTablet登记信息占1KB,那么最大可以容纳(128M/1K)*(128M/1K)=2的34次方个UserTablet。

BigTable虽然采取全局查找表，但该项工作不是由Master承当，而是