（一）关键问题
- 数据分布
对于存储系统，最重要的问题就是数据分布，即什么样的数据放置在什么样的节点上。数据分布时需要考虑数据是否均衡、以后是否容易扩容等一系列问题。不同的数据分布方式也存在不同的优缺点，需要根据自身数据特点进行选择。
1）哈希分布 => 随机读取
取模直接哈希：将不同哈希值的数据分布到不同的服务器上
关键：找出一个散列特性很好的哈希函数
问题：增加、减少服务器时的大量数据迁移
解决：1）将<哈希值,服务器>元数据存储在元数据服务器中；2）一致性哈希
一致性哈希： 给系统每个节点分配一个随机token，这些token构成一个hash环。执行数据存放操作时，先计算key的hash值，然后存放到顺时针方向第一个大于或者等于该hash值的token所在节点。
关键：哈希值变成了一个范围，每个物理节点上存储的数据是哈希值处于前一段范围的数据。
优点： 节点增加/删除时只会影响到在hash环中相邻的节点，而对其他节点没影响。
维护每台机器在哈希环中的位置方式：1） 记录它前一个&后一个节点的位置信息，每次查找可能遍历整个哈希环所有服务器；2） O（logN）位置信息，查找的时间复杂度为O（logN）；3） 每台服务器维护整个集群中所有服务器的位置信息，查找服务器的时间复杂度为O（1）
虚拟节点：将哈希取模的模数取得很大，就会得到更多的哈希值，这个哈希值成为逻辑节点，一个物理机器可以根据自己的能力选择若干个逻辑节点的存储节点。
优点：将传统哈希的一（物理节点）对一（哈希值）的分布变成了一（物理节点）对多（哈希值）的分布。可以根据物理节点的能力调整数据的分布。
2）顺序分布 => 顺序扫描
表格上的数据按照主键整体有序
- 负载均衡
1）数据写入时，写入节点的选择（空间容量？CPU负载？）
2）运行过程中，数据的迁移
如果运行过程中有新机器的加入，导致每个机器的存储数据量不同，需要能够自动发现，并自动进行调整。但是在调整的过程中也要控制好速度，以免对业务产生影响。
- 复制&多备份
1）最大保护模式
强同步复制：至少在一个备库上执行成功
至少成功存储2个备份，才返回成功。
2）最大性能模式
异步复制模式：主库执行成功即返回
只要成功存储1个备份，就返回成功。
3）最大可用性模式
两种模式折衷：正常情况是最大保护模式，出现故障时变成最大性能模式
- 数据一致性
版本号：在收到写入数据请求时，生成对应版本号。
删除老的版本号；读取时，保证读取到的是最新的版本号的数据；写入时，保证写入数据的版本号要新与存储的。
- 容错
1）故障检测
心跳：S每隔一段时间向C发送一个心跳包
租约机制：带有超时时间的授权
2）故障恢复
master：主备机制，持久化索引
datanode：永久故障，增加备份
- 可扩展性
1）总控节点是否成为瓶颈
不是瓶颈：舍弃小文件的处理，数据的读写控制权下放到工作机，通过客户端缓存元数据减少对总控节点的访问
内存成为瓶颈：采用两级结构，在总控机与工作机之间加一层元数据节点
2）同构系统
存储节点分为若干组，每个组内的节点服务完全相同的数据
3）异构系统
将数据划分为大小接近的分片，每个分片的多个副本分布到集群中的任何一个存储节点，某个节点发生故障，原有的服务将由整个集群而不是某几个固定的存储节点来恢复
（二）GFS（google分布式文件存储）
- 适用场景
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（taobao分布式图片存储）
- 适用场景
海量小文件（不超过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（facebook分布式照片存储）
- 适用场景
1）大量小文件
2）越新写入的文件越容易被读到
3）大量读，少量写，几乎无修改
- 数据分布
单位：colume（100GB）；一个逻辑colume对应不同机器上的3个物理colume
每个图片作为一个needle放在一个物理卷文件中，包含图片数据和逻辑图片的元数据；部分元数据装载到内存中作为index用于图片查找。
- 核心组件
1）Haystack Store（持久化存储系统）负责图片存储、管理图片的文件系统元数据。将其下所有吴丽娟的fd缓存在内存中
2）Haystack Directory（目录）维护逻辑到物理卷的映射、图片到逻辑卷的映射、某个逻辑卷的空闲空间等。采用Replicated Database做持久化存储，前面增加一个memcache集群满足查询需求。
3）Haystack Cache，类似于系统内部的CDN。可理解为一个分布式Hash Table，使用图片ID作为key来定位缓存的数据。
- 负载均衡
Directory在分配写请求到逻辑卷、分配读请求到物理卷时保证负载均衡。
- 数据一致性
只要写操作成功，逻辑卷对应的所有物理卷都存在一个有效的照片文件，但照片文件在不同物理卷中的offset可能不同。
- 容错
1）故障检测：pitchfork周期性检测每个store机器的健康度，检查其每个卷文件的可用性，并尝试读取数据。
2）故障恢复：bulk操作使用副本卷文件重置某个store机器的所有数据（对于永久损坏的磁盘）。
- 可扩展性
增加Haystack Store存储节点。
- 数据读写
1）读数据：浏览器->web服务器->Haystack目录->web服务器->浏览器->CDN->Haystack Cache->Haystack Store
2）写数据：发送到web服务器，web服务器从Directory中请求一个可写逻辑卷；web服务器为图片分配一个唯一的ID，然后将其上传至逻辑卷对应的每个物理卷。
（五）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（taobao分布式键值存储）
- 适用场景
分布式键值存储引擎
- 数据分布
单位：主键计算哈希值后的桶。
- 负载均衡
Config Server按照一定的策略把每个桶指派到不同的Data Server上，只要保证桶的分布的均衡性，就能保证数据分布的均衡性。
- 容错
1）Data Server故障，Config Server能检测到，如果备副本->复制数据到新的Data Server；主副本->提升另外的备副本为主副本，复制数据到新的Data Server。
2）Config Server故障，备Config Server提升为主Config Server对外提供服务，等Config Server修好，成为备的Config Server。
- 可扩展性
添加Data Server机器
- 数据读写
客户端缓存路由表，客户端可以不需要访问Config Server，直接访问对应Data Server。每次路由变更，Config Server都会将新的配置信息推给Data Server。如果客户端路由表版本过旧，会重新去Config Server获取新的。