互联网催生NoSql

1、互联网催生互联网催生nosql 张云浩张云浩sql的困境与的困境与nosql的兴起的兴起 nosql的基本概念的基本概念 nosql的关键技术的关键技术 nosql的现状分析的现状分析 nosql的优势及挑战的优势及挑战 3sql的困境与的困境与nosql的兴起的兴起sqlsql的困境的困境mysqlmysqlmemcached+mysql读写分离读写分离分表分库分表分库199020022003web2.0低延迟的读写速度支持海量数据和流量ab低成本d大规模集群的管理c导致7nosql的基本概念的基本概念 cap理论 9nosql的基本概念的基本概念 acid vs basic acidato

2、micity 原子性consistency 一致性isolation 隔离性 durability 持久性basebasically available 基本可用soft state 软状态eventually consistent 最终一致性强一致性隔离性专注于“提交”嵌套的事务可用性要求低比较保守很难进化弱一致性首先考虑可用性近似的结果激进简单快容易进化11nosql的基本概念的基本概念 最终一致性 强一致性强一致性弱一致性弱一致性最终一致性最终一致性假如假如process a写入了一个值写入了一个值到存储系统，到存储系统，存储系统保证存储系统保证后续后续a、b和和c的读取操作都的读取操作

3、都将返回最新值。将返回最新值。 假如假如processa写写入了一个值到入了一个值到存储系统，存存储系统，存储系统不能保储系统不能保证后续证后续a、b和和c的读取操作都的读取操作都将返回最新值。将返回最新值。 假如a首先写了一个值到存储系统，存储系统保证如果在a、b和c后续读取之前没有其他写操作同样的值的话，最终所有的读取操作都会读取到a写入的最新值。 因果一致性因果一致性read-your-write consistency session consistency monotonic read consistency monotonic write consistency 14nosql的关

4、键技术的关键技术 哈希表（hash table） logologo基本概念基本概念1构造哈希函数的方法构造哈希函数的方法2处理冲突的方法处理冲突的方法3查找的性能分析查找的性能分析416nosql的关键技术的关键技术 分布式哈希表（distributed hash table） 18nosql的关键技术的关键技术 paxos logologophase 1aphase 1bphase 2aphase 2b prepareproposer (当时的当时的leader) 选择选择一个编号一个编号n，发送发送prepare消消息给所有息给所有acceptor的的某个子集某个子集（quorum）pro

5、miseaccept！accepted20nosql的关键技术的关键技术 分布式数据处理 mapreduce23nosql现状分析现状分析 一种典型分类25几种典型的几种典型的nosql数据库数据库 分布式数据表bigtable为什么需要设计bigtable？ google需要存储的数据种类繁多 网页，地图数据，邮件 如何使用统一的方式存储各类数据？ 海量的服务请求 如何快速地从海量信息中寻找需要的数据？bigtable：基于gfs和chubby的分布式存储系统 对数据进行结构化存储和管理 与gfs的联系26数据存储可靠性高速数据检索与读取存储海量的记录（若干tb）可以保存记录的多个版本27与

6、写操作相比，数据记录读操作占绝大多数工作负载单个节点故障损坏是常见的磁盘是廉价的可以不提供标准接口 google既能控制数据库设计，又能进行应用系统设计28具有广泛的适应性 支持google系列产品的存储需求具有很强的可扩展性 根据需要随时加入或撤销服务器 应对不断增多的访问请求高可用性 单个节点易损，但要确保几乎所有的情况下系统都可用简单性 简单的底层系统可减少系统出错概率，为上层开发带来便利29总体上，与关系数据库中的表类似row keytime stampcolumn contentscolumn anchorcolumn “mime”my.look.ca“n.www”t9cnnt8cn

7、n.comt6“. “text/htmlt5“. “t3“. “30关系数据库中的表是什么样的？有什么特征？关系数据库中的表设计需要遵循什么原则？行 每行数据有一个可排序的关键字和任意列项 字符串、整数、二进制串甚至可串行化的结构都可以作为行键 表按照行键的“逐字节排序”顺序对行进行有序化处理 表内数据非常稀疏，不同的行的列的数完全目可以大不相同 url是较为常见的行键，存储时需要倒排 统一地址域的网页连续存储，便于查找、分析和压缩/index.asp/index.asp31列 特定含义的数据的集合，如图片、链接等 可将多个列归并为一组，称为族（family） 采用 族:限定词 的语法规则进行

8、定义 fileattr:owning_group”, “fileattr:owning_user”, etc 同一个族的数据被压缩在一起保存 族是必须的，是bigtable中访问控制的基本单元32时间戳 保存不同时期的数据，如“网页快照”“a big table” 表中的列可以不受限制地增长 表中的数据几乎可以无限地增加通过(row, col, timestamp)查询通过(row, col, most_recent)查询33无数据校验 每行都可存储任意数目的列 bigtable不对列的最少数目进行约束 任意类型的数据均可存储 bigtable将所有数据均看作为字符串 数据的有效性校验由构建于

9、其上的应用系统完成一致性 针对同一行的多个操作可以分组合并 不支持对多行进行修改的操作符34row keytime stampcolumn: contentscn.wwwt6“.”t5“.”t3“.”row keytime stampcolumn: anchorcn.wwwt9anchor:cnnt5anchor:my.look.cacnn.comrow keyrow keytime stamptime stampcolumn:column: mime mimecn.wwwt6text/htmlrow keytime stampcolumn contentscolumn anchorcolum

10、n “mime”my.look.ca“n.www”t9cnnt8cnn.comt6“. “text/htmlt5“. “t3“. “35逻辑上的“表”被划分为若干子表（tablet） 每个tablet由多个sstable文件组成 sstable文件存储在gfs之上每个子表存储了table的一部分行 元数据：起始行键、终止行键 如果子表体积超过了阈值（如200m），则进行分割3637为每个子表服务器分配子表，对外提供服务与gfs垃圾回收进行交互，收回废弃的sstable探测子表服务器的故障与恢复负载均衡有效缓解单点故障3839404142任何对子表的写操作都会记录到一个存储在gfs之上的comm

11、it log中 每个子表服务器上所有子表变化对应于一个commit log新的数据存储到子表服务器的内存（memtable）中次压缩 旧数据存储在sstable中，而新数据存放在memtable中 当memtable体积超过一定阈值，将形成sstable，并写入gfs 每个tablet对应多个sstable43tablet含有多个sstable导致查询效率低合并压缩操作读取多个sstable，创建一个新的sstable来保持其中的最新数据 旧的sstable删除 如果合并压缩操作完成后，tablet只包含一个sstable，那么该操作也称为主压缩4445新的故障 子表服务器内存中的memtab

12、le丢失恢复方法 按照tablet将该服务器对应的日志分片 为每个失效tablet分配新的子表服务器 新子表服务器读取对应的分段commit log，并按照日志修改tablet 删除commit log中已实施的内容 重新对外提供服务46局部性群组(locality group) 根据需要，将原本不存储在一起的数据，以列族为单位存储至单独的子表 如用户对网站排名、语言等分析信息感兴趣，那么可以将这些列族放至单独的子表，减少无用信息读取，改善存取效率布隆过滤器(bloom filter) 什么是布隆过滤器？判断某个元素是否隶属于集合 优点：误判概率低，其存储空间仅为hash表的1/8至1/4 用

13、于判断列键是否位于sstable中，快速确定某个列键的位置474849几种典型的几种典型的nosql数据库数据库 基础架构存储dynamo50dynamo在amazon服务平台中的地位dynamo架构的主要技术问题问题采取的相关技术采取的相关技术数据均衡分布改进的一致性哈希算法，数据备份数据冲突处理向量时钟（vector clock）临时故障处理hinted handoff（数据回传机制），参数（w,r,n）可调的弱quorum机制永久故障后的恢复merkle哈希树成员资格以及错误检测基于gossip的成员资格协议和错误检测一致性哈希算法优势： -负载均衡 -屏蔽节点处理能力差异最终一致性模型向量时钟 （vector clock）读写参数w、r、nn：系统中每条记录的副本数w：每次记录成功写操作需要写入的副本数r：每次记录读请求最少需要读取的副本数。满足r+wn，用户即可自行配置r和w优势：实现可用性与容错性之间的平衡