深入浅出存储引擎

存储引擎的细节写的不错，再结合代码看更完美

找页面置换算法的书，结果weread上只有这一本描述清楚了clock和改进型clock😂😂，很多操作系统书上面反而没有，作者写这本书应该下了很多功夫，读一读应该能有收获，建议按需阅读

一、存储引擎的产生和作用什么是存储引擎？答：存储引擎最基础的目的就是管理用户数据到盘上数据映射的模块，用于读取到对应写到盘上对应的数据。存储引擎的基本目标？答：能够在4个背景（1、读多写少的业务，2、关系型数据库是按照行格式存储，3、千万条数据量，4、要选择底层本、大容量的持久化设备）下实现基础的读写功能存储引擎的终极目标？答：就是性能，要实现高效、快速的实现基本功能，评价性能指标：用户请求耗时。 二、B+tree存储引擎的特点B+tree的特点总结：B+tree作为存储引擎，是大多数读多写少业务的选择，比如MySql，BoltDb等。其本质是由有序多叉树+叶子节点保存value特点组成，并且叶子节点和节点之间，会链接起来，因此非常适合排序查询+范围查找。 磁盘特性：并且，由于磁盘顺序IO速度 > 随机IO速度，响应速度差了数量级以上，因此为了保证尽量通过顺序的IO来进行持久化，需要数据在下盘前在内存中进行排序并保证时间复杂度低，而具有排序能力的数据结构（跳表、红黑树、AVL-tree、二叉排序树、B树、B+树）。 选择B+树的原因：1、而为了保证磁盘顺序IO的特性，内存中排序好的数据要按照一定规则刷盘，一般采用操作系统内存操作的page size（4K）作为阈值，这样就能兼顾内存操作和磁盘顺序的特性，那么最合适的数据结构就是B树/B+树了。2、B树是非叶子和叶子节点均保留原始数据，这样的优点就是命中到非叶子节点的数据，不需要每次遍历到叶子节点，就能直接返回，当然所带来的问题也是显而易见的，就是树的层数会过高，单节点保存的数据量少，磁盘IO数量多，这样性能不够稳定。B+树就是只有叶子节点保留数据，那么读写性能稳定，如果16K大小节点，数据kv占用160B，索引kv占16B，那么3层b+树就能存储1亿的数据。 实际工程KVS（key-value store）中的应用：MKV中kvs模块，采用的数据结构就是B+树，单node为508字节，能保存差不多33个kv对象。 为什么kvs采用B+树作为存储引擎的数据结构？其实还是业务导向的，主存dorado等面向的客户都是toB的业务，运营商、银行、国企等，场景基本就文件系统FS，或者LUN业务，特别是对于LUN业务来说，给客户一个连续的空间自己使用，天然就是带有顺序性的，排序和范围查询就是重点。 KVS中的B+tree还有什么优化？kvs索引里面，key是由于poolkey+offset+cloneid+snapId组成的，poolkey又是根据lunid，shardid进行位运算组合到一起的，fs是根据fsId和fsname得到的。因为key信息对于lun来说，很有可能多个key前缀是一样的，这时候可以采用前缀压缩的形式，压缩空间。 三、LSM tree（log structured merge tree）存储引擎的特点背景：大数据/云计算等写多读少的业务，当前互联网业务，每天会产生大量的中间用户数据，比如点赞、评论等用户数据用于推荐系统，或者系统的日志信息用于链路监控，问题追踪，此类业务均是写多读少，为了保证该类型业务性能，再采用B+树的索引结构，性能就较为低下了。 LSM Tree的组成结构：memTable、ImmuMemTable、SSTable、WAL log这几部分组成由于要保证写性能，采用TVL格式（key，value，opType）进行追加写，因此写性能强，而同一时刻，同一个key会有多个value存在，有效的key就一个，为了防止空间放大，需要采取对应手段进行优化——合并压缩。为了保证写性能强，因为要充分利用内存进行追加写，但是内存虽然速度快，但是成本高，且断电丢失，所以引入SSTable，用于索引数据下盘持久化。新写的都是进入memTable，满了之后转为ImmuMemTable，然后再转为SSTable，为防止写流程故障数据丢失，写memTable之前都要写WAL Log用于故障回放。 合并压缩：SSTable一般分为L0，L1和L2，每一层的key范围不同，上层向下层转换的流程是将（本层+下一层）重合的部分进行merge，然后生成新的子节点，合入到下一层SSTable里，原始的两个子节点释放 读性能优化：由于读要通过memTable->ImmuMemTable->L0 SSTable -> L1 SSTable -> L2 SSTable一层一层往下找，查询性能将会越来越差，因此一般会在每个table防止一个布隆过滤器，用于快速判断key是否存在（但是有可能有假阳性问题，就是判断存在实则不存在） 读放大、写放大、空间放大读写放大都是IO次数的放大，因为LSM Tree都是非原位更新，导致了单个KV的更新，伴随着多次merge磁盘IO，但是实际上B+tree虽然是原位更新，但是一样有读写放大，因为中间节点和其他元数据信息也伴随磁盘IO。空间放大：比如你的IO大小为100Byte，但是磁盘单次IO都是一个扇区，这种造成了空间放大。 四、故障处理一般的IO伴随的是阵列运行数据、写IO数据、写IO的元数据，故障之后的处理手段原则都是回滚到操作前的状态。对于运行数据，一般采用备份双写的形式，一个运行中出问题了，用另一个备份的覆盖回滚写IO的用户数据，特别是写了部分到磁盘上的数据出现故障场景，采用redo log的形式，每次写之前进行写log，内部信息为key->old value，用于保留老数据回滚。对于元数据来说：所采用的也基本上是复本、镜像、日志的形式 五、事务处理ACID：针对于存储引擎来说，必然伴随着原子操作（A：原子性），单次更新涉及多个流程的，要么都成功，要么都失败，事务执行成功之后状态将会持久化保留（持久性），事务和事务之间不能互相影响（隔离性），保证了以上三点，就能保证整体的数据的一致性（比如：A给B转账前后，AB的账户总额不变）。隔离级别：多个事务并发互相影响的程度，一般分为读未提交（脏读），读已提交（幻读），可重复度（不可重复读），串行化，从前到后隔离成都越来越高，读未提交风险最大，其他事务能够读取到本事务修改但是为提交的数据（脏读），由于两次事务操作的时序问题，事务B两次读取事务A操作的值不同，彷佛幻觉一样（幻读），而事务B两次读取的数量不一样，事务A进行了新增或者删除（不可重复读，是幻读的一种特殊形式）MVCC：为了保证多个事务并发执行的策略，多版本并发控制，一般有三种类型，基于锁的，基于时间戳的，基于有效性检查的 MDS（meta data store）中的应用，该模块除了存储对应的元数据外，还提供了元数据的事务操作，本身利用的是多版本并发控制，一共三个状态，T0（已经提交成功的事务，也是外部读能读到的），T1（写未提交），T2（写已提交），并且元数据更新流程是采用副本更新，在原来的节点复制一个副本进行更新操作，然后从叶子节点，一层一层回写到根节点。

就像后记中说的，作者看了很多现有的资料和书籍，加上大学教材中的基础知识，还有几篇自己的博客，汇编成了一本书。

作为存储入门比较合适；太多cs专业基础知识的填充；lsm的概念大可不必如此泛化到包罗万象；mq场景和类leveldb模式有着本质的不同、不建议相提并论

这本书最好的点是各种技术的推理演进过程，把基础知识与成熟系统串起来了