分布式存储_存储技术分布式存储

一、分布式存储架构

1.1 集中式元数据架构（2000s）

1.2 去中心化架构（2010s）

1.3 集中式vs分布式

1.4 新的架构？

二、典型架构-HDFS

2.1 系统设计目标和原则

2.2 基本架构

2.3 数据副本

2.4 健壮性

2.5 演进与考虑

三、典型架构-Ceph

3.1 目标和理念

3.3 动态分布式的元数据管理

3.3.1 基本概念

3.3.2 动态子树划分

3.3.3 访问控制

3.4 分布式数据存储机制

3.4.1 基于CRUSH的数据分发

3.4.2 故障上报

3.5 演进和思考

四、高并发架构

4.1 并发模型

4.2 面向TCP连接的公平性问题、流控问题

4.3 数据修复与QoS

一、分布式存储架构

1.1 集中式元数据架构（2000s）

Google在2003年发表了GFS的文章，开启了软件定义存储的时代，其核心思想是基于通用服务器提供规模存储能力。在GFS中，需通过集中设置的元数据管理节点获得数据位置和索引信息。

优点：1）因为元数据集中存储，方便操作 2）扩容的时候，不需要数据迁移 3）因为元数据集中管理，所以根据节点存储情况进行负载均衡，提高空间利用率 4）非常容易扩展管理功能

缺点：1）因为元数据放在内存中，因为内存容量受限，所以导致元数据存储的空闲有限，导致系统的规模受限，一般是10亿级别的文件规模  2）需要解决高可用

1.2 去中心化架构（2010s）

出现了一些开源的去中心化架构，例如GlusterFS、Ceph、Swift等。其核心思想，是根据计算的方式确定存储的位置，来实现去中心化，例如通过HASH来存取文件。

但其存在挑战：系统扩容、磁盘损坏时，磁盘数量有变时，很多文件数据的hash值有所变化，那么需要大量数据需要迁移。

MIT在1993年提出了一致性算法，把迁移数量减少到理论最优值。在实际应用做了简化，主要思想如下：引入虚拟节点概念 ，数据落盘过程：hash取值后，存储到虚拟节点，然后虚拟节点分配到物理节点。当系统扩容、磁盘损坏时，通过虚拟节点来迁移数据，虚拟节点可以控制迁移数据量。

优点：消除了元数据集中的性能瓶颈；文件数量基本不受限制；读写性能更高，流程更简化

缺点：

1）扩容时需要迁移数据；

2）目录操作性能较低，例如list操作；

3）磁盘空间利用率不均衡，如果文件数量足够多、大小均衡，那么hash存储的结果还好，但是通常不是这么理想；

4）管理困难，例如删除1年前、x点前的文件数据，集中元数据架构下比较方便

1.3 集中式vs分布式

1.4 新的架构？

是否可以兼得，用Nosql管理名字空间和元数据，文件以对象方式存储。即分布式数据库管理元数据，用分布式对象存储文件数据。

二、典型架构-HDFS

HDFS作为GFS的开源实现，其构建在通用服务器硬件之上。HDFS提供了对文件数据的流式访问。（说明：参考Hadoop 1.2.1 Documentation-HDFS Architecture）

2.1 系统设计目标和原则

1、构建快速的故障诊断发现和自动恢复措施，避免底层硬件损耗频率高带来的数据丢失和业务中断。

2、高吞吐的流式数据访问。HDFS主要面向批处理模式，而不是和用户交互式。强调数据的高带宽，而不是数据访问的低时延。

3、满足大数据量需求。典型场景下，文件大小GB到TB级别不等，文件数量达到百万级别。

4、简单一致性。HDFS采用一次写多次读的模式，即文件写入后，文件只能写或删除而无法修改。

5、迁移计算能力比数据更节省。HDFS提供接口用于应用将计算处理移动到靠近数据存储的位置，以节约网络带宽，提升系统整体吞吐。

6、通用型。可以适配不同软硬件，可以十分方便的移植。

2.2 基本架构

1、采用Master/Slave架构，单个HDFS集群中有一个Master节点+多个Slave节点。Master节点又可称为NameNode，该节点负责管理文件系统的命名空间（NameSpace）、响应客户端（Client）对文件的访问（例如文件/目录的开关、重命名等）；Slave节点又可称为DataNode，负责管理本节点的存储。

2、每个文件被分成块Block进行存储，Block以副本形式存储在不同DataNode中

4、DataNode定期向NameNode发送心跳，以便NameNode掌握DataNode的运行状态；同时NameNode也向DataNode发送文件数据块的创建、复制、删除等控制指令。

2.3 数据副本

1、每个文件被分成连续的块Block进行存储，每个块除了最后一个块以外大小都是相同的。针对数据块会设置多个副本，以保障容错和可靠性。块的大小和副本数量是可以在系统的配置文件中进行修改的。

2、副本的放置。HDFS中副本放置是通过Rack来区分放置的，一个比较简单的策略是所有副本都放置在不同的机架上，这样可以十分方便的做负载均衡，有效防止故障导致的数据丢失。但是这种方式会会给写方式带来更多开销，因为需要跨rack进行副本数据同步。通常的策略是，设置三副本，其中2个副本在一个rack上，另外一个在不同rack上。

3、副本的选择。为了降低整体的带宽消耗，HDFS会让距离“读者”最近的数据副本满足访问需求。例如和读者同节点Node、同rack。

4、副本一致性。当客户端有新的数据或数据被更新时，副本全部更新后才会返回给客户端。这样一致性比较强，读取时副本都是最新的。但是写延迟比较高，降低了吞吐量。

2.4 健壮性

1、心跳机制：避免Node出现故障。DataNode周期性向NameNode发送心跳信息，如果超时，则NameNode会认定该节点死亡或失效，将不会对该节点进行数据读写，同时对该节点上的数据副本进行重新调度。

2、元数据故障：避免元数据出现丢失或失效。对元数据进行多副本设置，保持同步，并且可以及时恢复。

3、快照。可以定制对HDFS进行快照，便于整体性恢复。

2.5 演进与考虑

1、高可用。为了避免NameNode单点故障，也出现了很多技术，例如将NameNode水平扩展，之间相互独立，管理自己的Block Pool；还有将元数据采用hash算法分布式进行存储。

2、负载均衡。

3、数据一致性。多个数据副本之间如何保证高效同步，同步的效率和准确性一致性两者如何平衡。在模型上，除了经典的ACID还有BASE（Basically Available、Soft-state、Eventually Consistency）。

三、典型架构-Ceph

Ceph作为经典的去中心化分布式存储，在2006年的OSDI上提出。本章节内容主要参考《Ceph: A Scalable, High-Performance Dsitributed File System》和http://docs.ceph.org.cn/。

3.1 目标和理念

传统文件系统例如NFS中，文件具有分明的层次结果，传统存储采用Client/Server模式，扩展性较差，故提出了分布式文件系统Ceph，用来提供出色的性能和可靠性，同时具备unparalled scalability。基于如下理念：

1）大规模系统是逐步扩张的

2）节点失效较为常见

3）负载随时有所变化

系统设计目标：

1）扩展性。包括多个维度，存储容量、吞吐

2）高性能。包括单个客户端、目录访问、文件访问，可满足成百上千个主机同时读写的极端情况。

3）动态自适应。可以随着上层应用和数据的不同动态适配。

3.2 基本架构

1、Ceph的基本架构如下。包含三个重要组成：

1）客户端。暴露一个接近POSIX的文件系统接口

2）OSD集群，其上存储了所有数据和元数据

3）元数据集群，其管理命名空间和一致性、安全等。

2、三大机制

1）数据和元数据的分离。对于元数据的操作（打开、重命名等）由元数据集群响应，在云数据操作同时，客户端可以同步通过与OSD交互进行文件的I/O读写。这是因为数据文件被分割为可预知的命名对象，使用CRUSH算法保存在存储设备上，不必获得维护和获取数据块列表，任意方可以独立计算数据对象的名称和存储位置。

2）动态分布式的元数据管理。在文件系统中，元数据的操作占到了一半至多。Ceph基于动态子树分割（Dynamic Subtree Partitioning）来将文件系统目录结构分散到MDS（MetaData Server）即元数据集群中。

3）可靠的自动化分布式对象存储。在考虑系统不断增长、节点经常失效、数据经常操作的情况下，保证数据的持久分发。Ceph使用了数据迁移、数据副本、故障发现和恢复等机制。

3.3 动态分布式的元数据管理

3.3.1 基本概念

文件和目录的元数据在Ceph中容量比较小，包含整个文件目录和inodes（80个bytes）。和传统文件系统不同，不需要文件的分配元数据（即文件分为了多少个数据块），数据对象的名字是基于inode来生成，通过CRUSH分发到OSD上。

OSD是Ceph中对象存储守护进程，一个ODS对应一个真实的硬盘。

在每个MDS上保存Journals，每个Journal大小为几百MB，一般保存在内存中，满足高速访问需求。MDS会及时更新Journal，同时将历史旧数据写入持久存储中。元数据主要依靠两个机制实现高可靠、高性能的访问，即动态子树划分和控制访问。

在访问的时候，MDS会提供给客户端自身目录，以及自身目录的ancestor即父目录的MDS信息。

3.3.2 动态子树划分

通过动态子树划分将目录分布到不同节点上，其中热点目录会保存在多个节点上，如下图所示，对于中间和靠右的热点分支目录，保存在多个MDS上。

1、交换MDS的负载信息。MDSs中的各个MDS会定期向其他MDS广播心跳以查看集群的状态同时发送自身的负载信息。元数据负责数据包括，inode读写次数和存取次数。MDS在统计自身MDS负载时，首先统计其管理的目录子树的元数据负载，并结合元数据请求频率和待处理的元数据请求数量进行加权计算

2、决定迁移的对象/角色：MDS收到全部MDS的心跳包后，首先计算出当前MDSs的负载平均值，然后将该值与自己的MDS负载进行比较。如果自己的大于平均值，则MDS自身作为迁出者，把一部分负载迁移到其它负载相对低的MDS；如果自身MDS负载小于平均值，则MDS本身作为迁入者等待负责相对较高的MDS迁入。

3、选择目标迁移目录。确定好迁移角色后，作为迁出者的MDS，根据自身MDS负责与集群负责平均值的差值选择相应负载的目录子树进行迁移。基本原则如下：从负载与差值接近的目录子树开始选择，以减少目标迁移目录的数目，同时尽可能保存完整的目录子树结构。

4、目录迁移。由于存在可能一个迁出者同时向多个迁入者迁移元数据的场景，为了保证元数据迁移中的强一致性，ceph采用两阶段提交方式：迁出者MDS首先将迁移目录上锁并通知迁入者MDS使其加载目标目录子树的inode到其元数据缓存中，然后迁出者MDS依次迁移目标目录子树的边界和元数据信息到迁入者MDS，最后迁出者解锁目标目录子树，并将其包含的文件和子目录的元数据信息从迁出者的元数据缓存中清楚并追加到日志文件中，同事通知迁入者MDS结束元数据迁移操作。

3.3.3 访问控制

虽然将目录均衡分散到MDSs中，但是并不能较好处理热点访问或突发集中访问。Ceph会根据元数据的热度情况，对元数据在多个节点上进行hash缓存。

3.4 分布式数据存储机制

Ceph可靠自动化分布式对象存储（RADOS，Reliable Autonomic Distributed Object Store）机制用来在管理、集群扩展、失效时，达到容量和性能上的线性增长。

采取的策略是：将新数据随机分发，将旧数据随机迁移到新设备的策略。在该策略下，可以在不同负载下十分健壮。

文件被拆分为数据块，然后基于一个简单Hash算法将数据块映射到PG（palcement groups），该算法通过可调节位数的掩码来控制PG数量。然后基于CRUSH（Controlled Replication Under Scaleble Hashing）算法，按照一定放置规则，将PGs分配到OSDs上。

一个Pool包含多个PG，一个对象只能属于一个PG，一个OSD上可以分布多个PG。

3.4.1 基于CRUSH的数据分发

CRUSH算法的输入为：pgid、cluster map（集群结构）、Placement Rule（放置规则），处理过程为hash过程，输出为：集群中用于存放相应PG的OSDs即OSD列表。

1、Cluser Map

一般构建数据中心-机架-主机-磁盘这样的树状层级关系，叶子节点最小为物理存储设备例如硬盘，为device，所有中间节点成为bucket。bucket和device之间也可以有分层分级；集群入口为root。

常见节点类型：root-->region(可用域)-->data center（数据中心，包含多个机房）-->room（机房）-->pod（一个大机房中的单间）-->pdu（为机柜分配的电源插座）-->row（包含若干主机的一排机柜）-->rack（包含若干主机的机架/机柜）-->chassis-->host-->OSD(Device对应的守护进程)。

可以根据实际情况进行层级设定和调整。

2、hash过程

在CRUSH中定义了四种不同的方法，分别为Uniform、list、tree和straw。

uniform：所有节点权重相同，通过hash（数据块key，bucket.id）得到哈希，基于该哈希通过取模得到选取子节点索引值。该hash过程，由于子节点的数量增加或减少导致模数变化，数据会重新分布。

list：适合规模较小且相对稳定的bucket。将其子节点按照时间顺序构成链表结构，对于数据块key，从头扫描，将该数据块分配到当前节点的概率与当前节点的权重占还未被扫描子节点的权重值之和的比值成正比。

tree：适用于规模较大且相对稳定。带权重的二叉树，根据当前节点的左右子节点的权重比决定分配左右子树的概率，直到遇到叶子节点为止。

straw：适合节点增加或减少较为频繁。为每个子节点预先根据其权重分配一个straw值，成正比。对bucket中每个子节点进行遍历，hash获得数据块kay和子节点id的哈希值，然后乘以straw值，选择乘积最大的节点。

3、放置规则

放置规则涉及：副本数量、备份方式等。

take（起点）-->select(type，n)，其中type是备份方式，例如为rack，那么选择不同rack存放n个副本。-->emt()，输出OSD列表。

3.4.2 数据安全性

通过CRUSH将多个PGs分配到相应OSDs之后。

write：首先对数据的主OSD进行写，然后由主OSD对副本OSDs进行写。只有备份副本和主副本都写成功后，才会最后生效。

3.4.2 故障上报

1、OSD对自身磁盘或数据故障进行上报

2、每个OSD都会监控属于同一个PG中的其他OSD，周期性心跳机制。分为两种情况，一种OSD节点无响应即无法reachable，将会认为该节点down掉了，对于该OSD作为主数据节点的地位需要转换到其他副本OSD上，并进行数据迁移；如果长时间无反应，那么该节点out。

3.5 演进和思考

随着Ceph的进一步成熟，已经从文件存储，扩展到块存储和对象存储。其基本架构如下所示。

针对Ceph的改进和研究工作，也在不断进行。随便去知网搜索一下就有很多。

1、元数据是否可靠和高效。虽然ceph中组成了元数据集群，但为了性能吞吐，还可以进行改进，例如缓存预取机制；元数据调整时，更好的负载均衡和迁移机制等。

2、数据的布局是否均衡。这回对磁盘造成不同负载，进而影响系统吞吐。当前由很多针对CRUSH算法的改进。

四、高并发架构

说明：本章节内容根据上海交通大学李小勇老师视频整理。

4.1 并发模型

计算机高并发模型主要有两种：1）线程池模型  2）事件驱动模型。两个技术长达20多年的争论。

可以参考论文why threads are a bad idea、why events are a bad idea。

Golang: 基于协议coroutine的高并发；Node.js：基于异步io的事件驱动模型的高并发。

进程池+事件驱动模型，各取所长。每个CPU启动一个进程；每个进程内部使用事件驱动模型；分配独立的进程负责执行时间长、调用同步API接口的任务。

4.2 面向TCP连接的公平性问题、流控问题

高并发服务需要对数万甚至数十万个TCP连接服务，保证公平性对用户体验非常重要。

问题1：select（）/epoll()反馈的socket fd从小到大排序，导致socket fd小的tcp连接总是优先得到服务

问题2：通常socket的触发模式为水平触发（level-triggered）,当socket有数据到达时，必须把所有的数据一次性接收完毕。如果有一个tcp非常快，数据量大，那么会长期占用。

想法和思路：

1、Epoll中使用edge-triggered模式

2、将待处理的socket放入FIFO队列

3、从FIFO队列头部取出socket，每个处理一个请求，然后把socket放入FIFO队列尾部

这样可以保证TCP连接之间的公平性，避免单个TCP占用过多资源，在重负载时更稳定

4.3 数据修复与QoS

磁盘在存储过程中有高速运动，所以存在一些机械故障。数据修复是存储系统设计需要考虑的核心问题之一。

主要的磁盘修复策略：1）插入新盘后，在新盘上修复数据 2）将故障磁盘的数据分散到其它磁盘进行修复。可以看到采用后一个策略，修复速度会相对快一些，并发写。

磁盘修复速度的权衡：1）修复速度快。可以降低数据丢失风险，但是却会占用网络和磁盘io带宽，对业务系统有冲击，严重时会导致业务中断 2）修复速度慢：数据丢失风险高。