《大规模分布式存储系统》读书摘记(持续更新)

时间:2022-02-08 23:58:19
3 分布式系统
3.5 容错
故障检测:
  • 心跳协议
  • 当机器发生故障时,需要将上面的服务迁移到其他服务器上,为了保证强一致性,需要确保故障机器不再提供服务;
  • 主要问题:正常机器和故障机器之间需要对“故障机器是否应该被认为发生故障而停止服务”达成一致。异步网络中多态机器无法达成一致。
  • 租约:带有超时时间的一种授权。考虑一个提前量。P51
故障恢复:
  • 分布式存储系统分为:单层结构和双层结构。一般都为单层,每个数据分片维护多个副本;Bigtable为双层,存储和服务分开,服务层只有一个副本。
  • 单层结构系统维护多个副本,贮备副本之间通过操作日志同步。
  • 两层结构系统将所有数据持久化写入底层的共享分布式文件系统,每个数据分片同一时刻只有一个提供服务的节点。
  • 故障检测和故障恢复过程中,不能提供写服务和强一致性读服务。故障检测事件较长,一般为几秒到十几秒,故障恢复时间较短,两层结构故障恢复只是将数据索引加载到内存中,而不是数据。
  • 为了实现高可用性,总控节点也需要一个备机。
 
3.6 可扩展性
总控节点:
  • 一般分布式系统中总控节点只需维护数据分片的位置信息,并执行调度,分布式文件系统中还需要维护文件系统目录树,所以内存容量可能会优先成为瓶颈。
  • 如果总控节点成为瓶颈,可以采用两级结构。在总控机与工作机之间增加一层,虽然看似增加了一次网络请求,但是客户端总是能够缓存总控机上的元数据,因此并不会带来额外的开销。
数据库扩容:
  • 假设数据库中有3张表格,首先根据业务将三张表格垂直拆分到不同的DB中,再将每张表通过哈希的方式水平拆分到不同的存储节点。每个拆分后的DB通过主从复制维护多个副本,且允许分布到多个数据中心。
  • 通常采用双倍扩容,将每个分片拆分为两个分片。
异构系统:
  • 同构系统:将存储节点分为若干组,每组内的节点服务相同的数据,一个节点为主节点,其余为从节点。这样的系统的问题在于增加副本时要迁移的数据量非常大,时间长,在迁移的过程中很有可能存储节点再次发生故障。所以这样的节点很难做到自动化。
  • 异构系统:每个分片的副本可以分布到集群中的任何一个存储节点。发生故障时,原有的服务有整个集群的存储节点来恢复。由于整个集群参与恢复数据,故恢复时间短,集群越大,效果越明显。
 
3.7 分布式协议
两阶段提交协议(2PC):
  • 保证跨多个节点操作的原子性,实现分布式事务
  • 两类节点:协调者(一个),事物参与者(多个)
  • 两个阶段:①请求提交。协调者通知参与者准备提交或者取消事务,然后进入表决过程。在表决阶段,参与者将告知协调者自己的决策(同意或取消)。②当且仅当所有参与者同意提交事务,协调者才通知所有的参与者提交事务,否则通知取消事务。
  • 两阶段提交协议是阻塞协议,执行过程中需要锁住其他更新,且不能容错,大部分分布式系统都敬而远之,放弃对分布式事务的支持。
  • 解决多个节点之间一致性问题(通过操作日志同步数据)
  • 主节点故障,多个备节点提议自己成为主节点,Paxos协议保证所有节点最终达成一致。
  • ........
Paxos与2PC:
  • Paxos用于保证一个数据分片的多个副本之间的数据一致性(尤其分布在不同的数据中心时)
  • 2PC用于保证多个数据分片的操作的原子性(多态服务器上的操作要么全部成功要么全部失败)
  • Paxos的两种用法:①实现全局的锁服务或者命名和配置服务(Google Chubby以及Apache Zookeeper)②将数据复制到多个数据中心(Google Megastore以及Google Spanner)
  • 2PC与Paxos结合使用:2PC保证多个数据分片上的操作的原子性,Paxos保证一个数据分片的多个副本之间的一致性。Paxos解决2PC协议中协调者宕机的问题,当协调者出现宕机时,Paxos选举出新的协调者继续提供服务
跨机房部署:
  • 集群整体部署(较常见),每个机房一个总控节点
  • 单个集群跨机房部署,总共一个总控节点
  • Paxos选主副本,总控节点和工作节点不需要保持租约

 

4 分布式文件系统
4.1 Google文件系统
系统架构:
  • 三种角色:GFS Master(主控服务器)、GFS ChunkServer(CS,数据块服务器)、GFS客户端
  • 客户端(GFS提供给应用程序的访问接口)首先访问主控节点,获取CS信息,然后访问CS获取数据
  • 客户端只缓存元数据,不缓存文件(由GFS应用特点决定)
关键问题:
  • 租约机制:
    • Master将写chunk通过租约授权给CS,该CS称为主CS,其他副本所在CS为备CS。
    • 如果其中一个chunk备副本下线后又上线,在此过程中主副本有更新,此时Master会删除过期的chunk(通过版本号解决)。
  • 一致性模型:
    • GFS主要设计为追加而不是改写,主要是因为追加的一致性模型相对简单(追加失败只是读到过期数据,而不是错误数据)
    • 多客户端并发追加时可能出现数据被打断,导致数据不连续的问题,即某些数据中夹杂这其他客户端的数据(追求性能导致,由应用层处理这些问题)
  • 追加流程
    • 追加流程请看书
    • 两个特色:流水线(减少延时)和分离数据流、控制流(优化数据传输)
  • 容错机制
    • Master容错:操作日志、检查点、实时热备
    • Master上存储的三种数据:命名空间、文件到chunk的映射、chunk副本的位置
    • Master先操作日志再修改内存
    • Master持久化前两种数据,可以选择不持久化第三种数据,因为chunk副本位置信息在CS上也有保存
    • chunk的所有副本写入成功才算成功
    • CS会对存储的数据维持校验和(chunk以64M为单位,chunk又以64KB为单位划分为Block,每个Block对应一个32位校验和)
    • 读取一个chunk时会比较校验和
Master设计:
  • Master内存占用:
    • 前两种数据持久化存储,最后一种不持久化,前面说过了
    • 不会成为系统的瓶颈
  • 负载均衡:
    • chunk的所有副本不会放在同一个机架
    • 影响chunk副本创建位置的因素:①新副本所在CS的磁盘利用率低于平均水平;②限制每个CS“最近”创建的数量;③每个chunk的所有副本不能在同一个机架。
    • 以上第二点保证一台刚上线的CS不会因为磁盘利用率低导致大量chunk迁移上来而将它压垮的情况
    • 副本数小于一定数量之后会复制,有一个优先级
    • Master定期扫描副本分布情况,发现磁盘使用量或机器负载不均衡,将执行重新负载均衡操作
    • 限制重新复制和重新负载均衡任务的拷贝速度,以免影响正常读写
  • 垃圾回收
    • 延迟删除
    • Master定期检查,如果删除文件超过一段时间,就把文件从内存元数据中删除,在心跳协议中Master通知CS哪些chunk被删除
  • 快照:
    • 使用写实复制机制生成快照
    • “快照”只增加chunk一个引用计数,修改的时候才复制成新chunk,再对其做修改
    • 步骤:①通过租约机制回收对文件的每个chunk写权限,停止对文件的写服务;②Master拷贝文件名等元数据生成一个新的快照文件;③对执行快照的文件的所有chunk增加引用计数
ChunkServer设计:
  • 删除chunk时只需要将chunk移动到每个磁盘的回收站,新建chunk时可以重用
  • 磁盘和IO密集型应用,需要将磁盘和网络操作异步化
 
4.2 Taobao File System(Blob存储系统)
  • 文档、图片、视频一般成为Blob数据,存储Blob数据的系统成为Blob系统,Blob文件系统的特点是写入后基本都是只读,很少出现更新操作。
  • 两个问题:①Metadata信息量过大,无法存储在单台机器上;②减少图片读取的IO次数
  • 设计思路:多个逻辑图片文件共享一个物理文件
系统架构:
  • 借鉴GFS,但是有很大不同。
  • 不维护文件目录树,每个小文件用64位编号表示;由于读多写少,可以将写流程做的更加简单有效
  • 一个集群两个NameServer(一主一备)、多个DataServer,NS通过心跳对DS监测。
  • 每个DS上有多个dsp进程,每个dsp对应一个挂载点,一个挂载点对一个独立磁盘
  • 大量小文件合并成一个大文件(64M的Block),并有唯一ID,默认存储三份
  • 应用客户端不缓存文件数据,只缓存NS元数据
  • 追加流程:
    • TFS读多写少,及时每次写操作都经过NS也不会出现问题
    • 不支持多客户端写,同一时刻每个Block只能有一个写操作,多个客户端的写操作会被串行化
    • TFS写流程不够优化:①每个写请求都需要多次访问NS;②数据推送没有采用流水线方式减少延迟
讨论:
  • 通过Tair进行对图片去重。采用hash算法为图片文件计算指纹,图片写入之前在Tair中查找是否存在指纹,写入以后需要将指纹以及在TFS中的位置信息保存到去重系统(Tair)中
  • 图片在TFS中的位置通过<Block id, File id>来标识
 
4.3 Fackbook Haystack
系统架构:
  • 设计思路:多个逻辑文件共享一个物理文件(和TFS类似)
  • 三部分:目录(逻辑卷着和物理卷轴的对应关系、照片id到逻辑卷着之间的映射关系)、存储(以一个很大的物理卷轴为单位,多个存储节点上的物理卷轴组成一个逻辑卷轴)、缓存(解决对CDN过于依赖的问题)
  • Haystack缓存只缓存用户浏览器发送的请求且要求请求的Haystack存储节点是可写的
  • 写流程:
    • 请求Haystack目录获取逻辑卷轴 -> 生成照片唯一id将数据写入每一个对应的物理卷轴(每一个物理卷轴都要成功)
    • 只支持追加操作,更新照片时增加一张编号相同的照片到系统中,若逻辑卷轴和原来的不同,则在目录中修改成最新的逻辑卷着,若逻辑卷轴相同,以偏移大的照片文件为准
  • 容错处理:
    • 存储节点出错时,所有物理卷轴对应的逻辑卷轴标记为只读;未完成写操作全部失败;若故障不可恢复,需要进行拷贝(小时级别)
    • 目录有贮备数据库做持久化储存,由主备数据库提供容错机制
  • Haystack目录功能:
    • ①提供逻辑卷轴到物理卷轴的映射,维护照片id到逻辑卷轴的映射;
    • ②提供负载均衡;
    • ③屏蔽CDN服务;
    • ④标记某些逻辑卷轴为只读

 

5 分布式键值系统
5.1 Amazon Dynamo
  • 存储原始数据,不解析数据的具体内容
  • Dynamo设计时面临的问题及最终的解决方案:
    • 数据分布                   :   改进的一致性哈希(虚拟节点)
    • 复制协议                   :   复制写协议
    • 数据冲突处理            :   向量时钟
    • 临时故障处理            :   数据回传机制
    • 永久故障后的恢复     :   Merkle哈希树
    • 成员资格及错误检测  :   基于Gossip的成员资格和错误检测协议
数据分布:
  • 采用改进的一致性哈希算法将数据分布到多个存储节点中
  • Dynamo中每个节点维护整个集群的信息,客户端也缓存整个集群的信息
  • 为保证每个节点缓存最新的成员信息,所有节点周期性通过Gossip协议从其他节点任意选择一个与之通信的节点,连接成功后交换集群信息
  • Gossip协议的执行过程请看书(P87)
  • 种子节点
一致性与复制:
  • 思路:假设数据存储N份,DHT(一致性哈希表)定位到的数据所属节点为K,则数据存储在节点K、K+1、....、K+N-1上。如果第K+i(0<=i<=N-1)台机器宕机,则往后找一台机器K+N临时替代;如果第K+i台机器重启,则数据回传;若永久失效,机器K+N需要进行数据同步操作(Merkle树)
  • NWR:N表示复制的备份数,R表示成功读操作的最少节点数,W表示成功写操作的最少节点数
  • 当W+R>N时,就能保证当存在不超过一台机器故障的时候,至少能够读到一份有效数据
  • 向量时钟用[nodes,counter]对表示,nodes表示节点,counter表示初始为0的计数器,更新一次加1(P89)
  • Dynamo只保证最终一致性,如果多个节点之间的更新顺序不一致,客户端可能读取不到期望的结果
容错:
  • 数据回传(临时故障)
  • Merkle树同步(永久故障):Merkle树非叶子节点对应多个文件(子节点值组合后的哈希值),叶子节点对应单个文件(文件内容的哈希值)
  • 读取修复(NWR)
负载均衡:
  • 随机分配。效果不错,但可控性比较差
  • 数据范围等分+随机分配
读写流程:
  • 写数据:
    • 根据一致性哈希计算出存储节点,选择一个副本作为本次写的协调者
    • 并发的往所有副本发送写请求,每个副本将接收到的数据写入本地
    • 副本写入成功后回复协调者
    • 若写入失败,协调者会将它加入重试列表不断重试
    • 所有协调者写入成功后,协调者回复客户端写入成功
  • 读数据:
    • 根据一致性哈希选择存储节点,选择一个副本作为本次读的协调者
    • 协调者根据并发策略选择R个副本,并发发送读请求
    • 当所有副本都读取成功时,协调者回复客户端
    • 两种情况:数据一致和数据不一致