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

法律【

】

和幻灯片为炼数成金网络课程的教学资料，所有资料只能在课程内使用，不得在课程以外范围散播，违者将可能被

法律和经济责任。课程详情

炼数成金培训http:

关于我58同城系统架构师即时通讯、C2C技术技术

架构组前

高级工程师代表58同城多次对外嘉宾开发大会）开发大会）案例研究

）Qcon（全球SDCC（中国Top100（全球UPYUN、TINGYUN《程序员》撰稿–

……关于我2007年开始接触涉及自主研发分布式

系统MongoDBMySQLMecachedRedis……《MongoDB实战》已开课欢迎大家报名交流上次课程回顾授课形式目标课程内容概述（11节课）分布式

系统发展历史80年代->90年代->20世纪末->现在分布式

概念概念、特性分布式

分类数据类型、分布式

类型分布式

知识原理高可用、高可靠、高扩展、数据一致、高安全、高性能、高稳定

–

基础硬

准备

OutLine单机多机原理与设计原理与设计FLP定理与设计CAP定理与设计2PC协议与设计Paxos协议与设计•单机

原理与设计–

单机

引擎引擎是系统的发决定了

系统能够提供的功能和性能•系统提供功能–

Create、Update、Read、Delete（CURD）引擎类型哈希

引擎B树

引擎LSM

引擎单机

原理与设计哈希

引擎基于哈希表结构的键值

系统数组+链表支持Create、Update、Delete、随机ReadO(1)Read复杂度B树

引擎基于B

Tree实现支持单条记录的CURD还支持顺序扫描、范围查找RDBMS使用较多MySQLInnoDB聚簇索引B+树单机

原理与设计LSM树

引擎Log

Structured

Merge

Tree对数据的修改增量保存在内存中，达到指定条件后（通常是数量和时间间隔），批量将更新操作持久到磁盘数据时需要合并磁盘中的历史数据和内存中最近修改操作LSM优势在于通过批量写入，规避了随机写入问题，提高写入性能LSM劣势在于

需要合并磁盘数据和内存数据如何避免内存数据丢失？Commit

Log首先将修改操作写入到Commit

Log中操作数据的可靠性保证典型案例设计LevelDB系统外壳单机

原理与设计数据模型数据模型是数据模型分类文件关系Key-Value列图形文档每个关系是一个表格，由多个行组成，每个行由于多个列组成MySQL、Orcale等键值(Key-Value)

型Memcached、Tokyo

Cabinet、Redis列

型Cassadra、HBase图形(Graph)数据库Neo4J、InfoGrid、Infinite

Graph文档型MongoDB、CouchDB单机

原理与知识数据模型分类文件–

以关系型树的方式组织文件Linux、Mac、Windows单机

原理与设计事务与并发控制事务四个基本属性原子性一致性性持久性并发控制锁粒度Process->DB->Table->Row提供Read并发，Read不加锁»

写时»

MVCC数据恢复

•

操作日志

多机

原理与设计单机

与多机单机

的原理在多机

仍然可用多级

基于单机多机数据分布区别于单机数据分布在多个节点上，在多个节点之间需要实现负载均衡数据分布方式静态方式»

取模»

uid%32动态方式»

一致性hash»

数据飘移问题多机

原理与设计多机数据分布负载均衡多节点之间数据的均衡负载高的节点迁移到负载低的节点数据迁移MongoDB

Auto-Sharding如何迁移MongoDB自动迁移问题指定迁移时间点多机

原理与设计–分布式

多个副本保证了高可靠和高可用Commit

Log故障检测心跳机制数据迁移故障恢复FLP定理与设计FLPFLP

Impossibility（FLP不可能性）是分布式领域中一个非常著名的结果1985年

、Lynch

and

Patterson三位作者

，并获取Dijkstra奖在异步消息通信场景，即使只有一个进程失败，没有任何方法能够保证非失败进程达到一致性FLP系统模型基于以下几个假设异步通信»

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

只要进程非失败，消息虽会被无限延迟，但最终会被送达，并且消息仅会被送达一次（重复保证）Fail-Stop模型»

进程失败不再处理任何消息失败进程数量»

最多一个进程失败FLP定理与设计FLP定理带给

的启示1985年FLP证明了异步通信中不存在任何一致性的分布式算法（FLP

Impossibility）人们就开始寻找分布式系统设计的各种因素一致性算法既然不存在，如果能找到一些设计因素，适当取舍以最大限度满足实现系统需求成为当时的重要议题CAP定理出现CAP定理与设计CAP定理2000年Berkerly的Eric

Brewer教授提出了一个著名的CAP理论性(Tolerance

of

network

Partition)一致性(Consistency)、可用性(Availability)、分区可在分布式环境下，三者不可能同时满足一致性(Consistency)的（Write的结果）Read的数据总是强一致性可用性(Availabilty)–

机器或者系统部分发生故障，仍然能够正常提供读写服务分区

性(Tolerance

of

network

Partition)–

机器故障、网络故障、机房故障等异常情况下仍然能够满足一致性和可用性CAP定理与设计CAP分布式系统需要能够自动容错，也就是说分区性需要保证保证一致性强同步主副本网路异常，写操作被阻塞，可用性无法保证保证可用性异步

机制保证了分布式

系统的可用性强一致性无法保证一致性和可用性需要折中权衡不允许数据丢失（强一致性）»

金融小概率丢失允

用性）»

消息2PC协议与设计Two

Phase

Commit(2PC)实现分布式事务两类节点协调者»

1个事务参与者»

多个每个节点都会记录Commit

Log，保证数据可靠性两阶段提交由两个阶段组成请求阶段提交阶段2PC协议与设计两个阶段的执行过程请求阶段（Prepare

Phase）协调者通知参与者准备提交或者取消事务，之后进入表决阶段，每个参与者将告知协调者自己的决策»

同意»

不同意提交阶段（Commit

Phase）收到参与者的所有决策后，进行决策»

提交»

取消通知参与者执行操作»

所有参与者都同意，提交»

否则取消参与者收到协调者

后执行操作2PC协议与设计2PC协议是阻塞式事务参与者可能发生故障设置超时时间协调者可能发生故障日志记录备用协调者应用分布式事务二手交易商品库、订单库Paxos协议与设计Paxos协议用于解决多个节点之间的一致性问题多个节点，只有一个主节点主节点挂掉，如果

新的节点主节点往往以操作日志的形式同步备节点角色提议者（Proposer）接受者（Acceptor）执行步骤批准（accept）»

Proposer发送accept消息到Acceptor要求接受某个提议者确认(acknowledge)»

如果超过一半的Acceptor接受，意味着提议值生效，Proposer发送acknowledge消息通知所有的Acceptor提议生效2PC与Paxos作用不同2PC协议保证多个数据分片上操作的原子性Paxos协议保证一个数据分片多个副本之间的数据一致性Paxos协议用法实现全局的锁服务或者命名和配置服务–

Apache

Zookeeper将用户数据到多个数据中心Megastore–2PC和Paxos2PC最大缺陷无法处理协调者宕机Paxos可以处理协调者宕机两者结合使用本课总结单机

原理与设计多机

原理与设计FLP定理与设计CAP定理与设计2PC协议与设计Paxos协议与设炼数成金逆向

式网络课程Dataguru（炼数成金）是专业数据分析

，提供教育，，内容，社区，

，数据分析业务等服务。

的课程采用新兴的互联网教育形式，独创地发展了逆向。既继承传统教育重学习氛围，重竞争压力的特点，同时又发挥互联网的天南地北志同道合的朋友