Question

1.概述

分布式存储分类： - 非结构化数据 - 结构化数据 - 半结构化数据

分布式存储系统分为四类：分布式文件系统、分布式键值（Key-Value）系统、分布式表格系统和分布式数据库 分布式文件系统:图片等非结构化数据, 这样的数据一般称为Blob（Binary Large Object，二进制大对象数据)。Blob对象、定长块以及大文件 分布式键值系统:用于存储关系简单的半结构化数据，它只提供基于主键的CRUD（Create/Read/Update/Delete）功能，即根据主键创建、读取、更新或者删除一条键值记录。 分布式表格系统:用于存储关系较为复杂的半结构化数据 分布式数据库一般是从单机关系数据库扩展而来，用于存储结构化数据

2.单机存储系统

单机存储引擎就是哈希表、B树等数据结构在机械磁盘、SSD等持久化介质上的实现。单机存储系统是单机存储引擎的一种封装，对外提供文件、键值、表格或者关系模型。 存储系统的性能：吞吐量和访问时延

• 数据模型：文件模型:unix 文件, 对象模型：存储二进制数据块, Amazon S3
• 关系模型：关系名、属性名、以及属性类型称作该关系模式。索引和事务
• 键值模型：表格模型（bittable、hbase）

事务的四个基本属性： - 原子性 - 一致性：保证数据库数据的正确性、完整性和一致性。 - 隔离性：一个事务在它的修改全部完成之前，对其他事务不可见 - 持久性：四种隔离级别

并发控制： 数据库锁：读事务、写事务、读写混合事务。锁也分为读锁及写锁 读锁和写锁，允许对同一个元素加多个读锁，但只允许加一个写锁，且写事务将阻塞读事务 多个事务并发可能引入死锁，两个事务循环依赖 解决死锁的思路： - 1.为每个事务设置一个超时时间，超时候自动回滚 - 2.死锁检测：检测到死锁后可通过回滚某些事务来消除循环依赖

写时复制(Copy-onWrite, COW): 读操作不用加锁。每次写操作都需要拷贝叶子到根节点路径上的所有节点，写操作成本高。 多个写操作互斥。

多版本并发控制(Multi-version concurrency control):每个查询都通过版本检查，只获得自己需要的数据版本

故障恢复：一般采用操作日志实现故障恢复。操作日志分为回滚日志（undo log),重做日志(redo log),以及 undo/redo 日志。

优化手段： - 1.成组提交(牺牲写事务的延迟，增大吞吐) - 2.检查点：将内存中的数据定期dump到磁盘

数据压缩:有损和无损 压缩算法：本质是寻找数据的重复或者规律，用尽量少的字节表示。 OLTP 和 OLAP 列式存储：将同一个数据列的各个值存放在一起。不适合每次查询涉及的数据量较小或者大部分查询都需要整行的数据

3章：分布式系统

两个重要的协议： Paxos选举协议: 用于多个节点之间达成一致，往往用于实现总控节点选取 两阶段提交协议: 用于保证跨多个节点操作的原子性，这些操作要么全部成功，要么全部失败

3.1.1 异常 1. 异常类型： - 服务器宕机：不可用 - 网络异常：设计容错系统的一个基本原则就是：网络永远是不可靠的，任何一个消息只有收到对方回复后才可以认为发送成功， 系统设计时总是假设网络出现会出现异常并采取相应处理措施。 - 磁盘故障：磁盘损坏和磁盘数据错误（校验和机制）

1. 超时 分布式系统中，如果某个节点向另外一个节点发起rpc，这个rpc执行的结果有三种状态：成功、失败、超时（幂等，一直重试到成功）

3.1.2 一致性 副本是分布式存储系统容错技术的唯一手段，如何保证多个副本之间的一致性是整个分布式系统的理论核心

从客户端角度看，一致性有三种情况：

• 强一致性：假如A先写入了一个值到存储系统，存储系统保证后续A、B、C的读取操作都将返回最新值
• 弱一致性：假如A先写入了一个值到存储系统，存储系统不能保证后续A、B、C的读取操作都将返回最新值
• 最终一致性：是弱一致性的一种特例。假如A先写入一个值到存储系统，存储系统保证如果后续没有写操作更新同样的值， A、B、C的读取操作『最终都会读取到A写入的最新值』。『最终』有一个『不一致窗口』的概念，它特指从A写入值，到后续A、B C读取到最新值的这段时间。 最终一致性变体： - 读写（raed-your-writes）一致性：如果A写入最新值，A的后续操作会读取导致最新值。但是其他用户可能要过一会能看到 - 会话（session）一致性：要求客户端和存储系统交互的整个会话保持读写一致性。 - 单调读（monotonic read）一致性：A已经读取到对象的某个值，后续操作不会读取更早的值 _ 单调写（monotonic write）一致性：A的写操作按顺序完成，对同一个客户端的操作，存储系统的多个副本需要按照与客户端相同 的顺序完成。

从存储系统的角度看，一致性主要包括几个方面： - 副本一致性:存储系统的多个副本之间的数据是否一致，不一致的时间窗口等 - 更新顺序一致性：存储系统的多个副本之间是否按照相同的顺序执行更新操作

衡量指标： - 性能：吞吐能力、响应时间。权衡两个指标 - 可用性:面对各种异常可以提供正常服务的能力，整体代码质量和容错能力。采用四个9衡量 - 一致性:越是强的一致性，用户使用起来越简单 - 可扩展性：扩展集群服务器规模来提高系统存储容量、计算量和性能的能力。理想是『线性可扩展』

3.3 数据分布 哈希分布：一致性哈希，Dynamo系统。根据数据项的特征计算哈希值，然后和集群中的服务器建立映射关系。元数据服务器、一致性哈希 顺序分布：每张表格上的数据按照主键整体有序 负载均衡：总控节点与工作节点。

3.4 复制 通过复制协议将数据同步到多个存储节点，并确保多个副本之间的数据一致性 强同步协议：提供了强一致性，但是备副本出现问题将阻塞写操作。可用性较差 异步复制：可用性较好，一致性较差 复制通过操作日志来实现。 一致性与可用性：CAP定理 - 一致性：读操作总是能读取到之前完成的写操作结果，满足这个条件的系统成为强一致性系统，『之前』一般针对同一个客户端而言 - 可用性：读写操作在单台服务器发生故障时仍能正常执行，而不需要等待发生故障的机器重启或者其上的服务迁移到其他机器。 - 分区容忍性：机器故障、网络故障、机房停电等异常情况下仍能够满足一致性和可用性。(总是要满足)

3.5 容错 故障检测：心跳检测。 租约机制 故障恢复：单层结构和双层结构。总控节点高可用，选主或者维护系统中重要的全局信息，可以使用通过Paxos协议实现的分布式锁服务（zookeeper）

3.6 可扩展性

3.6.1 总控节点 用于维护数据分布信息，执行工作机器管理，数据定位，故障检测和恢复，负载均衡等全局调度工作。

3.6.2 数据库扩容 数据库可扩展性实现包括：通过主从复制提高系统的读取能力，通过垂直拆分和水平拆分姜数据库分布到多个存储节点，通过主从复制 将系统扩展到多个数据中心。

3.6.3 异构系统 同构系统：同一个组内的节点服务相同的数据。出现故障后拷贝数据比较耗时，不适合大规模分布式存储系统 异构系统：将数据划分为很多个大小接近的分片，每个分片的副本可以分布到集群中的任何一个存储借节点。如果某个 节点发生故障，原有的服务由整个集群而不是某个固定的存储节点来恢复。

3.7 分布式协议 3.7.1 两阶段提交协议（Two-phase commit，2pc）阻塞协议:用于保证属于多个数据分片上的操作的原子性。 一般包含两类节点：协调者，事务参与者 1：请求阶段(Prepare phase)：协调者通知事务参与者准备提交或取消事务，然后进入表决过程。表决过程中参与者告诉协调者自己的决策： 同意（事务参与者本地执行成功）或者取消（事务参与者本地执行失败） 2： 提交阶段(commit phase): 协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者 才通知所有的参与者提交事务。

可能面临两种故障： - 事务参与者发生故障:给每个事务设置超时时间 - 协调者发生故障：协调者需要将事务相关记录到操作日志并同步到备用协调者

3.7.2 Paxos协议 用于解决同一分片多个节点之间的一致性问题。多个节点之间通过操作日志同步数据，如果只有一个节点为主节点，很容易保证多个节点之间 操作日志的一致性。考虑到主节点可能出现故障，系统要选举出新的主节点。Paxos 协议用来实现此需求。保证多个节点之间操作日志的 一致性。为了实现高可用，主节点往往将数据以操作日志的形式同步到备用借点。如果主节点故障，备用借点会提议自己成为主节点。 问题时网络分区的时候，可能会存在多个备节点提议（Proposer，提议者）自己成为主节点。Paxos协议保证，即使同时存在多个 proposer，也能够高正所有节点最终达成一致。，选出唯一的主节点。

Paxos协议执行步骤： 1.批准：Proposer发送accept 消息到所有其他节点(acceptor)接受某个提议值，acceptor 可以接受或者拒绝。 2.确认:超过一般的 acceptor 接受，提议生效。proposer 发送 acknowledge 消息通知所有acceptor 提议生效。

考虑问题： 正确性：只有一个提议值会生效。paxos中要求每个每个生效的提议被acceptor中多数派接受，并且每个acceptor不会接受两个不同的提议 ，可以保证正确性。 可终止性：最后总有一个协议值会生效.不能完全保证可终止性，但是会往『某个提议被多数接受并生效』靠拢

3.8 跨机房部署 数据同步及服务切换。三方案：

• 1.集群整体切换：强同步或者异步
• 2.单个集群跨机房：单个集群部署到多个机房，允许不同分片的主副本位于不同的机房
• 3.Paxos选主副本。总控节点与工作节点之间不需要保持租约。能降低对总控节点的依赖，缺点是工程复杂

4.分布式文件系统

主要功能：存储图像之类的Blob类型数据；另外一个是作为分布式表格系统的持久化层。 4.1 Google 文件系统（GFS） 最主要的应用：MapReduce 与 Bigtable 关键问题：

• 租约机制：将chunk写操作授权给ChunkServer
• 一致性模型：GFS主要为追加而不是改写操作设计的。

4.2 Taobao File System(TFS) 设计思路：多个逻辑图片文件共享一个物理文件 一个 TFS 集群由2个 NameServer（一主一备）和多个 DataServer 节点组成

4.3 Facebook Haystack 主要包含三个部分：目录、存储和缓存

4.4 内容分发网络（CDN）

5.分布式键值存储

5.1 Amazon Dynamo 主要用于亚马逊购物车和S3 云存储(p2p架构) 采用改进的一致性哈希将数据存储在多个存储节点 Gossip协议用于p2p系统中自治的节点协调对整个集群的认识（借点状态、负载情况 容错：数据回传；Merkle树同步；读取修复 存储节点包括三个组件：请求协调；成员和故障检测；存储引擎

5.2 淘宝 Tair 一个中心控制节点和若干个服务节点组成 关键问题： - 数据分布：根据主见计算hash后分布到Q 个桶 - 容错：config server 提升副本为主副本 - 数据迁移：转发与路由 - config server：每次路由的变更，config server会将最新的配置信息推给 data server - data server：默认包含两个存储引擎Mdb 和 Fdb

6.分布式表格系统

对外提供表格模型，每个表格由很多行组成，通过主键唯一标识，每一行包含很多列。整个表格在系统中全局有序

6.1 Google Bigtable 设计理念：构建在廉价硬件之上，通过软件层面提供自动化容错和限行扩展能力 架构：

• 客户端程序库：通过 Chubby 锁服务获取一些控制信息。
• 主控服务器：管理所有的子表服务器
• 子表服务器：实现子表的装载/卸出、表格内容的读写，子表的合并与分裂。

6.2 Google Megastore 介于传统关系型数据库和 Nosql 之间的存储技术 架构： - 客户端库 - 复制服务器 - 协调者

6.3 Winsow AZure Storage(WAS) 主要包括两个部分：

• 定位服务：管理存储区，映射关系
• 存储区: 一个集群，一般包含10-20个机架，每个机架18个存储节点提供大约2pb容量。分3层：文件流层，分区层，前端层()

7章：分布式数据库

7.1 数据库中间层 应用层按照规则将数据拆分为多个分片，分布到多个数据库节点，引如一个中间层来屏蔽数据库拆分细节 架构： - mysql客户端库 - 中间层dbproxy：解析SQL 请求并转发到后端的数据库。具体是解析mysql协议，执行sql路由、sql过滤、读写分离、 结果归并、排序以及分组等。可以在客户端与中间层之间引入LVS，或者直接在客户端配置中间层服务器列表 - 数据库组dbgroup：每个dbgroup 由N台数据库极其组成，一个为主机（Master），另外N-1台为备机(Slave)。主机 负责所有的写事务及强一致读事务，并将操作以binlog 的形式复制到slave，slave 可以支持一定延迟的读事务。 - 元数据服务器：维护dbgroup拆分规则并用于dbgroup选主。常见采用zookeeper实现 - 常驻进程agents：部署在每台数据库服务器上的常驻进程，用于实现监控、单点切换、安装、卸载程序等。

7.2 Microsoft SQL Azure 架构: - sql server 实例 - 全局分区管理器 - 协议网关 - 分布式基础部件

7.3 Google Spanner

8章：OceanBase架构初探