分布式键值系统

Amazon Dynamo

  • 整体还是采用了无中心节点的P2P设计,一致性较差,只保证最终一致性,影响测试用例的设计
    • P2P技术:向量时钟(Vector Lock)、数据回传、Merkle树、冲突处理等
  • 开源实现:Cassandra
  • 问题及对应方案
graph LR
A(数据分布) --> B(改进的一致性哈希/虚拟节点/)
C(复制协议) --> D(复制写协议,NWR参数可调)
E(临时故障处理) --> F(数据回传机制Hinted Handoff)
G(永久故障恢复) --> H(Merkle哈希树)
I(成员资格及错误检测) --> J(基于Gossip的相关协议)
  • 每个节点需要维护一定的集群信息(带有P2P架构的部分含义)

  • 新节点刚进入时可与种子节点交换信息,对集群产生基本的认识。节点间定期通过Gossip协议交换更新集群信息

  • Dynamo设计支持可插拔引擎(默认Berkeley DB,还支持MySQL InnoDB)

NWR模型

  • N是复制的备份数,W是写成功的备份数,R是读成功的备份数,W+R>N则至少有一份最新数据(可以手动调节wr来调整读写比重)

  • 结合向量钟,建立版本号,低版本号不允许更新的特性类似乐观锁

  • 版本冲突的硬伤:最新版正确的分布式节点上的数据在没有完全扩散开的情况下,旧版本的节点无权拒绝写请求,就会出现v(a1,b2) VS v(a1,c2)这样的写冲突,Dynamo的选择是交给调用方自己去做版本冲突处理(……)

  • 论文:译文Dynamo:Amazon的高可用性的键-值存储系统

容错

  • 数据回传

  • Merkle树同步

    • 每个非叶子节点对应多个文件,为其所有子节点组合后的哈希值,叶子节点为单个数据文件,为内容的哈希值,因此任何一个文件的不匹配都将导致从叶子节点到根节点的不匹配
    • 每个机器维护一课Merkle树,机器同步时先传输树,只需要传播从根到叶子节点均不同的文件
  • 读取修复

Tair

  • 迁移中的数据收到修改操作会记录修改日志,迁移完成后对新迁移部分应用日志

分布式表格系统

Google Bigtable

  • 组成:客户端程序、主控服务器、子表服务器(Tablet Server)

  • 本质:构建在GFS上的一层***分布式索引***,解决了遗留的一致性问题

  • 保证***强一致性***,可扩展性极强

  • Bigtable数据结构

graph LR
A(Chubby文件) --> B[根表/一级元数据表...]
B --> C[元数据表...]
C --> D[用户表]
  • 子表的分裂与合并:分裂较容易,直接修改索引、元数据就行,合并操作由Master发起,首先要将子表迁到同一个Tablet Server上(可否由Master发起转移独占锁请求?还是只有故障了才有换的可能?

  • Compacation:Minor、Merging、Major,Minor转储MemTable,后两者合并SSTable

Chubby

  • 依赖Chubby提供分布式锁服务,如果Chubby发生故障,Bigtable系统整体不可用
  • 经典部署:两地、三数据中心、五副本

  • Tablet Server启动需要获取互斥锁(同一张子表同一时间只能有一个Tablet Server处理),故障时Master会先试图获取互斥锁,获得失败说明Chubby服务出现问题,否则则是Tablet Server出现问题

  • Master启动也需要获取独占锁,获取锁后若Master故障,超时自动释放,管理程序指定其他Master

Google Megastore

  • 介于关系型数据库与NoSQL之间

  • 组成:客户端库、复制服务器、协调者

  • 实体组(Entity Group):同一个实体组的操作是原子的,是序列化的,内部支持ACID特性,组间维持类似NoSQL的弱一致性,该定义方式规避了影响性能和可扩展性的Join操作

    • 单集群实体组:分布式队列提供最终一致性,跨实体组操作有专门线程扫描发送,若要强一致性,只能2PC加锁
    • 对同一个实体组的多个事务被串行化

分布式数据库

数据库中间层

  • 为了扩展关系数据库,最简单直接的做法就是按照应用层将数据分片,分到多个数据库节点,引入中间层屏蔽逻辑

  • MySQL Sharding架构

    • dbproxy:解析MySQL协议,执行MySQL路由,SQL过滤,读写分离,结果归并,排序分组
    • LVS:Linux Virtual Server
graph TD
A(应用端) -->|MySQL客户端库读取| B(负载均衡LVS)
B -->|路由| C(中间层dbproxy集群)
C -->|返回结果| B
C --> D(ZooKeeper集群)
C -->|读/写| E(数据库组)
D --> F(常驻进程)
E --> F

Microsoft SQL Azure

  • 数据分区(Partition)、主副本(Primary)、备副本(Secondary)

  • 三个副本至少两个写成功才可以返回客户端成功

  • 事务T的主副本分区将操作日志发给备副本(事务T回滚,主副本会发送一个ABORT;提交主副本会发送一个COMMIT,并带上序号),备副本应用日志到本地数据库,成功则回复ACK给主副本

  • 故障恢复后备副本往主副本发送本地已提交最后一个事务的提交顺序号,两者差别较小则准备重放日志,否则主副本先传送数据库快照,再把快照后的日志发送过去

数据库

Google Spanner

  • 全球级分布式数据库,扩展性极强,通过同步复制多版本管理支持跨数据中心分布式事务

  • 构建基础: Colossus

架构

  • Universe:一个 Spanner 部署实例(目前全世界测试线上、开发各一个),支持多数据中心部署

  • Zones:每个Zone属于一个数据中心,一个数据中心可以有多个zone

组件

  • Universe Master

  • Placement Driver:跨zone数据迁移

  • Zone

    • Zonemaster
    • Location Proxy:提供目录映射Spanserver信息
    • Spanserver:实际提供存储服务,相当于Tablet Server
      • 子表(主副本,多个副本)
        • 目录
      • Paxos状态机
      • 锁表(主副本所在Spanserver,Paxos组内单机事务)
      • 事务管理器(主副本所在Spanserver,跨Paxos组协调)

复制、一致性、并发控制

  • TrueTime机制:GPS、原子钟

  • 事务:读写事务、只读事务(保证不会读到不完整的事务)、快照读(客户端提供时间戳)、快照读(客户端提时间范围)

  • 延时提交(考虑TrueTime误差+e/-e,核心在于保证只要事务A的提交早于B的开始,A时间戳版本号必然小于B,代价是事务提交至少延时2e)

graph TD
X(A事务开始) --> Y(B时间戳误差-e)
Y --> Z(A时间戳误差+e)
X --> |e| Z
Z --> O(B事务开始)
O --> P(A可以提交)
Y --> |e|O
P --> Q(B可以提交)
Z --> |e|P
O --> |e|Q

OceanBase

  • 将更新操作限制在一台服务器上:牺牲一定的可用性换取强一致性,实现跨行跨表事务容易,无需2PC(本质单点)

  • 容忍故障点:主机,备机,主备机之间的网络

    • 异步模式:异地容灾
  • 操作本质:基线数据存储于多台基线数据服务器中,每次读操作都需要把基线数据和增量数据融合(此处有多路归并,概念上类似LSM,沉淀为SSTable)后返回给客户端。

  • 瓶颈解决:更新服务器上的修改增量能够定期分发到多台基线数据服务器中

  • 优势:数据不易损坏,因为不是直接修改,牺牲一定一致性(读到老数据)

  • 基线数据

graph LR
A(活跃MemTable) -- 达到一定量 <br/> 冻结 --> B(冻结MemTable)
B --> | 转储 |C(SSTable磁盘持久化)
A --> | 开启新内存表 |A
Q>一棵内存中的B+树] --> A
  • MemTable B树结构(哈希索引,B树索引)
graph TD
A((root)) --> B((index1))
A((root)) --> C((index2...))
B --> D[rowkey1]
B --> E[rowkey2]
C --> F[rowkey3]
C --> G[rowkey4...]
D --> H(cell操作)
H --> I(cell操作)
I --> K(cell操作)
E --> J(cell操作)
J --> L(cell操作)
F --> M(cell操作)
G --> N(cell操作)
M --> O(cell操作)
  • ChunkServer中所有SSTable都是常驻内存的,不同缓存的底层采用相同的实现方式
  • 惊群效应
    • 多个线程读取同一个数据,发现不在缓存中,都执行将其加入缓存的操作,浪费资源
    • 解决算法:
if(不在缓存中) {
    往缓存中加入一个标记fake
    从SSTab中读取数据行
    将读到的行加入缓存中,清楚fake标记,唤醒等待线程
    返回数据
} else if(行存在) {
    if(fake == true) {
        等待直到fake标记消除
        if(等待成功) 返回行缓存中的数据
        else 返回读取超时
    } else {
        读取行数据
    }
}
  • RootServer升级时可以给 UpdateServer 发一个超长的租约

  • 支持磁盘IO与CPU计算并行化


Written with StackEdit.