读书笔记-Design Data Intensive Applications

Design Data Intensive Applications

Ch3: Storage and Retrieval

Hash Index的目的是为数据库构建一份索引，方便根据key快速查询对应的value。

Compaction操作合并多个文件，相同key只会保存一份最新的value。

SSTables和LSM树：数据写到MemTable中是排序的，刷写到磁盘上也是有序的，最后通过定期的Compaction再合并数据。

由于每个SSTable的key都是唯一的，多个SSTable文件合并时，如果key重复，选取最新Segment的值，去掉旧Segment的所有值。

读取Segment不可避免地要扫描文件，所以可以对文件进行压缩，提高I/O带宽和传输速率。

不需要为所有SSTable的key建全量索引，只需要稀疏索引。由于key是有序的，可以通过二分查找快速定位key的位置。

稀疏索引不是必须的，不过通常需要稀疏索引。如果key和value的长度是固定的，就可以不需要稀疏索引，不同实际情况value一般是变长的。

LSM树的优化方法有：为文件添加BloomFilter、不同的合并策略。

传统数据库使用B树就地更新数据。B树一般将数据库分成固定的块或页，比如4K。这样读写操作每次也是一页。
这种方式和底层硬件对应起来，比如磁盘就是按照4K固定块组织的。

新增key到B树会调整树的结构，比如拆分出两个子Page，然后更新父Page。

B树的优化方法有：Copy-On-Write、不存储整个key，而是对key进行简写、范围查询时，子页之间会有指针。

为了容错，B树和LSM都有WAL预写日志，用于节点宕机后的数据恢复。

虽然LSM在后台执行增量的Compaction操作，但是磁盘资源有限，当执行一个昂贵的Compaction，
客户端请求可能需要等待Compaction完成，造成响应时间上升。

磁盘的写带宽会被三个操作共享：写WAL日志、MemTable刷写磁盘、Compaction。
数据库一旦变得越来越大，Compaction操作需要的带宽也会越来越多。

Compaction如果没有配置好，一旦写吞吐量很高，那么Compaction操作跟不上写请求。未合并的文件会越来越多，读请求也会越来越慢。

B树和LSM树的区别是：每个键在B树中只有一条记录，但在LSM中可能存在多条。这也是B树可以提供强一致性事务的保证（只对行进行加锁）。