《DDIA》笔记

Apr 25, 2018 21:00 · 3852 words · 8 minute read web 数据库 读书笔记

第一章:可靠性,可扩展性,可维护性

  • 许多应用程序都需要:数据库,缓存,搜索索引,流处理,批处理。
  • 三个软件系统中的重要问题:可靠性(在困境中仍能正常工作),可扩展性(应对系统的增长,数据量、流量、复杂性etc),可维护性(使系统保持现有行为,并适应新的应用场景)。
  • 故障:硬件故障,软件错误,人为错误。
  • 描述负载:负载参数(读写比率,用户量,缓存命中率etc),推特主页的时间线获取方式:1.查询关注用户的推文集合并按时间线合并。2.每个用户维护一个时间线缓存,发布推文时插入到所有关注者的推文集合。方法2的缺点:关注者数量庞大时写入次数非常多,解决方法:结合1和2,推拉结合。
  • 描述性能:吞吐量,响应时间。衡量响应时间的方式:算术平均值,中位数,p95,p99,p99.9,尾部延迟,排队延迟(头部阻塞)。
  • 应对负载的方法:水平扩展(将负载分布到更多机器,无共享架构),垂直扩展(转向更强大的机器)。
  • 可维护性:管理复杂度,保持简单性,抽象解耦,拥抱变化。

第二章:数据模型与查询语言

  • 1970提出的SQL数据模型:数据被组织成关系,其中每个关系是元组的无序集合。
  • SQL模型之间的阻抗不匹配:需要一个笨拙的转换层来处理行、列和数据对象的相互转换。
  • 文档数据库:层次模型:把数据表示为嵌套在记录中的记录树,具有自包含性。网络模型:访问记录的唯一方法是跟随从根记录起沿这些链路所形成的路径。
  • 图形数据库:任意事物都可能与任何事物相关联。
  • 数据查询语言:命令式语言:告诉计算机以特定顺序执行某些操作。声明式语言:指定所需数据的模式-结果必须符合哪些条件-如何将数据转换(例如,排序,分组和集合)。
  • 图数据模型:一个图由两种对象组成:顶点(实体)和边(关系)。
  • 属性图的声明式查询语言:Cypher。
  • 三元组存储(主语,谓语,宾语):SPARQL。

第三章:存储与检索

  • 存储引擎:日志结构(log-structured,案例:Bitcask,SSTables,LSM树,LevelDB,Cassandra,HBase,Lucene),面向页面(page-oriented,案例:B-Tree)。
  • 原始存储:往文件末尾追加键值记录。挑战:查找效率。
  • 哈希索引:用内存中的记录保存磁盘数据文件位置的偏移量。挑战:数据压缩(去重),删除记录,崩溃恢复,范围搜索。
  • SSTable:要求键值对序列按键排序,归并合并多个段,保持最新记录,特点:合并高效,查找效率高。
  • 构建和维护SSTable:写入时将记录添加到内存中的平衡树结构(也称作内存表,memtable),当内存表大小高于某个阈值,将其作为SSTable写入磁盘,之后再构建一个新的memtable实例。处理读取顺序:memtable中搜索->最近的磁盘段中搜索->更旧的磁盘段中搜索。问题:发生崩溃时,处于memtable中未写入磁盘的记录会丢失,解决方式:在磁盘保存一个写入日志(commit log),每个写入都会附加到磁盘上,用来发生崩溃后重建memtable。
  • B树:将数据库分为固定大小的块或页面,一次只能读取或写入一个页面,每个页面都可以使用地址或位置来标识,这允许一个页面引用另一个页面。崩溃恢复:预写式日志,并发控制:锁存器。
  • LSM树和B树的比较:LSM树支持更高的写入吞吐量(具有较低的写放大问题,顺序写入),缺点:压缩会影响读写操作。
  • OLTP(事务处理):查询少量记录,按键读取。随机访问,写入要求低延时。
  • OLAP(分析系统):在大批量记录上聚合。批量导入(ETL),事件流。
  • 列存储:把来自同一列的所有值存储在一起。

第四章:编码与演化

  • 向后兼容(backward compatibility): 新代码可以读旧数据。
  • 向前兼容(forward compatibility):旧代码可以读新数据。
  • 从内存中表示到字节序列的转换称为编码,反之称为解码。
  • 文本格式编码:JSON,XML,CSV
  • 二进制编码:MessagePack,Protobuf,Thrift,Avro
  • 基于模式的编码格式的优点:空间更加紧凑,编译时进行类型检查,检查向前和向后兼容性。
  • 服务器本身可以是另一个服务的客户端,这种方法通常用于将大型应用程序按照功能区域分解为较小的服务,这种构建应用程序的方式传统上被称为面向服务的体系结构。
  • RPC的问题:网络问题不可预测,超时、重试、幂等,编码etc
  • 消息代理系统的优点:提供缓冲区防止过载,重新发送,将生产者和消费者逻辑分离。

第五章:复制

  • 复制:使得数据与用户在地理上接近(从而减少延迟),即使系统的一部分出现故障,系统也能继续工作(从而提高可用性),扩展可以接受读请求的机器数量(从而提高读取吞吐量)。
  • 常用的复制方式:单领导者,多领导者,无领导者。
  • 同步复制:主库等待从库复制完成返回成功,从库保证有与主库一致的数据副本。异步复制:主库不等待从库复制完成返回,从库不保证有与主库一致的数据副本。
  • 处理节点宕机:从库失效:故障恢复(拉取快照,同步变更,消费数据积压)。主库失效:故障转移(确认失效,选举新主库,重新配置)。
  • 故障转移的麻烦:复制日志不同步导致新老主库的写入冲突,脑裂(两个节点认为自己是主库)。
  • 复制日志的实现:基于语句的复制(麻烦:非确定性函数,自增列),传输预写式日志,逻辑日志复制(基于行),基于触发器的复制。
  • 最终一致性:从库最终会赶上并与主库保持一致。
  • 读写一致性:用户总能看到自己提交的任何更新。
  • 单调读:一个用户顺序地进行多次读取,应该看到一致的数据。(比强一致性弱,比最终一致性强)
  • 一致前缀读:如果一系列写入按某个顺序发生,那么任何人在读取这些写入时,也能看到它们以相同的顺序出现。
  • 多主数据库最大的问题:处理写入冲突,解决方式:同步和异步冲突检测(等待写入复制到所有副本),避免冲突(所有写入通过同一个领导者)。处理冲突合并的方式:最后写入为准(LWW),即给每个写入一个唯一的ID/时间戳,选择最新的ID作为胜利者。
  • 无领导者式复制(Dynamo风格):客户端/协调者向多个副本发送写入。
  • 读写的法定人数:如果有n个副本,每个写入必须由w节点确认才能被认为是成功的,并且我们必须至少为每个读取查询r个节点。只要$w + r> n$,我们期望在读取时获得最新的值,因为r个读取中至少有一个节点是最新的。遵循这些r值,w值的读写称为法定人数(quorum)的读和写。

第六章:分区

  • 分区通常与复制结合使用,使得每个分区的副本存储在多个节点上。 即使每条记录属于一个分区,它仍然可以存储在多个不同的节点上以获得容错能力。
  • 分区目标是将数据和查询负载均匀分布在各个节点上。
  • 一些分区比其他分区有更多的数据或查询,称之为数据倾斜。不均衡导致的高负载的分区,称之为热点。
  • 根据键的范围分区:为每个分区指定一块连续的键范围。
  • 根据键的散列分区:每个键通过散列函数落在适合的分区上。
  • 文档分区的二级索引:每个分区维护自己分区中文档记录的二级索引,查询时并行查找所有分区的二级索引,把结果聚集返回。
  • 关键词分区的二级索引:根据特定的关键词把二级索引分布在不同的分区,查询时需要找到关键词所在的分区,直接查询结果返回。
  • 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡。平衡策略:反面教材:hash mod N。固定数量分区:创建比节点更多的分区,添加分区时从各节点中移动分区。动态分区:当分区增长到一定数量后自动再分区。按节点比例分区:每个节点具有固定数量的分区。
  • 服务发现的三种方式:1.客户端联系任何节点,节点处理或将请求转发到合适的其他节点上。2.客户端联系路由层,路由层将请求转发到合适的其他节点上。3.客户端知道分区和节点的分配,将请求直接发送到合适的节点上。
  • 协调服务:ZooKeeper跟踪集群的元数据,节点上面注册,ZooKeeper维护分区和节点的可靠映射。

第七章:事务

  • 事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。事务ACID:A(原子性,要么全部成功,要么全部失败),C(一致性,对数据的一组特定陈述必须始终成立),I(隔离性,事务之间不应该相互干扰),D(持久性,事务成功后写入的数据不会丢失)。
  • 脏读:一个客户端读取到另一个客户端尚未提交的写入。
  • 脏写: 一个客户端覆盖写入了另一个客户端尚未提交的写入。
  • 读已提交:从数据库读时,只能看到已提交的数据(没有脏读)。写入数据库时,只会覆盖已经写入的数据(没有脏写)。
  • 不可重复读:一个事务中两个相同的查询中间由于其他事务的提交,导致查询返回了不一样的结果。
  • 快照隔离:MVCC:当一个事务开始时,它被赋予一个唯一的,永远增长的事务ID(txid)。每当事务向数据库写入任何内容时,它所写入的数据都会被标记上写入者的事务ID。
  • 一致性快照的可见性原则:读事务开始时,创建该对象的事务已经提交。对象未被标记为删除,或如果被标记为删除,请求删除的事务在读事务开始时尚未提交。
  • 写偏差:两个事务同时更新两个不同的对象,导致不符合预期。写偏差模式:1.查询找出特定的行。2.根据第一个查询的结果决定是否进行。3.如果判断成功执行更新事务。例子:医生值班,多人游戏,抢注用户名,会议室预订。解决方法:为更新的对象加行锁(SELECT FOR UPDATE),唯一索引,可序列化。
  • 一个事务中的写入改变另一个事务的搜索查询的结果,被称为幻读。
  • 可序列化三种技术:顺序执行事务,2PL,SSI。
  • 2PL:写阻塞读,读阻塞写。锁模式:共享锁,排它锁。读对象:要求共享锁,有排它锁则阻塞。写对象:有任何锁存在则阻塞。
  • 间隙锁:通过对索引范围的间隙加锁防止其他事务写入导致的幻读。

第八章:分布式系统的麻烦