大规模高性能分布式存储系统（2月25日）

--高扩展性，指分布式存储系统通过扩展集群服务器规模从而提高系统存储容量、计算和性能的能力；业务量增大，对底层分布式存储系统的性能要求越来越高，自动增加服务器来提升服务能力；Scale Up与Scale Out，线性可扩展，系统整体性能与服务器数量呈线性关系

--数据一致性，分布式存储系统多个副本之间的数据一致性，强一致性、弱一致性、最终一致性、因果一致性、顺序一致性

--高安全性，指分布式存储系统不受恶意访问和攻击，保护存储数据不被窃取；互联网是开放的；任何人在任何时间任何地点通过任何方式都可以访问网站；针对现存的和潜在的各种攻击与窃取手段，要有相应的应对方案

--高性能，衡量分布式存储系统性能常见的指标是系统的吞吐量和系统的响应延迟，系统的吞吐量，在一段时间内可以处理的请求总数，QPS（Query Per Second）和TPS（Tra-nsaction Per Second）；系统的响应延迟，指某个请求发出到接收到返回结果所消耗的时间，通常用平均延迟来衡量；衡量分布式存储系统性能常见的指标是系统的吞吐量和系统的响应延迟；这两个指标往往是矛盾的，追求高吞吐量，比较难做到低延迟；追求低延迟，吞吐量受影响；

--高稳定性，综合指标，考核分布式存储系统的整体健壮性，任何异常，系统都能坦然面对，系统稳定性越高越好

软硬件环境准备：

-基础软硬件环境

--硬件：物理机尽量4G内存

--OS：CentOS5.9及以上64位

--HDFS（hadoop）：2.0.0及以上64位

--Redis：2.0.0及以上64位

--MongoDB：2.0.0及以上64位

--工具软件：VIM、SecureCRT等

大规模高性能分布式存储原理与设计

1、单机存储原理与设计

单机存储引擎，存储引擎是存储系统的发动机，决定了存储系统能够提供的功能和性能；存储系统提供的功能：Create、Update、Read、Delete（CURD）；存储引擎类型：哈希存储引擎；B树存储引擎；LSM存储引擎

哈希存储引擎：基于哈希结构的键值存储系统，数值+链表，支持Create、Update、随机Read、Delete，O(1)Read复杂度

B树存储引擎：基于B Tree实现，支持单条记录的CURD，还支持顺序扫描、范围查找；RDBMS使用较多：MySQL、InnoDB聚簇索引、B+树

LSM树存储引擎：Log Structured Merge Tree，对数据的修改增量保存在内存中，达到指定条件后（通常是数量和时间间隔），批量将更新操作持久到磁盘；读取数据时需要合并磁盘中的历史数据和内存中最近修改操作；LSM优势在于通过批量写入，规避了随机写入问题，提高写入性能；LSM劣势在于读取需要合并磁盘数据和内存数据；如何避免内存数据丢失？-Commit Log；首先将修改操作写入到Commit Log中，操作数据的可靠性保证；典型案例设计：LevelDB

数据模型：数据模型是存储系统外壳，数据模型分类：文件、关系、key-value、列存储、图形、文档

1、文件，以目录树的方式组织文件 Linux、Mac、Windows

2、关系型，每个关系是一个表格，由多行组成，每个行由多个列组成，MySQL、Oracle等

3、键值（key-value）存储型，Memcached（仅作缓存使用）、Tokyo Cabinet、Redis（有持久化功能）等

4、列存储型：Cassadra、HBase

5、图形（Graph）数据库：Neo4J、InfoGrid、Infinite Graph

6、文档型（KV型的升级）：MongoDB、CouchDB

事务与并发控制

-事务四个基本属性：原子性、一致性、隔离性、持久性

-并发控制：锁粒度、Process->DB->Table->Row，提供Read并发，Read不加锁，写时复制，MVCC

数据恢复：操作日志

2、多机存储原理与设计

-单机存储与多机存储，单机存储的原理在多机存储仍然可用，多机存储基于单机存储

-多机数据分布，区别于单机存储，数据分布在多个节点上，在多个节点之间需要实现负载均衡，数据分布方式：静态方式（取摸、uid%32）；动态方式（一致性hash、数据漂移问题）

动态和静态的区别是，当有机器挂机时，数据可以做一些动态的调整，静态分布不能动态调整，需要人工做一些调整

一致性hash也会有数据漂移的情况，例如发生网络抖动，在节点A上存储了一些数据，发生抖动后，数据迁移到B节点上，这时候在B节点上发生更新操作，更新操作结束后，网络恢复，A节点可以继续提供服务，这个时候B节点上做了更新操作，A上没有，可能会造成脏数据的情况，在hash算法中需要重点解决这个问题

-负载均衡，多节点之间数据的均衡，负载高的节点迁移到负载低的节点，数据迁移，MongoDB Auto-Sharding（当发现某个节点数据比较多，就会启动balance，balance随时随地进行，哪怕请求处于高峰期，因此对online请求造成影响）；如何迁移，MongoDB、自动迁移、问题、指定迁移时间点

-复制，分布式存储多个副本；保证了高可靠和高可用；Commit Log；

-故障检测：心跳机制、数据迁移、故障恢复

3、FLP定理与设计

FLP Impossibility（FLP不可能性）是分布式领域中一个非常著名的结果；1985年Fischer、Lynch and Patterson三位作者发表论文，并获取Dijkstra奖；在异步消息通信场景，即使只有一个进程失败，没有任何方法能够保证非失败进程达到一致性

FLP系统模型基于以下几个假设：

1、异步通信：与同步通信最大的区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序

2、通信健壮性：只要进程非失败，消息虽会被无限延迟，但最终会被送达，并且消息仅会被送达一次（重复保证）

3、Fail-Stop模型：进程失败不再处理任何消息

4、失败进程数量：最多一个进程失败

启示：1985年FLP证明了异步通信中不存在任何一致性的分布式算法（FLP impossibility），人们就开始寻找分布式系统设计的各种因素；一致性算法既然不存在，如果能找到一些设计因素，适当取舍以最大限度满足实现系统需求成为当时的重要议题，CAP定理出现

4、CAP定理与设计

2000年Berkerly的Eric Brewer教授提出了一个著名的CAP理论，一致性（Consistency）、可用性（Availability）、分区可容忍性（Tolerance of network Partition）

在分布式环境下，三者不可能同时满足：

一致性（Consistency）：Read的数据总是最新的（Write的结果）；强一致性

可用性（Availability）：机器或者系统那部分发生故障，仍然能够正常提供读写服务

分区容忍性（Tolerance of network Partition）：机器故障、网络故障、机房故障等异常情况下仍然能够满足一致性和可用性

分布式存储系统需要能够自动容错，也就是说分区容忍性需要保证

保证一致性：强同步复制，主副本网路异常，写操作被阻塞，可用性无法保证

保证可用性：异步复制机制；保证了分布式存储系统的可用性；强一致性无法保证

一致性和可用性需要折中权衡：不允许数据丢失（强一致性）：金融；小概率丢失允许（可用性）：消息

5、2PC协议与设计

Two Phase Commit（2PC），实现分布式事务，两类节点：协调者1个；事务参与者多个；每个节点都会记录Commit Log，保证数据可靠性；两阶段提交由两个阶段组成：请求阶段、提交阶段

两个阶段的执行过程：

1、请求阶段（Prepare Phase）：协调者通知参与者准备提交或者取消事务，之后进入表决阶段，每个参与者将告知协调者自己的决策（同意或不同意）

2、提交阶段（Commit Phase）：收到参与者的所有决策后，进行决策（提交或取消）；通知参与者执行操作，所有参与者都同意，提交；否则取消；参与者收到协调者的通知后执行操作；参与者收到协调者的通知后执行操作

2PC协议是阻塞式协议，事务参与者可能发生故障，设置超时时间；协调者可能发生故障，日志记录，备用协调者；应用：分布式事务；二手交易（商品库、订单库）

6、Paxos协议与设计

用于解决多个节点之间的一致性问题；多个节点，只有一个主节点；主节点挂掉，如果选举新的节点；主节点往往以操作日志的形式同步备节点

角色：提议者（Proposer）、接受者（Acceptor）

执行步骤：

1、批准（accept）：Proposer发送accept消息到Acceptor要求接受某个提议者

2、确认（acknowledge）：如果超过一半的Acceptor接受，意味着提议值生效，Proposer发送acknowledge消息通知所有的Acceptor提议生效

2PC与Paxos的不同：

1、作用不同：2PC协议保证多个数据分片上操作的原子性；Paxos协议保证一个数据分片多个副本之间的数据一致性

2、Paxos协议用法：实现全局的锁服务或者命名和配置服务：Apache Zookeeper；将用户数据复制到多个数据中心：Google Megastore

3、2PC和Paxos：2PC最大缺陷无法处理协调者宕机；Paxos可以处理协调者宕机；两者结合使用

第三讲：典型分布式存储系统分析对比

1、GFS

使用场景：

Google File System，为存储海量搜索数据设计的文件系统；可扩展的分布式文件系统；运行于廉价的普通硬件；提供容错功能；提供总体性能较高服务

基于假设，基于普通PC，单机不可靠，集群能检测和恢复；存储较多的大文件（几十M～几个GB），大量的顺序读，小量的随机读；直接APPEND（末尾追加），带宽要求高

使用场景：海量大文件、海量读、不修改文件、高并发、网页数据、视频（非直播）、日志

架构设计：

1、GFS master：元数据服务节点，一个，负责维护GFS的元数据，命名空间，访问控制，文件和块映射，块存储节点，垃圾回收，负载均衡，心跳（获取chunkserver的心跳，处理）

2、GFS chunkserver：数据存储节点，多个，大文件分为多个块，每个块有个64位ID，每块存储在chunkserver上，可靠性（副本，3个，分布在不同chunkserver上），64M（元数据大小，交互次数）

3、GFS client：客户端节点，多个，应用方嵌入client代码，Client作为代理与GFS master和GFS chunkserver交互

读取数据流程：

1、client指定读取某个文件的某段数据，因为数据块是定长，client计算包含几个数据块，client将file name、chunk index发给master；

2、master根据file name查找命名空间和文件->块映射表，得到需要的数据块副本地址，master将chunk handle，chunk locations所有副本的地址反馈给client

3、client选择一个副本，和chunkserver交互，获取数据

4、chunkserver获取数据返回给client

client会做数据的预取和缓存

2、HDFS

HDFS：Hdoop的一部分，另一部分并行计算组成，Map-Reduce框架，离线请求，HDFS是GFS的一个开源实现版本，按照GFS设计实现，Apache组织管理，

Yahoo，amazon，eby，alibaba，baidu，tencent，58......都在支持

使用场景：

1、超大文件：100M～G～T

2、基于流式数据访问，一次写入，多次读取

3、高吞吐量：以数据延迟为代价

架构设计：

Namenode：元数据服务器节点，1个

Datanodes：数据存储服务器节点，多个，默认也会存储3份

Client：客户端节点，数据预取与缓存，嵌入到业务上去用，

整个系统采用Java语言开发

3、MongoDB

使用场景：

MongoDB from “humongous”，面向文档的NoSQL数据库，

举例“人"描述，RDBMS(People、Address) MongoDB(People)

可扩展（scalable）（主从方式扩展，副本级的形式）、高性能（high-performance）、开源（open source）NoSQL database

用C++写，10gen公司，开源社区支持

关键特性：Document-Oriented Storage面向文档存储，文档可以嵌套、Full Index Support最像关系型数据库、Replication & High Availability、Auto-Sharding、Rich Querying、Updates、Map/Reduce、GridFS

适用场景：web应用程序、敏捷开发、分析和日志、缓存、可变schema

架构设计：

1、跨平台：linux、unix、Mac、windows；整体架构相同

2、MongoDB Server：实例、数据库及其对应关系

3、数据逻辑结构：文档、集合、数据库

4、数据存储：元数据、实际数据

4、HBase

使用场景

架构设计