分布式存储系统

基本概念

  • 三态:成功、失败、超时。

  • 协议类型:租约协议、复制协议、一致性协议

  • 目标

    • 可扩展性,最终目标是线性可扩展
    • 功能,最终目标是支持全功能SQL
  • RPC请求成功但超时

sequenceDiagram
Client->Server: 请求
Server->Server: 请求处理成功
Server-->Client: 网络异常
sequenceDiagram
Client->Server: 请求
Server->Server: 请求处理成功
Note left of Server: 服务器宕机
  • 一致性:强(更新后的数据都一定能被看到)、弱(能容忍更新后部分访问不到)、最终

副本是分布式存储系统容错技术的唯一手段

  • 理论核心:如何保证副本一致(,存储系统角度)

  • 全局角度

    • 顺序一致性:进程自身看执行顺序与实际一致,不在进程间按照物理时间进行全局排序。
    • 线性一致性:系统等价于是顺序执行,所有进程看到的所有操作的序列顺序都一致,并且跟实际发生顺序一致
  • 客户端角度(一般要求↓都要支持)

    • 读写一致性
    • 会话一致性:会话期间保持读写一致性
    • 单调读一致性:客户端已读取某个值,不会再读取更早的值
    • 单调写一致性:写操作按顺序完成(意味着存储系统多个副本也按客户端顺序完成)
  • 存储系统

    • 副本一致性:不一致的时间窗口?
    • 更新顺序一致性(FIFO一致性):副本间更新顺序

技术选用优劣对比

  • 性能对比程度标注

各种常用技术优劣权衡性能对比

Master-Slave

  • 通常为异步操作,同步类型的实现困难

    • 吞吐量较高、延迟较低
  • 大部分 RDBMSes

    • 例:MySQL二进制日志
  • 弱/最终一致性

    • 粒度非常重要
  • 数据存储:当前

Multi-Master Replication

  • Umbrella term for merging concurrent writes

  • 异步,最终一致性

    • 例如,使用时间戳机制的Oracle:单调递增的时间戳
    • SPOF,Master节点选举
    • 或分布式一致性协议
  • 不支持全局事务性

  • 数据存储:非强一致性

二阶段提交

  • 半分布式一致性协议

  • 组成:参与者、协助者

  • 1:提出提案(参与者在此处有资源上锁等操作)。2:投票。3:提交/废弃(只要有一个参与者拒绝提交,协助者向所有参与者发送abort)

  • 笨重,同步

  • 进阶:三阶段提交

  • 数据存储:极差的吞吐量

三阶段提交

  • 3PC以额外的一轮过程为代价换取异步性

  • Cohert-i

graph TB
qi(Query-i) --> |commit request msg <br>received,agreedmsg sent<br> to coordinator|wi(Wait-i)
qi -.-> |prepare msg received,<br>abort msg sent <br>to coordinator|ai(Abort-i)
wi --> |prepare msg received,<br>send ack msg to coordinator|pi(PreCommit-i)
wi -.-> |abort msg received<br>from coordinator|ai
pi --> |commit msg received<br>from coordinator|ci(Commit-i)
pi -.-> |abort msg received<br>from coordinator|ai
  • Coordinator
graph TB
q1(Query-1) --> |commit request msg<br>sent to all coherts|w1(Wait-1)
w1 -.-> a1(Abort-1)
w1 --> |all coherts agreed,<br>send prepare msg<br>to all coherts|p1(PreCommit-1)
p1 --> |all coherts sent ack<br>msg, sent commit msg<br>to all coherts|c1(Commit-1)
q1 -.-> |one or more coherts<br>replied abort, abort msg<br>sent to all coherts|a1
p1 -.-> a1
p1 -.-> c1
  • 预提交阶段

    • 陈浩大佬 认为其意义在于确定coordinator的可用性,因为协调者Coordinator对于事务的完成非常重要,Coordinator的可用性是个关键
    • 个人认为在这里还有个确定网络环境良好的意义在,毕竟造成Fail和Timeout的原因除了传输实体是否正常工作的外,还有网络环境的波动
  • 核心:在询问的时候并不锁定资源,除非所有人都同意了,才开始锁资源。


数据分布

哈希分布

  • 传统问题:N值发生变化

    • 一致性哈希算法(Distributed Hash Table),将服务器节点构成一个哈希环,数据存放时计算哈希值,存放到环的第一个大于或等于值的节点,算法最大特征是增删节点只影响相邻节点

    • 负载均衡问题:节点性能不一的情况下,可以调整节点在环上的位置做出非均衡比例;或者引入虚拟节点,每个虚拟节点处理能力一致(即一个能力单位),一个处理能力强的物理节点可以拥有多个虚拟节点,在此基础上可以实现将需要迁移的数据分散到整个集群的操作(调整虚拟节点/能力单位)

  • 散列特性

graph LR
B(散列特性) --> C{散列键值}
C -->|用户id| D(数据倾斜)
C -->|主键| E(同用户数据被分散到多台服务器)
D --> F(好的散列函数困难)
E --> F
D --> G(大用户)
G --> H(自动拆分)
G --> I(手动拆分)

顺序分布

  • 将大表划分为连续的范围,得到子表,B+树形式组织,B+树节点即子表的合并操作

复制与故障

  • 主副本(primary)、备副本(Backup)
graph LR
O(主备复制协议) --> A(基于主副本的复制协议)
A --> B(强同步复制)
A --> C(异步复制)
O --> D(基于多个存储节点的复制协议)
  • 故障检测:租约机制,带超时机制的一种授权
  • 分布式存储系统结果:单/双层结构

可扩展性

  • 总控节点的瓶颈问题?=>P2P架构更有优势?

    • 目前主流的分布式系统大多带有总控节点
  • 数据库水平扩展:分库分表

  • 系统

    • 同构系统:主备节点,存储节点分为若干组,同个组内节点服务完全相同的数据,增加副本时需要迁移的数据量太大,不利于自动化,不适合大规模分布式存储系统
    • 异构系统:数据划分为大小接近的分片,每个分片的副本可以分布在集群内的任意一个存储节点,发生故障将由整个集群来恢复,而不是某几个固定的存储节点
  • 两阶段提交协议(2PC协议)

    • 阻塞协议,执行过程中需要锁住其他更新,大部分分布式存储系统不适用
    • 本质:分布式原子操作
    • 组成:协调者、参与者(workers、coherts、participant)
    • 过程:请求阶段(Prepare)、提交阶段(Commit)
  • Paxos协议

    • 前提:在非拜占庭模型条件下
    • 有单Paxos和多Paxos,多Paxos大多数单Paxos的重复协调操作
    • 过程:- 准备(prepare)/预提案、批准(accept)/提案、确认(acknowledge)/接受提案
      • 本质:一个倡议被接受后很快会被通知到其他的proposer,扩散式提交从而更多的acceptor同意
      • 正确性(只接受一个)、可终止性(最后一定有协议被接受)
      • 相关实现要点问题:倡议编号全局唯一且递增增长,proposer或者acceptor崩溃
      • 用法:全局锁或命名配置服务、数据复制到多个数据中心
      • 待问:同时担当多个角色?
graph LR
A[proposer] -->|提案编号n| B[acceptor]
B --> C{n值}
C -->|n大于已回复编号| D(回复接受过提案最大编号)
C -->|n值小| F(不回复)
D --> A
D --> E(不再回复小于n提案)
graph LR
A(预提案回复集不为空) --> B(选择最大序号)
C(预提案回复集不为空) --> D(生成新序号)
D --> DD(自定义提案值)
B --> E[acceptor]
DD --> E
E --> F{n值}
F -->|小于响应过的| G(不接受)
F -->|大于响应过的| H(接受)
graph LR
O[proposer] --> A(超过一半acceptor接受)
A --> B(提议值生效)
B --> C(acknowledge)
C --> D[acceptor]
  • 2PC与Paxos的结合:2PC保证分布式原子性问题(如Paxos的全局递增变量),Paxos解决一致性(2PC的协调者宕机)

文件系统

Google File System系统架构

  • 性质:底层支撑文件系统,扩展性高,支撑上层复杂的文件系统架构,本质上是***弱一致性***
graph LR
A(GFS分布式文件系统) --> B(Bigtable表格型数据)
B --> C(Megastore)
C --> D(Spanner关系型数据)
  • 角色:GFS Master(主控服务器)、GFS ChunkServer(CS,数据块服务器)、GFS客户端(一组接口,不遵循POSIX标准,库文件形式,不缓存文件数据
graph LR
A(GFS主控服务器) -->|chunk句柄,chunk位置| B(GFS客户端)
B -->|文件名,chunk索引| A
B -->|chunk句柄,字节范围| C(GFS数据块服务器)
C -->|chunk数据| B
A -->|控制消息| C
C -->|控制消息| A

控制流和数据流分离,SDN的一种经典表现

  • 应用:Google Bigtable、MapReduce

  • 一致性模型:追加模型而非修改模型,追加模型更新没有落地到每一个副本上读到的只是过时数据,而修改则可能读到错误数据

  • GFS追加流程(核心):数据流水线(减少时延)、分离数据流与控制流(优化数据传输,将数据流优先传达网络拓扑上最近的节点上,避免副本节点间跨机架、跨机房之类的消耗

  • 负载均衡

    • chunk副本创建位置
      • 磁盘利用率较低的节点
      • 限制时间范围内创建的数量(重要,因为不加以限制,新的chunkserver上线时由于磁盘利用率低很可能被创建请求压垮)
      • 所有副本不能同在一个机架
    • 主控Master会定期扫描挡墙副本的分布情况,分布不均会重新执行负载均衡
graph LR
A(主控服务器) -->|1,控制| B(客户端)
B -->|2,控制| A
B -->|3,数据| C(备A)
C -->|3,数据| D(主副本)
D -->|3,数据| E(备B)
B -->|4,控制| D
D -->|5,控制| C
D -->|5,控制| E
C -->|6,控制| D
E -->|6,控制| D
  • 延续/下一代:Colossus
    • 实时性
    • 海量小文件

Taobao File System对比GFS

  • NameServer有一主一备,GFS只有一个Master

  • 读写比较高,没有针对写操作的优化,每次写操作都要请求NameServer(即GFS的主控);而GFS有租约机制,将写权限下放到ChunkServer,客户端请求一次获得ChunkServer相关信息后会缓存起来,后面读写该chunk都不会重复请求Master

  • 没有分离数据流与控制流

  • NameServer不需要维护目录树,也不需要维持文件与Block结构的映射关系

Blob文件系统

  • 特征:较大,文件间没什么联系,基本只读(如图片存储)

内容分发网络

  • 分布式缓存系统比分布式存储系统构建容易,因为缓存故障节点可以直接踢掉

架构

  • CDN(Content Distribution Network)
  • P2P(Peer-to-Peer)

CDN

  • CDN通过将网络内容分发到靠近用户的边缘节点,使得不同地域用户访问时能就近获取内容,不需要通过多个路由器中转
    • 边缘节点:与用户"一跳之遥"(Single Hop)的节点

Written with StackEdit.