一、概述
A.分布式存储概念
1.分布式存储系统是大量普通 PC服务器通过Internet互联，对外作为一个整体提供存储服务
2.特性：可扩展、低成本、高性能、易用
3.分布式存储涉及的技术主要来自两个领域：分布式系统以及数据库，包括数据分布、一致性、容错、负载均衡、事务与并发控制、易用性、压缩/解压缩
B.分布式存储分类
1.数据需求分：非结构化数据、结构化数据、半结构化数据
2.本书分为四种：
- 分布式文件系统：图片、照片、视频等非结构化数据对象，对象之间没有关系，一般称为Blob数据。存储三类数据：Blob对象、定长块及大文件。
- 分布式键值系统：用于存储关系简单的半结构化数据，只提供基于主键的CRUD功能。与Hash表比较类似，一般用作缓存
- 分布式表格系统：用于存储关系比较复杂的半结构化数据，不仅支持简单的CRUD操作，而且支持扫描某个主键范围。
- 分布式数据库：用于存储结构化数据。采用二维表格组织数据，提供SQL关系查询语言。
二、单机存储系统
A.硬件基础
1.存储系统的性能主要包括两个维度：吞吐量以及访问延时，设计系统时要求能够在保证访问延时的基础上，通过最低的成本实现尽可能高的吞吐量。
2.磁盘和SSD的访问延时差别很大，但带宽差别不大，因此，磁盘适合大块顺序访问的存储系统，SSD适合随机访问较多或者对延时比较敏感的关键系统。也常组合在一起进行混合存储，热数据（访问频繁）存储到SSD中，冷数据（访问不频繁）存储到磁盘中
B.单机存储引擎
1.哈希存储引擎：Bitcask
- 数据结构：数据文件中数据项分为主键（key）、value内容（value）、主键长度（key_sz）、value长度（value_sz）、时间戳（timestamp）以及crc校验值；内存中哈希表包含文件编号（file id）、value在文件中的位置（value_pos）、value长度（value_sz）
- 定期合并：需要定期执行合并（Compaction）操作以实现垃圾回收
- 快速恢复：通过索引文件（hint file）来提高重建哈希表的速度
2.B树存储引擎：Mysql InnoDB
- 数据结构：按照页面（Page）来组织数据，每个页面对应B 树的一个节点。叶子节点保存每行的完整数据，非叶子节点保存索引信息。数据在每个节点有序存储，数据库查询时需要从根节点开始二分查找直到叶子节点，每次读取一个节点，如果对应的页面不在内存中，需要从磁盘中读取并缓存起来。B 树检索一次最多需要h-1次磁盘IO，复杂度为O(h)=O(logdn)，N为元素个数，d为每个节点的出度，h为B 树高度。
- 缓冲区管理：LRU，淘汰最长时间没有读或者写过的块；LIRS，将缓冲池分为两级，数据首先进入第一级，如果数据在较短的时间内被访问两次或者以上，则成为热点数据进入第二级，每一级内部还是采用LRU替换算法。
3.LSM树存储引擎：LevelDB
- LSM树（Log Structured Merge Tree）将对数据的修改增量保持在内存中，达到指定大小限制后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作
- 存储结构：内存中的MemTable和不可变MemTable以及磁盘上的几种主要文件，当前（Current）文件、清单（Mainfest）文件、操作日志（Commit Log）文件以及SSTable文件
- 合并：LevelDB内部会执行Compaction操作来对已有的记录进行整理压缩，从而删除一些不再有效的记录，减少数据规模的文件数量。
C.数据模型
1.文件模型：以目录树的形式组织文件
- POSIX(Portable Operating System Interface)：是应用程序访问文件系统的API标准，定义了：Open/close、Read/write、Opendir/closedir、Readdir。NFS(Network File System)文件系统。
- 对象模型典型系统：Amazon Simple Storage(S3)、Taobao File System(TFS)等，弱化了目录树的概念，要求对象只一次性写入到系统，只能删除整个对象，不允许修改其中某个部分。
2.关系模型：是一个表格，由多个元组（行）构成，而每个元组又包含多个属性（列）。
- 关系名、属性名以及属性类型称作该关系的模式（schema）。
- SELECT语句大致计算过程：FORM->WHERE->GROUP BY->HAVING->SELECT->ORDER BY
3.键值模型：
- 支持基于主键的操作：Put、Get、Delete
- 基于列的操作：Insert、Delete、Update、Get、Scan，典型系统是Google Bigtable以及HBase
- 表格模型一般不支持多表关联操作，事务操作支持也比较弱，支持无模式（schema-less）特性
4.SQL与NoSQL：
- NoSQL具有良好的可扩展性、弱化数据库的设计范式、弱化一致性要求，在一定程度上解决了海量数据和高并发的问题。二者的优势将不断融合，不存在谁取代谁的问题。
- 关系数据库在海量数据场景面临的挑战：事务、联表、性能
- NoSQL面临的问题：缺少统一标准、使用及运维复杂
D.事务与并发控制
- 事务规范了数据库操作的语义，每个事务使得数据库从一个一致的状态原子地转移到另一个一致的状态。
- 多个事务并发执行时，如果它们的执行结果和按照某种顺序一个接着一个串行执行的效果相同，这种隔离级别称为可串行化。可串行化是比较理想的情况。
- 为了提高读事务性能，可以采用写时复制 （Copy-On-Write,COW）或者多版本并发控制（Multi-Version Concurrency Control,MVVC）技术来避免写事务阻塞读事务。
1.事务
- 原子性（A）：对数据的修改，要么全执行，要么全都不执行
- 一致性（C）：事务需要保持数据库数据的正确性、完整性和一致性。
- 隔离性（I）：数据据库在并发执行多个事务，每个事务可能需要对多个表项进行修改和查询，此时，更多的查询请求可能也在执行中。数据库需要保证每一个事务在它的修改全部完成之前 ，对其他的事务是不可见的，也就是不能让其他事务看到该事务的中间状态
- 持久性（D）：事务完成后，它对于数据库的影响是永久的，即使系统出现各种异常也是如此
2.牺牲隔离属性来换取并发度，4种隔离级别：
- Read Uncommmitted(RU)：读取未提交的数据，最低；
- Read Committed(RC)：读取已提交的数据；
- Repeatable Read(RR)：可重复读取；
- Serizlizable(S)：可序列化，即串行化执行的，最高；
3.低隔离级别可能会导致读取到脏数据或者事务执行异常
- Lost Update(LU)：第一类丢失更新，两个事务同时修改一个数据项，但后一个事务中途失败回滚，则前一个事务已提交的修改都可能丢失（所有隔离级别都不会出现）
- Dirty Reads(DR)：一个事务读取了另外一个事务更新即没有提交的数据项（RU）
- Non-Repeatable Reads(NRR)：一个事务对同一数据项的多次读取可能得到不同的结果（RU、RC）
- Second Lost Updates problem(SLU)：第二类丢失更新，两个并发事务同时读取和修改同一数据项，则后面的修改可能使得前面的修改失效（RU、RC）
- Phantom Reads(PR)：事务执行过程中，由于前面的查询和后面的查询的期间有另外一个事务插入数据，后面的查询结果出现了前面查询结果中未出现的数据（RU、RC、RR）
4.并发控制
- 数据库锁：允许对同一个元素加多个读锁，但只允许加一个写锁，且写事务将阻塞读事务。事务如果只操作一行，可以对该行加相应的读锁或写锁，如果操作多行，需要锁住整个行范围。
- 死锁：多个事务并发执行时可能引入死锁。解决方式：为每个事务设置一个超时时间，超时后自动回滚；死锁检测，检测到死锁后通过回滚其中某些事务来消除循环依赖
- 写时复制（Copy-On-Write,COW）：读操作不用加锁，问题是每次写操作都需要拷贝从叶子到根节点路径上的所有勤快点，写操作成本高，另外多个写操作之间是互斥的，同一时刻只允许一个写操作
- 多版本并发控制（Multi-Version Concurrency Control,MVCC）：对每行数据维护多个版本，无论事务的执行时间有多长，MVCC总能够提供与事务开始时刻相一致的数据
E.故障恢复
1.一般采用操作日志（或提交日志），分为回滚日志（UNDO Log）、重做日志（REDO Log）、UNDO/REDO日志
2.操作日志：记录了事务的操作，简化：假设内存够大全部存入内存；每个事务只包含一个操作，每个事务都必须立即提交；
3.重做日志：必须要确保与修改相关的操作日志先刷入到磁盘中
- 将REDO日志以追加写的方式写入磁盘的日志文件
- 将REDO日志的修改操作应用到内存中
- 返回操作成功或失败
4.优化手段：
- 成组提交：对一致性要求高的立即刷入，要求低的可以将REDO缓存下来定期刷入，会牺牲事务的延时，但大大提高了系统的吞吐量
- 检查点：将内存中的数据定期转储（Dump）到磁盘，称为checkpoint（检查点技术）
F.数据压缩
1.压缩算法：
- Huffman编码：找出一种前缀编码方式，使编码的长度最短
- LZ系列压缩算法：是基于字典的压缩算法，压缩过程中动态创建字典并保存在压缩信息里面。（LZW、Gzip）
- BMdiff与Zippy（也称为Snappy）：源于LZ77，速度更快改进：只保存所有长度为4的子串；将数据划分为一个一个长度为32KB的数据块分别压缩；
2.列式存储：通过把相同列的数据组织在一起，不仅减少了大数据分析需要查询的数据量，还大大提高了数据的压缩比
- 传统的行式数据库适合查询时用到大部分数据列的查询，OLTP(Online Transaction Processing,联机事务处理)应用适合采用这种方式
- 如果只查询少数数据列时，用列式存储数据库能大大提高OLAP大数据量查询的效率
- 部分提供列组，能够同时满足OLTP和OLAP
三、分布式系统
A.基本概念
1.异常：
- 服务器宕机：需要考虑如何通过读取持久化介质（硬盘）中的数据来恢复内存信息，从而恢复到宕机前的某个一致状态
- 网络异常：网络永远是不可靠的，任何一个消息只有收到对方的回复后才可以认为发送成功，系统设计时总是假设网络将会出现异常并采取相应的处理措施
- 磁盘故障：将数据存储到多台服务器
2.超时：
- 某个节点向另外一个节点发起RPC(Remote Procedure Call)调用，这个RPC执行的结果有三种状态：“成功”、“失败”、“超时”
- 当出现超时状态时，只能通过不数据读取之前 操作的状态来验证RPC操作是否成功。
- 设计分布式存储系统时可以将操作设计为“幂等”的，操作执行一次与执行多次的结果相同，如，覆盖写就是一种常见的幂等操作
3.一致性：
- 场景：存储系统、客户端A、B、C
- 客户端角度：强一致性，假如A写入数据，存储系统保证A、B、C的读取操作都返回最新值；弱一致性，假如A写入数据，不保证A、B、C是否能够读取到最新值；最终一致性，假如A写一篇数据，存储系统保证如果后续没有写操作更新同样的值，ABC读取操作“最终”都会读取到A写入的最新值。
- 最终一致性描述：读写(Read-your-writes)一致性，A写入数据保证A后续操作都是最新值；会话(Session)一致性，要求客户端和存储系统交互的整个会话期间保证读写一致性；单调读(Monotonic read)一致性，如果A已经读取了对象的某个值，那么后续操作不会读取到更早的值；单调写(Monotonic write)一致性，A的写操作顺序 完成；
- 存储系统一致性：副本一致性；更新顺序一致性；
4.衡量指标：
- 性能：系统的吞吐能力（每秒的读操作数(QPS，Query Per Second)或者写操作数(TPS，Transaction Per Second)）、系统的响应时间
- 可用性(availability)：系统在面对各种异常时可以提供正常服务的能力
- 一致性：越是强的一致性模型，用户使用起来越简单
- 可扩展性(scalability)：指分布式存储系统通过扩展集群服务器规模来提高系统存储容量、计算量和性能的能力。
B.性能分析
1.性能分析的结果不是精确的，但至少可以保证估算的结果与实际值不会相差一个数量级。性能分析就是需要找出可能出现的资源瓶颈
2.性能分析可能会很复杂，因为不同情况下系统的瓶颈点不同，网络、磁盘、机房等
C.数据分布
1.哈希分布：根据数据的某一种特征计算哈希值，并将哈希值与集群中的服务器建立映射关系，从而将不同哈希值的数据分布到不同的服务器上。所谓数据特征可以是key-value系统中的主键(key)，也可以是其他与业务逻辑相关的值。
- 如果按照主键散列，同一个用户id下的数据可能被分散到多台服务器；如果按照用户id散列，容易出现“数据倾斜”问题，即某些大用户的数据量很大。
- 处理大用户问题一般两种方式，一种是手动拆分，即线下标记系统中的大用户，根据这些大用户的数据量将其拆分到多台服务器上。另一种方式是自动拆分，即数据分布算法能够动态调整。
- 传统哈希分布还有一个问题：当服务器上下线时，N值发生变化 ，数据映射被打乱。一种思路是将哈希值与服务器对应关系作为元数据，交给专门的元数据服务器来管理。另一种思路就是采用一致性哈希（Distributed Hash Table,DHT）算法，给系统中每个节点分配一个随机token，这些token构成一个哈希环，执行数据存放时，计算主键(Key)的哈希值，存放到顺时针方向第一个大于或者等于该哈希值的token所在的节点。
- 哈希环中的位置信息：O(1)位置信息，每台服务器记录它的前一个以及后一个节点的位置信息；O(longN)位置信息，每台服务器维护一个大小为n的路由表；O(n)位置信息，每台服务器维护整个集群中所有服务器的位置信息，将查找服务器的时间复杂度降为O(1)，牺牲空间换时间
2.顺序分布：将大表顺序划分为连续的范围，每个范围称为一个子表，总控服务器负责将这些子表按照一定的策略分配到存储节点上。
- 系统设计时需要考虑子表的分裂与合并，将极大增加系统复杂度。
- 子表分裂指当一个子表太大超过一定阀值时需要分裂为两个子表。子表合并一般由数据删除引起，当相信的两个子表都很小时，可以合并为一个子表。
3.负载均衡
- 工作节点通过心跳包（Hearbeat，定时发送）将节点负载相关的信息，如CPU、内存等资源使用率，读写次数及读写数据量等发送给主控节点。主控节点计算出工作节点的负载以及需要迁移的数据，生成迁移任务放入迁移队列中等待执行
- 负载均衡需要控制节奏，需要做到比较平滑
D.复制
1.同一份数据的多个副本中往往有一个副本为主副本（Primary），其他副本为备副本（Backup），由主副本将数据复制到备份副本。复制协议分为两种：强同步复制以及异步复制。
2.强同步模式的好处在于如果主副本出现故障，至少有1个备副本拥有完事的数据，但可能产生阻塞；异步复制 不需要等待备副本的回应，系统可用性较好，但一致性较差
3.Oracle的复制组件包含三种模式：最大保护模式（Maximum Protection）、最大性能模式（Maximum Performance）、最大可用性模式（Maximum Availability），推荐最大可用性模式，折衷同步和异步模式。
E.容错
1.首先，分布式存储系统需要能够检测到机器故障，在分布式系统中，故障检测往往通过租约（Lease）协议实现。接着，需要能够将服务揿电掣或者迁移到集群中的其他正常服务的存储节点。
2.常见故障：单机故障和磁盘故障以及机架等，多备份
3.总控机发送心跳包检测故障。租约机制就是带有超时时间的一种授权。服务机器通过不断续租来延长有效期。
4.故障恢复
- 单层结构：临时故障，等待一段时间后如果重新上线即可恢复；永久性故障则需要执行增加副本操作重新添加
- 总控节点自身也要将状态实时同步到备机，当故障发生时，可以通过外部服务选举某个备机作为新的总控节点。
F.可扩展性
1.总控节点
- 用于维护数据分布信息，执行工作机管理，数据定位，故障检测和恢复，负载均衡等全局调度工作。通过引入总控节点，可以使得系统的设计更加简单，并且更加容易做到强一致性，对用户友好。
- 瓶颈：分布式文件系统的总控节点除了执行全局调度，还需要维护文件系统目录树，内存容量可能会率先成为性能瓶颈；而其他分布式文件系统的总控节点只需要维护数据分片的位置信息，一般不会成为瓶颈
- 如果总控节点成为瓶颈，可以采用两级结构，在总控机与工作机之间增加一层元数据节点，每个元数据节点只维护一部分而不是整个分布式文件系统的元数据
2.数据库扩容
- 通过主从复制提高系统的读取能力
- 通过垂直拆分和水平将数据分布到多个存储节点
- 通过主从复制将系统扩展到多个数据中心
- 传统架构面临的问题：扩容不够灵活、扩容不够自动化、增加副本时间长
3.异构系统
- 通过分片副本
G.分布式协议
1.两阶段提交协议（Two-phase Commit,2PC）经常用来实现分布式事务，在两阶段协议中，系统一般包含两类节点：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个。
- 阶段1：请求阶段（Prepare Phase）。协调者通知事务参与者准备提交或者取消事务，然后进入表决过程。表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地执行成功）或者取消（事务参与者本地执行失败）
- 阶段2：提交阶段（Commit Phase）。协调者基于第一个阶段的结果进行决策：提交或者取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者通知所有的参与者取消事务。
- 可能面临的故障：事务参与者发生故障、协调者发生故障
- 两阶段提交协议是阻塞协议，执行过程中需要锁住其他更新，且不能容错。
2.Paxos协议用于解决多个节点之间的一致性问题。多个节点之间通过操作日志同步数据，如果只有一个节点为主节点，那么，很容易确保多个节点之间操作日志的一致性。考虑到主节点可能出现故障，系统需要选举出新的主节点。Paxos协议正是用来实现这个需求。只要保证了多个节点之间操作日志的一致性，就能够在这些节点上构建高可用的全局服务。
- 需要考虑两个问题：正确性，即只有一个提议值会生效；可终止性，即最后总会有一个提议值生效。
3.Paxos与2PC：建议结合使用
H.跨机房部署
1.集群整体切换：机房保持独立，每个机房部署单独的总控节点。
2.单个集群跨机房：将单个集群部署到多个机房，允许不同数据分片的主副本位于不同的机房
3.Paxos选主副本：每个数据分片的多个副本构成一个Paxos复制组。
四、分布式文件系统
1.分布式文件系统的主要功能有两个：一个是存储文档、图像、视频之类的Blob类型数据；另外一个是作为分布式表格系统的持久化层。
A.Google文件系统
1.Google File System(GFS)，构建在廉价服务器之上的大型分布系统，将服务器故障视为正常现象，通过软件的方式自动容错，在保证系统可靠性和可用性的同时，大大降低系统的成本。
2.系统架构
- GFS 文件被划分为固定大小的数据块(chunk)
- GFS Master(主控服务器)：在创建时分配一个64位全局唯一的chunk句柄，维护系统的元数据，包括文件及chunk命名空间、文件到chunk之间的映射、chunk位置信息，整个系统的全局控制如chunk租约管理、垃圾回收无用chunk、chunk复制等，会定期与CS通过心跳交换信息
- GFS ChunkServer(CS，数据块服务器)：以普通linux文件形式将chunk存储在磁盘，在不同的机器复制多份，默认三份
- GFS客户端：提供给应用程序的访问接口，一组专用接口，不遵循POSIX规范，以库文件形式提供。
- GFS最主要的应用：MapReduce与Bigtable
3.关键问题
- 租约机制：GFS系统中通过租约（lease）机制将chunk写操作授权给ChunkServer。拥有租约授权的ChunkServer称为主ChunkServer，其他称为备ChunkServer。在租约有效其内，对该chunk的写操作都由主ChunkServer负责，从而减轻Master的负载
- 一致模型：GFS主要是为了追加（append）而不是改写（overwrite）而设计的。GFS追加失败将重试，只要返回用户追加成功，说明在所有副本中都至少追加成功了一次。需要应用层能够处理重复记录及产生可识别的填充记录的问题
- 追加流程：有两个特色，流水线及分离数据流与控制流P69
- 容错机制：Master容错与传统方式类似，通过操作日志加checkpoint的方式进行，并且有一台“Shadow Master”实时热备；ChunkServer容错采用复制多个副本的方式实现，每个chunk有多个存储副本，分别 存储在不同的ChunkServer上。
4.Master设计
- 内存是Master的稀有资源，1PB数据的chunk元信息大小不超过3GB
- GFS采用延迟删除的机制，垃圾回收一般在服务低峰期执行
- GFS使用标准的定时复制机制生成快照，“快照”只是增加GFS中chunk的引用计数
5.ChunkServer设计
- 存储的时候需要保证chunk尽可能均匀分布在不同的磁盘中
- ChunkServer是一个磁盘和网络IO密集型应用，需要能够做到将磁盘和网络操作异步化，但会增加代码实现的难度
B.Taobao File System
1.系统架构
- 借鉴了GFS，但有不同：TFS内部不维护文件目录树，每个小文件使用一个64位的编号表示，TFS是一个读多写少的应用，相比GFS的写流程可以做得更加简单有效
- 一个TFS集群由两个NameServer节点（一主一备）和多个DataServer节点组成，NameServer相当于GFS中的Master，DataServer相当于ChunkServer
2.追加流程：多个写操作会被串行化，每个写请求都要多次访问NameServer，数据推送也没有采用流水线方式减小延迟
3.NameServer：主要功能是Block管理，包括创建、删除、复制、重新均衡；DataServer管理，包括心跳、DataServer加入及退出；管理Block与所在DataServer之间的映射关系
4.图片应用的问题：去重：需要在外部维护一套文件级别的去重系统（Dedup）
C.Facebook Haystack
1.类似TFS，主要包括三个部分：目录（Directory）、存储（Store）、缓存（Cache）
D.内容分发网络
1.CDN通过将网络内容发布到靠近用户的边缘节点，使不同地域的用户在访问相同网页时可以就近获取 。
五、分布式键值系统
A.Amazon Dynamo
1.Dynamo以很简单的键值方式存储数据，不支持复杂的查询。Dynamo中存储的是数据值的原始形式，不解析数据的具体内容。采用无中心的P2P设计。
2.数据分布
- Dynamo系统采用一致性哈希算法将数据分布到多个存储节点中。
- Dynamo使用了改进的一致性哈希算法，每个节点根据性能分配多个token，每个token对应一个“虚拟节点”。
- 所有节点每隔固定时间通过Gossip协议的方式从其他节点中做任意选择一个与之通信的节点。
3.一致性与复制
- 数据回传（Hinted Handoff）
- NWR：N表示复制的备份数，R指成功读操作的最少节点数，W指成功写操作的最少节点数，只要保证W R>N，就可以保证当存在不超过一台机器故障时，至少能够读到一份有效的数据
- 解决冲突使用向量时钟方式
4.容错
- 数据回传
- Merkle树同步：每个非叶子节点对应多个文件，为其所有子节点值组合以后的哈希值；叶子节点对应单个数据文件，为文件内容的哈希值
- 读取修复
5.负载均衡
- 随机分配token
- 数据范围等分 随机分配token（将数据的哈希空间等分为Q=N*S份，N=机器个数，S=每台机器 的虚拟节点数）然后每台机器选择S个分割点作为token
B.
1.系统架构
- Tair作为一个分布式系统，是由一个中心控制节点和若干个服务节点组成。中心节点称为Config Server，服务节点称为Data Server
2.关键问题
- 数据分布：根据数据的主键计算哈希值后，分布到Q个桶中，桶是负载均衡和数据迁移的基本单位。Q取值要远大于集群的物理机器数
- 容错：当某台Data Server故障不可用时，Config Server能够检测到。
六、分布式表格系统
A.Google Bigtable
1.Bigtable是Google开发的基于GFS和Chubby（分布式锁服务）的分布式表格系统。
2.Bigtable由很多表格组成，每个表格包含很多行，每行通过一个主键（Row Key）唯一标识，每行又包含很多列（Column）。某一行的某一列构成一个单元（Cell），每个单元包含多个版本的数据。整体上看，是一个分布式多维映射表。另外，Bigtable将多个列组织成列族（column family），这样列名由两个部分组成：（column family,qualifier）
3.架构：三部分组成：客户端程序议员团（Client）、一个主控服务器（Master）、多个子表服务器（Tablet Server）
4.数据分布：数据在系统中切分为大小100-200MB的子表，所有的数据按照行主键全局排序。
5.复制与一致性：Bigtable系统保证强一致性，同一个时刻同一个子表只能被一台Tablet Server服务。这是通过Chubby的互斥锁机制保证的。
6.容错：Bigtable Master启动时需要从Chubby中获取一个独占锁，如果Master发生故障，Master的独占锁将过期，管理程序会自动指定一个新的Master服务器，它从Chubby成功获取独占锁后可以继续提供服务
7.负载均衡：子表是Bigtable负载均衡的基本单位。Tablet Server定期向Master汇报状态，当状态检测时发现某个Tablet Server上的负载过重时，Master会自动对其进行负载均衡，即执行子表迁移操作
8.分裂与合并：分裂操作不需要进行实际 的数据拷贝工作，只需要将内存中的索引信息分成两份，比如分裂前子表的范围为（起始主键，结束主键），在内存中将索引分成（起始主键，分裂主键）和（分裂主键，结束主键）两个范围
9.单机存储：采用Merge-dump存储引擎。写入时要先写操作日志，成功后应用到内存中的MemTable中，写操作日志是往磁盘中的日志文件追加数据
- 包含三种Compaction策略：Minor Compaction、Merging Compaction、Major Compaction
- Tablet Server的缓存两种：块缓存（Block Cache）和行缓存（Row Cache）
10.垃圾回收：Compaction后生成新的SSTable，原有的SSTable成为垃圾被回收掉
B.Google Megastore
1.系统架构 ：客户端库、复制服务器、协调者
2.实体组：数据拆分成不同的实体组，每个实体组内的操作日志采用基于Paxos的方式同步到多个机房保证强一致性。
3.并发控制
- 读事务：最新读取（current read）、快照读取（snapshot read）、非一致性读取（inconsistent read）
- 写事务：采用了预写式日志（Write-ahead日志或REDO日志），只有当所有的操作都在日志中记录下来后，写操作才对数据执行修改。
4.复制：基于Paxos的复制协议机制，对于普通 的Master-Slave强同步机制，Master宕机后，Slave如果需要切换为Master首先需要确认Master宕机，检测Master宕机这段时间需要停止写服务，否则将造成数据不一致
5.索引
- 局部索引（local index）：是单个实体组内部的，先记录REDO日志，回放REDO日志时原子地更新实体组内部的数据和局部索引
- 全局索引（global index）
- STORING子句：通过在索引中增加STORING字句，系统可以在索引中冗余一些常用的列字段，从而不需要查询基本表，减少一次查询操作
可重复索引：一行数据可能对应多行索引
6.协调者
- 快速读：能够利用本地读取（local reads）实现快速读。
- 协调者的可用性：使用了Chubby锁服务，协调者在启动时从数据中心获取Chubby锁
- 竞争条件：失效操作总是安全的，但是生效操作必须谨慎处理
7.读取流程：本地查询->发现位置（本地读取、多数派读取）->追赶（获取操作日志、应用操作日志）->使实体组生效->查询数据
8.写入流程：请求主副本接受->准备->接受->使实体组失效
C.Windows Azure Storage
1.整体架构
- WAS部署在不同地域的多个数据中心，依赖底层的Windows Azure结构控制器（Fabric Controller）管理硬件资源。结果控制器的功能包括节点管理，网络配置，健康检查，服务启动，关闭，部署和升级
- WAS分为两个部分：定位服务（Location Serveric,LS）和存储区（Storage Stamp），存储区分为三层，文件流层（Stream Layer）、分区层（Partition Layer）以及前端层（Front-End Layer）
- WAS包含两种复制方式：存储区内复制（Intra-Stamp Replication）、跨存储区复制（Inter-Stamp Replication）
2.文件流层
- 文件流层提供内部接口供服务分区层使用。提供类似文件系统的命名空间和API，但所有的写操作只能是追加，把持的接口包括：打开&关闭文件、改名、读取以及追加到文件。
- 架构：三个部分组成，流管理器（Stream Manager,SM）、extent存储节点（Extent Node,EN）、客户端库（Partition Layer Client）
- 复制及一致性：只允许追加不允许修改，追加操作是原子的，以数据块（block）为单位，多个数据块可以由客户端凑成一个缓冲区一次性提交到文件流层的服务端，保证原子性；文件流层保证：只要记录被追加并成功响应客户端，从任何一个副本都能够读到相同的数据；即使追加过程出现故障，一旦extent被缝合，从任何一个被缝合的副本都能够读到相同的内容
- 存储优化：文件流层客户端追加操作应答成功要求所有的副本都将数据持久化到磁盘；文件流层还有一种抹除码（erasure coding）机制用于减少extent副本占用的空间，GSF以及开源的HDFS也采用了这个机制
3.分区层
- 分区层构建在文件流层之上，用于提供Table、Blob、Queue等数据服务。一个重要特性是提供强一致性并保证事务操作顺序。
- 架构：客户端程序库（Client）、分区服务器（Partition Server，PS）、分区管理器（Partition Manager,PM）、锁服务（Lock Service）
- 分区数据结构：与Bigtable类似，不同处：每个分区有一个操作日志；每个分区维护各自的元数据；专门走入了Blob数据文件流；
- 负载均衡：两个阶段：卸载、加载
4.分裂与合并：WAS对某个分区执行分裂操作两种原因，一种可能是分区太大，另外一种可能是分区的负载过高
七、分布式数据库
A.数据库中间层
1.架构：
- MySQL客户端库
- 中间层dbproxy：解析MySQL协议，执行SQL路由，SQL过滤，读写分离，结果归并，排序以及分组
- 数据库组dbgroup：由一主N备组成
- 元数据服务器：负责维护dbgroup拆分规则并用于dbgroup选主
- 常驻进程agents：用于实现监控，单点切换，安装，卸载程序等
2.扩容：MySQL Sharding集群一般按照用户id进行哈希分区
B.Microsoft SQL Azure
1.数据模型
- 逻辑模型：将数据划分为多个分区，通过限制事务只能在一个分区执行来规避分布式事务，通过主从揿电掣（Primary-Copy）协议将数据复制到多个副本，保证高可用性
- 物理模型：每个有主键的表格组根据划分主键列有序地分成多个数据分区（partition）
2.架构
- SQL Server实例：是一个运行着SQL Server的物理数据库，每个物理数据库包含多个子数据库
- 全局分区管理器（Global Partition Manager）：维护分区映射表信息
- 协议网关（Protocol Gateway）：负责将用户的数据库链接请求转发到相应的主分区上
- 分布式基本部件（Distributed Fabric）：用于维护机器上下线状态，检测服务器故障并为集群中的各种角色执行选举主节点操作
3.复制与一致性：采用“Quorum Commit”的复制协议，用户数据存储三个副本，至少写成功两个副本才可以返回客户端成功
4.容错：通过全局分区管理器
5.负载均衡：包括副本迁移以及主备副本切换
6.多租户：云存储系统中多个用户的操作相互干扰，因此需要限制每个SQL Azure逻辑实例使用的系统资源
- 操作系统资源限制
- SQL Azure逻辑数据库容量限制
- SQL Server物理数据库数据大小限制
C.Google Spanner
1.数据模型：与Megastore系统比较类似
2.架构：构建在Colossus上，Universe：一个Spanner部署实例称为一个Universe；Zones：每个Zones属于一个数据，而一个数据中心可能有多个Zone
- Universe Master：监控这个Universe里Zone级别的状态信息
- Placement Driver：提供跨Zone数据迁移功能
- Location Proxy：提供获取数据的位置信息服务
- Spanserver：提供存储服务，功能上相当于Bigtable系统中的Tablet Server
3.复制与一致性：通过Paxos协议，实现了跨数据中心的多个副本之间的一致性
4.TrueTime：是一个提供本地时间的接口，但与Linux上的gettimeofdayr癌不一样的是，它除了可以返回一个时间戳t，还会给出一个误差e.
5.并发控制
6.数据迁移：移动目录操作在后台进行
八、OceanBase架构初探
九、分布式存储引擎
十、数据库功能
十一、质量保证、运维及实践
十二、云存储
十三、大数据
