rainyzz's blog

分布式存储概要

单机存储模型

内存中的结构

Map
HashMap
SkipList,和红黑树性能数量级一致,但是不需要调整树结构,锁使用较少

Direct-Access (Hash Engine)

全内存索引,内存中存储了key和对应的offset

  1. 读取时随机读
  2. 写入append到最后,提升写性能,读写一次io
  3. 更新时也是追加写,旧数据标志为无效
  4. 定时回收无用区块
    限制:
  5. 内存容量,需要压缩。
  6. Hash桶利用率 (Cuckoo Hash)

B+树

每次io都能读取一个B+树节点
读写一个节点需要使用log n次IO操作

LSM-Tree

  1. 随机写转换为顺序写,写入数据时先写入内存,内存buffer写满后排序形成小patch文件,不同patch是有时间序的
  2. 当读取时,从最新的patch读取,每个patch也存了当前patch的最大key和最小key,然后找到包含对应的patch,然后二分查找,然后读取到各个patch后依次应用,生成最后的结果,可以用bloomfilter来减少patch的读取
  3. 写操作的话都是不停的写日志
  4. patch也会不断合并,minor patch放在SSD,major patch读取也只是寻道时间10ms

单机存储模型设计原则

空间换时间

Cache, Buffer, Index, LSM, SkipList

时间换空间

压缩, EC(EraseCode)
8分片->12分片
N+K分片,最多可以丢K个分片都能恢复

读延迟换写延迟

LSM

写延迟换读延迟

Index, Tree…

读写吞吐量,读写延时
硬盘读性能每秒100次,ssd每秒6w次读以上
SAS_SATA SSD (10)110us 1.5GBs 16TB_disk, 200K IOPS
SAS_SATA HDD (10)10ms 1.5GBs 10TB_disk, 200 IOPS

数据划分

哈希划分

实现简单,不宜扩展

范围划分

全局有序,常见时间分区

一致性哈希

均衡好,实现复杂

虚拟节点

每个物理机有多个虚拟节点,扩展时移动虚拟节点即可
key->bucket, bucket->DataNode
扩展时只需要移动bucket和DataNode的关系

metadata

  • 轻量级master
    元信息较少,状态可恢复
  • 主从master
    元信息较多,需保证master的可靠性
  • 去中心化master
    DHT,Gossip,Dynamo,Cassandra
  • 无状态master
    元信息存zookeeper,Table中

Replication

流水线(Pipeline)

写入primary,写入slave1,写入slave2,所有slave写完成后返回给master ack,然后再返回给用户
所有节点入度出度都是1,减少网络压力
当遭遇慢节点时比较难处理

Dispatch

client向master询问slave节点位置
client 同时向slave写
规避慢节点:同时写四个节点,去掉慢节点
单master压力较大
写延迟需要比较低,不在乎网络流量使用

星形

client写master
master同时向slave同时写

基于共享存储

master写log,slave1和slave2读取log同步

一致性

一主多从:只读主副本保证一致性

对等副本:W+R>N 保证会话一致性
提高可靠性:增加副本数,提高副本修复速度

强一致性:

只要写成功了就一定能读到
只要能读到就一直能读到

一致性协议:

磁盘不稳定,网络划分,机器假死,时钟不准,进程运行,网络速度可快可慢

election

fencing

机器假死又复活,重新选了新的主,原来的主又复活,变成了双主,或者两个客户端同时写
数据存储层面应该防止这种情况

log replication/ compaction

数据可靠性
数据一致性

membership change

Raft
Zookeeper
Chubby

架构设计范式

Master-Node

Primary Master, Slave Master, Client直接向node写

共享协调系统

Zookeeper

无中心架构

一致性hash,Dynamo

分层架构

(HBase, BigTable)数据存储依赖于第三方分布式存储,对上层来说不需要关注数据的可靠性和一致性

性能

吞吐,延迟
读性能?写性能?元信息操作?
网络不好,跨机房,集群整体繁忙,限速

CAP

CP:主从模式,主挂了或者主分割了就不可用了
CA:对等副本,可能会数据不一致

分布式系统分类

KV,对象,表格,文件系统