互联网催生互联网催生NoSql 张云浩张云浩内容内容Sql的困境与的困境与NoSql的兴起的兴起 NoSql的基本概念的基本概念 NoSql的关键技术的关键技术 NoSql的现状分析的现状分析 NoSql的优势及挑战的优势及挑战 3Sql的困境与的困境与NoSql的兴起的兴起SqlSql的困境的困境关系数据库关键技术使用顺序关系数据库关键技术使用顺序MySqlMySqlMemcached+MySql读写分离读写分离分表分库分表分库199020022003Web2.0当前应用对数据存储的四个要求当前应用对数据存储的四个要求低延迟的读写速度支持海量数据和流量AB低成本D大规模集群的管理C关系数据库天生的几个限制关系数据库天生的几个限制NoSqlNoSql数据库迎来了新的机遇数据库迎来了新的机遇导致扩展困难扩展困难扩展困难扩展困难读写慢读写慢读写慢读写慢成本高成本高成本高成本高容量有限容量有限容量有限容量有限7NoSql的基本概念的基本概念 CAP理论 CAPCAP理论理论9NoSql的基本概念的基本概念 ACID vs BASIC 表1-1 ACID和BASE的特性ACIDAtomicity 原子性Consistency 一致性Isolation 隔离性 Durability 持久性BASEBasically Available 基本可用Soft state 软状态Eventually consistent 最终一致性强一致性隔离性专注于“提交”嵌套的事务可用性要求低比较保守很难进化弱一致性首先考虑可用性近似的结果激进简单快容易进化11NoSql的基本概念的基本概念 最终一致性 强一致性强一致性弱一致性弱一致性最终一致性最终一致性假如假如Process A写入了一个值写入了一个值到存储系统，到存储系统，存储系统保证存储系统保证后续后续A、B和和C的读取操作都的读取操作都将返回最新值。将返回最新值。 假如假如ProcessA写写入了一个值到入了一个值到存储系统，存存储系统，存储系统不能保储系统不能保证后续证后续A、B和和C的读取操作都的读取操作都将返回最新值。将返回最新值。 假如A首先写了一个值到存储系统，存储系统保证如果在A、B和C后续读取之前没有其他写操作同样的值的话，最终所有的读取操作都会读取到A写入的最新值。 最终一致性最终一致性最终一致性最终一致性“ “变体变体” ”因果一致性因果一致性Read-your-write consistency Session consistency Monotonic read consistency Monotonic write consistency 变体变体变体变体14NoSql的关键技术的关键技术 哈希表（Hash Table） www.themegallery.comLOGO哈希表哈希表基本概念基本概念1构造哈希函数的方法构造哈希函数的方法2处理冲突的方法处理冲突的方法3查找的性能分析查找的性能分析416NoSql的关键技术的关键技术 分布式哈希表（Distributed Hash Table） 18NoSql的关键技术的关键技术 Paxos www.themegallery.comLOGOPaxosPaxos算法简介算法简介Phase 1aPhase 1bPhase 2aPhase 2b PrepareProposer (当时的当时的leader) 选择选择一个编号一个编号N，发送，发送Prepare消息消息给所有给所有Acceptor的的某个子集某个子集（quorum）PromiseAccept！Accepted20NoSql的关键技术的关键技术 分布式数据处理 MapReduceMapReduceMapReduce的运行模型的运行模型MapReduceMapReduce的执行流程图的执行流程图23NoSql现状分析现状分析 一种典型分类CAPCAP理论理论25几种典型的几种典型的NoSql数据库数据库 分布式数据表BigTableBigTableBigTable为什么需要设计BigTable？Google需要存储的数据种类繁多网页，地图数据，邮件如何使用统一的方式存储各类数据？海量的服务请求如何快速地从海量信息中寻找需要的数据？BigTable：基于GFS和Chubby的分布式存储系统对数据进行结构化存储和管理与GFS的联系26数据存储可靠性高速数据检索与读取存储海量的记录（若干TB）可以保存记录的多个版本GoogleGoogle的需求的需求27与写操作相比，数据记录读操作占绝大多数工作负载单个节点故障损坏是常见的磁盘是廉价的可以不提供标准接口Google既能控制数据库设计，又能进行应用系统设计假设假设28具有广泛的适应性支持Google系列产品的存储需求具有很强的可扩展性根据需要随时加入或撤销服务器应对不断增多的访问请求高可用性单个节点易损，但要确保几乎所有的情况下系统都可用简单性简单的底层系统可减少系统出错概率，为上层开发带来便利设计目标设计目标29总体上，与关系数据库中的表类似逻辑视图逻辑视图Row KeyTime StampColumn ContentsColumn AnchorColumn “mime”cnnsi.commy.look.ca“com.cnn.www”T9CNNT8CNN.COMT6“. “Text/htmlT5“. “t3“. “30关系数据库中的表是什么样的？有什么特征？关系数据库中的表设计需要遵循什么原则？行每行数据有一个可排序的关键字和任意列项字符串、整数、二进制串甚至可串行化的结构都可以作为行键表按照行键的“逐字节排序”顺序对行进行有序化处理表内数据非常稀疏，不同的行的列的数完全目可以大不相同URL是较为常见的行键，存储时需要倒排统一地址域的网页连续存储，便于查找、分析和压缩数据模型数据模型mp3.baidu.commp3.baidu.commp3.baidu.commp3.baidu.com/index.aspcom.baidu.mp3com.baidu.mp3com.baidu.mp3com.baidu.mp3/index.asp31列特定含义的数据的集合，如图片、链接等可将多个列归并为一组，称为族（family）采用 族:限定词 的语法规则进行定义fileattr:owning_group”, “fileattr:owning_user”, etc同一个族的数据被压缩在一起保存族是必须的，是BigTable中访问控制的基本单元数据模型数据模型32时间戳保存不同时期的数据，如“网页快照”“A big table”表中的列可以不受限制地增长表中的数据几乎可以无限地增加数据模型数据模型通过(row, col, timestamp)查询通过(row, col, MOST_RECENT)查询33无数据校验每行都可存储任意数目的列BigTable不对列的最少数目进行约束任意类型的数据均可存储BigTable将所有数据均看作为字符串数据的有效性校验由构建于其上的应用系统完成一致性针对同一行的多个操作可以分组合并不支持对多行进行修改的操作符数据模型数据模型34物理视图物理视图Row KeyTime StampColumn: ContentsCom.cnn.wwwT6“.”T5“.”T3“.”Row KeyTime StampColumn: AnchorCom.cnn.wwwT9Anchor:cnnsi.comCNNT5Anchor:my.look.caCNN.COMRow KeyRow KeyTime StampTime StampColumn: mimeColumn: mimeCom.cnn.wwwT6text/htmlRow KeyTime StampColumn ContentsColumn AnchorColumn “mime”cnnsi.commy.look.ca“com.cnn.www”T9CNNT8CNN.COMT6“. “Text/htmlT5“. “t3“. “35逻辑上的“表”被划分为若干子表（Tablet）每个Tablet由多个SSTable文件组成SSTable文件存储在GFS之上每个子表存储了table的一部分行元数据：起始行键、终止行键如果子表体积超过了阈值（如200M），则进行分割物理视图物理视图36体系结构体系结构37为每个子表服务器分配子表，对外提供服务与GFS垃圾回收进行交互，收回废弃的SSTable探测子表服务器的故障与恢复负载均衡主节点的职责主节点的职责有效缓解单点故障38子表服务器故障子表服务器故障39子表服务器故障子表服务器故障40子表服务器故障子表服务器故障41数据访问方式数据访问方式42任何对子表的写操作都会记录到一个存储在GFS之上的commit log中每个子表服务器上所有子表变化对应于一个commit log新的数据存储到子表服务器的内存（memtable）中次压缩旧数据存储在SSTable中，而新数据存放在memtable中当memtable体积超过一定阈值，将形成SSTable，并写入GFS每个tablet对应多个SSTable数据写的流程数据写的流程43tablet含有多个SSTable导致查询效率低合并压缩操作读取多个SSTable，创建一个新的SSTable来保持其中的最新数据旧的SSTable删除如果合并压缩操作完成后，tablet只包含一个SSTable，那么该操作也称为主压缩合并压缩合并压缩44数据存储与读取流程数据存储与读取流程45新的故障子表服务器内存中的memtable丢失恢复方法按照tablet将该服务器对应的日志分片为每个失效tablet分配新的子表服务器新子表服务器读取对应的分段commit log，并按照日志修改tablet删除commit log中已实施的内容重新对外提供服务子表服务器故障恢复子表服务器故障恢复46局部性群组(Locality Group)根据需要，将原本不存储在一起的数据，以列族为单位存储至单独的子表如用户对网站排名、语言等分析信息感兴趣，那么可以将这些列族放至单独的子表，减少无用信息读取，改善存取效率布隆过滤器(Bloom Filter)什么是布隆过滤器？判断某个元素是否隶属于集合优点：误判概率低，其存储空间仅为Hash表的1/8至1/4用于判断列键是否位于SSTable中，快速确定某个列键的位置性能优化性能优化47BigTableBigTable小结小结4849几种典型的几种典型的NoSql数据库数据库 基础架构存储Dynamo50基础存储架构基础存储架构DynamoDynamoDynamo在Amazon服务平台中的地位Dynamo架构的主要技术问题问题采取的相关技术采取的相关技术数据均衡分布改进的一致性哈希算法，数据备份数据冲突处理向量时钟（vector clock）临时故障处理Hinted handoff（数据回传机制），参数（W,R,N）可调的弱quorum机制永久故障后的恢复Merkle哈希树成员资格以及错误检测基于gossip的成员资格协议和错误检测数据均衡分布的问题数据均衡分布的问题一致性哈希算法优势： -负载均衡 -屏蔽节点处理能力差异DynamoDynamo的数据冲突处理的数据冲突处理最终一致性模型向量时钟 （Vector Clock）DynamoDynamo的临时故障处理机制的临时故障处理机制读写参数W、R、NN：系统中每条记录的副本数W：每次记录成功写操作需要写入的副本数R：每次记录读请求最少需要读取的副本数。满足R+WN，用户即可自行配置R和W优势：实现可用性与容错性之间的平衡DynamoDynamo的永久性故障恢复的永久性故障恢复Merkle哈希树技术Dynamo中Merkle哈希树的叶子节点是存储数据所对应的哈希值，父节点是其所有子节点的哈希值成员资格及错误检测成员资格及错误检测基于Gossip协议的成员检测机制56NoSql的优势及挑战的优势及挑战 NoSql的五大优势NoSqlNoSql的五大优势的五大优势灵活的扩展性适合大数据 无需DBA数据存储处理价格低廉数据模型灵活58NoSql的优势及挑战的优势及挑战 NoSql的五大劣势NoSqlNoSql的五大劣势的五大劣势成熟度低技术支持较少偏向web2应用而企业应用偏少离“零距离管理”还差距很大知名度低