（一）关键问题

• 数据分布

1）哈希分布 => 随机读取

取模直接哈希：将不同哈希值的数据分布到不同的服务器上

关键：找出一个散列特性很好的哈希函数

问题：增加、减少服务器时的大量数据迁移

解决：1）将<哈希值,服务器>元数据存储在元数据服务器中；2）一致性哈希

一致性哈希： 给系统每个节点分配一个随机token，这些token构成一个hash环。执行数据存放操作时，先计算key的hash值，然后存放到顺时针方向第一个大于或者等于该hash值的token所在节点。

优点： 节点增加/删除时只会影响到在hash环中相邻的节点，而对其他节点没影响。

维护每台机器在哈希环中的位置方式：1） 记录它前一个&后一个节点的位置信息，每次查找可能遍历整个哈希环所有服务器；2） O（logN）位置信息，查找的时间复杂度为O（logN）；3） 每台服务器维护整个集群中所有服务器的位置信息，查找服务器的时间复杂度为O（1）

虚拟节点：

2）顺序分布 => 顺序扫描

表格上的数据按照主键整体有序

• 负载均衡

1）数据写入时，写入节点的选择

2）运行过程中，数据的迁移

• 复制&多备份

1）最大保护模式

强同步复制：至少在一个备库上执行成功

2）最大性能模式

异步复制模式：主库执行成功即返回

3）最大可用性模式

两种模式折衷：正常情况是最大保护模式，出现故障时编程最大性能模式

• 数据一致性

版本号：删除老的版本号

• 容错

1）故障检测

心跳：S每隔一段时间向C发送一个心跳包

租约机制：带有超时时间的授权

2）故障恢复

master：主备机制，持久化索引

datanode：永久故障，增加备份

• 可扩展性

1）总控节点是否成为瓶颈

不是瓶颈：舍弃小文件的处理，数据的读写控制权下放到工作机，通过客户端缓存元数据减少对总控节点的访问

内存成为瓶颈：采用两级结构，在总控机与工作机之间加一层元数据节点

2）同构系统

存储节点分为若干组，每个组内的节点服务完全相同的数据

3）异构系统

将数据划分为大小接近的分片，每个分片的多个副本分布到集群中的任何一个存储节点，某个节点发生故障，原有的服务将由整个集群而不是某几个固定的存储节点来恢复

（二）GFS

• 适用场景

1）适当数量大文件（超过100MB），GB以上很常见

2）大量流式读，小量随机读，连续写，追加写

3）高带宽比低延时更重要，要求快速处理大量数据，对单一操作的响应时间无严格要求

4）不适合多用户写入

• 数据分布

单位：chunk（64MB）；一个文件占用多个chunk

优：1）减少client与master交互次数；2）减少client与chunkserver交互次数；3）减少元数据规模

缺：1）内部碎片；2）热点小文件使chunkserver负载过重

• 负载均衡

1）数据写入时，通过磁盘利用率、最近创建chunk数量来决定写哪个chunkserver，并保证chunk所有副本不在同一机架

2）运行过程中的数据迁移，根据吸盘适用率、负载，将>平均的chunk迁到<平均的

• 复制

写入主副本，再写入备副本，全部写完后才返回成功

• 数据一致性

        使用租约机制保障在跨多个副本的数据写入中保持顺序一致性。 GFS Master将chunk租约发放给主副本，主副本确定针对该chunk的写入顺序，次副本遵守这个顺序，以此保障了全局顺序一致性。

• 容错

master：持久化1）命名空间，文件系统目录结构&chunk信息；2）文件到chunk之间的映射；log和checkpoint技术，checkpoint相当于全量备份，log记录元数据的每一次变化

chunk：1）多副本；2）校验和检测错误数据

• 可扩展性

扩展chunkserver

• 数据读写

1）读数据。客户端缓存了从master请求的副本位置，直接选择最优的副本访问。

2）写数据。采用流水线方式，分离数据流和控制流。客户端选择最佳的网络拓扑按照流水线技术传输数据。主副本决定数据的写入顺序。

（三）TFS

• 适用场景

海量小文件（不超过1MB）

• 数据分布

单位：block（64MB）；一个block上存储多个小文件

每个block在整个集群拥有唯一ID=>blockID，由namenode分配

namenode：1）维护每个block与datanode的相关信息and可写block信息列表；2）dataserver的加入、退出和心跳信息

datanode：1）维护block中每个文件位置信息（blockID，块内fileID）；2）实际数据的存储和读写

• 负载均衡&复制

1）数据写入时，根据可写块，容量，负载决定

2）集群负载轻的时候，namenode对datanode上的block进行均衡；优先选择统计器的源到目的之间的移动，也就是童泰datanode的不同datanode进程。

• 数据一致性

namenode写主副本，主副本写备副本，更新版本号，返回客户端

• 容错

1）namenode：主备HA结构。

        两台机器互为热备，同时运行，一台为主，一台为备。

        主机绑定到对外vip，提供服务；当主机宕机后，迅速将vip绑定至备机，切换其为主机。

2）datanode：namenode检测到备份数减少的block，对这些block重新进行数据复制。

3）故障检测：心跳，datanode会把自己拥有的block发送给namenode，namenode会根据这些信息重建datanode和block的关系

• 可扩展性

        扩展datanode节点。将相应数量的新datanode服务器部署好应用程序后启动即可。这些datanode服务器会向namenode进行心跳汇报。namenode会根据datanode容量的比率和datanode的负载决定新数据写往哪台datanode服务器。

• 数据读写

1）客户端将文件名转换为blockID和fileID信息；

2）在namenode取得该块所在datanode信息，如果客户端有该block与datanode缓存，直接从缓存中取；

3）直接与datanode进行读取操作

（四）Haystack

• 适用场景

1）大量小文件

2）越新写入的文件越容易被读到

3）大量读，少量写，几乎无修改

• 数据分布

单位：colume（100GB）；一个逻辑colume对应3个物理colume

• 负载均衡

• 复制
• 数据一致性
• 容错

1）故障检测：pitchfork周期性检测每个store机器的健康度

• 可扩展性
• 数据读写

（五）Dynamo

• 适用场景

1）查询模型：基于K-V模型，而不是SQL关系模型

2）存储对象较小，通常小于1MB

3）数据存储的写是高可用的（将协调冲突的复杂性推给读，以确保写永远不会拒绝）

• 设计考虑

1）增量的可扩展性：水平扩展一台存储主机，而对系统操作者和系统本身影响很小。

2）对称性：每个节点与它的对等节点责任相同。

3）去中心化：没有集中管理的节点。

4）异质性：机器配置异质，负载的分配与各个服务器的能力成正比。

• 数据分布

一致性hash => 虚拟节点

1）一致性hash

        在一致性哈希中，哈希函数的输出范围为一个圆环，如图2所示，系统中每个节点映射到环中某个位置，而Key也被Hash到环中某个位置，Key从其被映射的位置开始沿顺时针方向找到第一个位置比其大的节点作为其存储节点，换个角度说，就是每个系统节点负责从其映射的位置起到逆时针方向的第一个系统节点间的区域。

        问题：1）热点数据导致数据分布不均；2）每个节点性能型号不同但无法按照节点能力划分数据

2）虚拟节点

        每个节点从逻辑上切分为多个虚拟节点，一个物理节点可以按照其处理能力给其划分多个或者一个虚拟节点。

        1）虚拟节点数要远大于物理节点数

        2）加入一个物理节点时，可以从其他多个物理节点均分出虚拟节点给它

• 负载均衡&复制

         每个Key被分配到一个协调器（coordinator）节点，协调器节点管理其负责范围内的复制数据项，其除了在本地存储其责任范围内的每个Key外，还复制这些Key到环上顺时针方向的N-1个后继节点。

        B负责（A~B）范围的复制数据项，除了存储key值到本地，还要在B、C处复制key。

        1）由于存在虚拟节点，需要跳过环上某些位置，让键的首选节点列表分别位于不同的物理节点上。

        2）首选列表：负责存储特定键的节点列表。

• 数据一致性

        允许系统中同一时间出现多个版本的对象，客户端协调多个冲突版本提供最终一致性

        1）使用向量时钟来标识同一数据在不同节点上多个副本之间的因果关系。向量时钟实际上就是一个(节点，计数器)列表。

        2）读取过程中的协调。数据版本之间的关系要么是因果关系，要么是平行关系，关系判断依赖于计数器值大小，如果第一个时钟对象的计数器小于或等于所有其它时钟对象的计数器时则是因果关系，那么因是果的祖先可以认为是旧版数据而直接忽略，否则是平行关系，那么就认为数据版本产生了冲突，需要协调并合并。

        3）当客户端要更新一个对象，必须指定要更新哪个版本。

• 容错

1）对于临时故障的处理：暗示移交，数据key本来发往A（A临时故障），发往了D；key被定期扫描，如果A复苏，D发送key到A，并从本地删除key。

2）对于永久故障的处理：副本同步。

3）环关系。每个节点每隔一秒随机选择一个对等节点，通过gossip协议传播节点的映射信息，最终每隔节点都知道对等节点所处理范围。

4）新加节点发现。通过种子节点协调所有节点的成员关系。

5）错误检测。每个节点都可以了解其他节点的加入和离开。

• 可扩展性

 一致性hash

• 数据读写

        三个关键参数(N, R, W)，其中，N是指数据对象复制到N台主机，协调器负责将数据复制到N-1个节点上，亚马逊建议N配置为3，R代表一次成功的读取操作中最小参与节点数量，W代表一次成功的写操作中最小参与节点数量。 R和W值过小则影响一致性，过大则可用性。

        1）写操作：协调员（首选列表之一）生成向量时钟并本地写入新版本=>将新版本发给首选列表中可达节点=>收到W-1个节点响应->成功

        2）读操作：协调员（首选列表之一）请求首选列表所有版本数据=>等待R个响应返回给客户端没有因果关系的版本=>不同版本被协调，取代当前版本，写回

（六）Tair

分布式存储系统横向对比