一: 增删改查的工作
参考学习《数据密集型应用系统设计》
crud boy的工作是什么?
1 典型场景
image.png
- 主数据库
- 缓存层 redis
- 全文索引服务器 es
- 消息队列kafka
crud的一个工作就是组合使用这些db来完成业务功能
问题是: 我们怎么知道需要用到哪种DB？需要考虑如何几个方面:
- 应用层的"数据模型"
- DB层的"数据存储模型"
- 上述两者的匹配程度
- DB层的可靠性、可扩展性、可维护性
2 建立数据模型
大多数应用程序是通过一层层叠加数据模型来构建的。每一层都面临的关键问题是: 如何将其用下一层来表示？
step1: 业务层对业务构建数据结构
step2: 应用层开发者选择存储数据结构的方式，诸如: 文档、关系表、图
step3: DB层开发者决定用何种内存、磁盘、编码方式来存储
step4: 硬件工程师存储字节
2.1 应用层的决策: 关系模型 vs 文档模型
image.png
关系型数据库(RDS)依然是数据库领域的统治者，器核心在于商业数据的处理: 事务处理和批处理。
而如今兴起的NoSQL有如下几个驱动元素:
- 比关系数据库更好的可扩展性，包括非常大的数据集或非常高的写入吞吐量
- 关系模型不能很好地支持一些特定的查询操作
- 对关系模型限制性感到沮丧，渴望更具动态和表达力的数据模型
关系型数据与文档数据库的比较:
数据模型:
- 历史上, 数据开始被表示为一棵大树（层次数据模型），但是这不利于表示多对多的关系，所以发明了关系模型来解决这个问题。文档数据库的应用场景是：数据通常是自我包含的，而且文档之间的关系非常罕见。
- 文档模型灵活，由于局部性而带来较好的性能，对于某些应用程序而言更接近于应用程序使用的数据结构。关系模型优点在于 联结,、多对一、多对多关系等更简洁的表达
- 如果应用层确实需要多对多的关系，那么文档模型就不太有优势。
容错性和并发处理
2.2 DB层的决策: 日志结构 VS B-Tree
在高层次上，我们看到存储引擎分为两大类：在线事务处理（OLTP）和在线分析处理（OLAP）。
image.png
image.png
- OLTP系统通常面向用户，这意味着他们可能会看到大量的请求。为了处理负载，应用程序通常只涉及每个查询中的少量记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。磁盘寻道时间往往是瓶颈。
- 数据仓库主要由业务分析人员使用。它们处理的查询请求远低于OLTP，但是每个查询通常要求很高，需要在短时间内扫描数百万条记录(往往只涉及几个列)。磁盘带宽（不是查找时间）往往是瓶颈，列式存储是这种工作负载越来越流行的解决方案。
在OLTP方面，有两个主流的存储引擎：
- 日志结构派，只允许附加到文件和删除过时的文件，但不会更新已经写入的文件。 Bitcask，SSTables，LSM-tree，LevelDB，Cassandra，HBase，Lucene等都属于这个组。日志结构的存储引擎是相对较新的发展。他们的主要想法是，他们系统地将随机访问写入顺序写入磁盘，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高
- 原地更新派，将磁盘视为一组可以覆盖的固定大小的页面。 B树是这种哲学的最大的例子，已经用于所有主要的关系数据库&许多非关系数据库。
2.2.1 LSM-Tree
原理比较简单: https://www.open-open.com/lib/view/open1424916275249.html
LSM-Tree的特点
LSM（log-structed-merge-tree）大家可能比较陌生，我之前也是听说而已，只知道Hbase、BigTable、Cassandra、MongoDB等NoSql底层存储模型用的是LSM，仅此而已；最近有个项目用到了RocksDB，底层用的存储模型也是LSM，于是就了解了下LSM，做个笔记加深下理解。
1 what LSM是什么?解决什么问题？
磁盘的顺序读写速度很快，随机读写很慢。现在市面上7200rpm的希捷SATA硬盘顺序读写基本都能达到300MB/s；但是随机读写却很慢，100 IOPS，假设随机读写每次IO大小为1KB，则随机读写数据带宽为100KB/s；顺序读写和随机读写差了三个数量级。
针对磁盘的上述特性，应用都根据自身读写特点做一些优化。比如数据库的binlog日志就是顺序写入，所以效率很高，但是缺点也比较明显，数据很难查询读取（其实binlog是用来回放恢复数据的，不存在查询读取的使用场景）；
Mysql的innodb存储引擎底层用B+树数据结构来组织磁盘上的数据，B+树因其节点的度远大于平衡二叉树（平衡二叉树度为2），所以B+树树高很低（34），每一次数据的查询只需34次磁盘随机IO即可查找到数据（说法不太准确，其实是找到数据所在的page 16K，加载到内存中，再以二分法查找数据，内存二分查找所耗时间远小于磁盘IO，可忽略不计），效率很高；但是insert和update操作是随机的，update隐藏的含义先找到更新的primary-key，更新，调整B+树；查找primary-key的过程很高效，但是调整B+树的磁盘IO开销却很大，因此关系型数据库mysql的写效率一致饱受诟病。那有没有一种替代B+树的数据组织模型，在不太影响读效率的前提下，提高数据的写效率（随机写->顺序写）?
由O'Neil提出的LSM存储模型LSM paper就是解决上述问题的。
2 how LSM如何解决问题的？
看下LSM是如何解决上述问题的：
简单来说，就是放弃部分磁盘读性能来换取写的顺序性。
我们假设要写入一个1000个key是随机数的数据，对磁盘来说，最快的写入方式一定是顺序地将每一次写入都直接写入到磁盘中即可。但这样带来的问题是，没办法查询，因为每次查询一个值都需要遍历整个数据才能找到，这个读性能就太差了；那么如果我想获取磁盘读性能最高，应该怎么做呢？把数据全部排序就行了，B+树就是这样的结构，但B+树的写性能太差了，需要提升写，可以放弃部分磁盘读性能，怎么办呢？
简单，那就划分很多个小的有序结构，比如每m个数据，在内存里排序一次，下面100个数据，再排序一次……这样依次做下去，我就可以获得N/m个有序的小的有序结构，在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。
很容易可以看出，这样的模式，读取的时间复杂度是(N/m)*log2N，读取效率是会下降的，这就是LSM的根本思路。当然RocksDB为了优化效率又引入了bloomfilter，compact机制，感兴趣可以阅读RocksDB的wiki：RocksDBwiki
3 why 为什么选用LSM?
B+索引树和log型（append）文件操作（数据库WAL日志）是数据读写的两个极端。B+树读效率高而写效率差；log型文件操作写效率高而读效率差；因此要在排序和log型文件操作之间做个折中，于是就引入了log-structed merge tree模型，通过名称可以看出LSM既有日志型的文件操作，提升写效率，又在每个sstable中排序，保证了查询效率。
2.2.2 LSM-Tree & B+ Tree
两者各有特点，适用场景各不相同。目前B+ tree用于所有主流关系型数据库，尤其是对于事务语义来说，B-tree更有吸引力。而时序数据库多采用LSM-Tree。
B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得B树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接连接到树[5]。在第7章中，我们将更详细地讨论这一点。 B树在数据库体系结构中是非常根深蒂固的，为许多工作负载提供始终如一的良好性能，所以它们不可能很快就会消失。在新的数据存储中，日志结构化索引变得越来越流行。没有快速和容易的规则来确定哪种类型的存储引擎对你的场景更好，所以值得进行一些经验上的测试。
在具体实现上，两个存储引擎都会面临相同的问题:
1. 采用什么样的文件格式？
2. 如何删除记录？
3. 如何崩溃恢复？
4. 如何并发控制？
5. 如何性能优化？
2.2.3 LSM-Tree Q&A
1. 采用什么样的文件格式？
采用二进制格式
2. 如何删除记录？
如果要删除一个键及其关联的值，则必须在数据文件（有时称为逻辑删除）中附加一个特殊的删除记录(墓碑)。当日志段被合并时，一旦发现墓碑标记，就会丢弃此键以前的所有值。
3. 如何崩溃恢复？
采用WAL和快照的方式
4. 如何并发控制？
由于写操作是以严格顺序的顺序附加到日志中的，所以常见的实现选择是只有一个写入器线程。数据文件段是附加的，否则是不可变的，所以它们可以被多个线程同时读取。
5. 如何性能优化？
- 布隆过滤器
- 日志段合并
2.2.4 B-Tree Q&A
1. 采用什么样的文件格式？
页式组织
2. 如何删除记录？
3. 如何崩溃恢复？
采用WAL和快照的方式
4. 如何并发控制？
使用锁
5. 如何性能优化？
