W2:MongoDB的实现原理
前情回顾
memory hierarchy永远不会变的原因是什么？
当有一块（页）被掉入Dram时，会被缓存而不是立刻扔掉。
文档数据库的组织
Database->collection->document
MongoDB如何实现find等操作。
Collection 在数据库中的组织如file.
File由i-node(page/block)组成。
但是，页查找方式的效率很低。
如何提高查找效率呢?
利用索引提高查找效率
Index/B-tree.
B树的结构特点
排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
很多数据库系统都会用到类似B树的索引。
通过B树的索引，找到某个ID的文档在哪一页，此时就无需再遍历所有的页。
B树顶部的节点作为常用节点可能一直驻留在内存之中。而最后真正需要的I/O操作可能是最底部的一些节点。
总结
在任何文档数据库中，ID常作为一种省缺的属性。
文档数据库会自动的在ID属性上做索引。
此时i-node可能是不需要的，因为我的所有文档集合都已经通过B树组织了。
PremaryIndex的概念(__ID是系统创建的默认的主索引)
有时要告诉数据库，以何关键字创建了索引。比如Create Index:Name这样数据库会再构建一个索引树。
主索引/副索引。secondary Index.
索引是越多越好吗
- 索引越多，数据更新时，代价越大。
- 建立更多索引时的额外代价。
存储系统的正确性
什么是存储系统的正确性？
- 宕机
- 恶意被修改
- 磁盘损坏/灾难发生
- 程序出错(软件)
这门课只设计数据库相关的部分
CRUD操作，看成数据库状态的转移。
在状态的改变的过程中保证都是正确的。
必要条件
任何一个CRUD操作都被正确执行
- 程序在逻辑上不出错
- 原子性(Automicity)
什么是原子性？
一个CRUD操作在瞬间完成。
要么成功要么失败，不存在中间状态。
可映射成时间轴上的点
如何实现原子性？(2 problem)
- 操作所遇到的系统故障的干扰(对抗干扰)：日志
- 其他并发CRUD操作的干扰。(对抗)：锁
解决上面俩问题，原子性基本保证。
如何从软件的角度修复宕机？
在故障之前如何判断我的修改操作有没有做完？即如何让他知道我启动恢复后哪些没有做完？
在操作开始前去记录我开始做了，在操作开始后记录一下我做完了。
判断完操作没有做完后，再改回去。比较内存中和外存中存储的值。比较，改动了，说明操作到这就宕机了，没变，说明宕机的时候还没改到这。
这种方法叫日志；(undo log)
Logging/Jounaling
UNDO 日志
有了Undo Log，当然操作是变复杂了，如下：
<O1,commit>说明O1已经结束了，如果日志未记录，则需要我们去修复。
顺序很重要，先记录A 的初始值，再改动。
在记录<O1,commit>之前，所有磁盘上的改动都必须完成，否则不能记录。
REDO 日志
先在内存做工作，写日志，日志写完即结束我的操作。日志记录结束之前，(操作结束后我们才能将数据写回磁盘)数据是不可以上磁盘的。
有O1commit即操作已经做完(修改内存)。但如果没有end的话，说明AB被修改后的值可能没有写回磁盘上。
若log上没有O1,commit.不要管，因为我知道我没有写回磁盘上，所以我无需理会，直接抛弃这些日志即可。
对比UNDO与REDO日志
REdo所有对数据的改动都保存在内存中，如果一个操作修改的东西很多，对内存的负载消耗很大。REDO日志只需要写到日志即可操作结束，REDO日志是顺序写。
UNDO所有结束前操作必须到磁盘，除了写日志以外还需要写数据，数据写是随机写比较慢。
当代数据管理系统基本都结合了二者的机制。
UNDO/REDO
记录的更多一些。
没有这么重要，只需要分别理解undo/redo日志的例子。
CheckPoint
强制检查点之前的操作全部提交，减少日志回放量。
为什么要进行检查点呢？
找到故障上一个检查点，毕竟我们无需关心该检查点之前已经完成的操作。
如何对抗其他并发CRUD操作的干扰？
Eg:两个文档同时插入。
其他CRUD操作要么在它之前，要么在它之后；
如果操作A在操作B开始之前结束，那么A一定排在B之前（线性一致性 / Linearizability）
- 如果A在B开始之前结束，我要求A一定在B之前，只有这种情况我才必须把A排在B前面，有重叠的话并无所谓。
- CRUD操作A和B一定是有顺序的
为什么会有上面一定的那个要求呢？
假设A操作是插入X，B操作是读入X。系统返回我插入成功才去读。所以A一定要在B前面。
两次push(10),两次pop()
先push1再两次pop，再push
找不到好的从时间段到时间点的映射，不满足线性一致性。
如何保证线性一致性呢？
原子性c.f.线性一致性。
我们可以通过加锁让他满足线性一致性。
利用加锁解决操作之间的线性一致性的问题
总结
- 出故障：日志
- 并行的干扰：加锁
思考
锁释放之前给用户反馈操作成功，还是之后？
操作完成后有两件事情。一件事是释放锁，一件事是通知。
前提：操作结束后，锁即释放，通知在释放锁之前
在释放锁之后通知用户：一个操作持有锁的时间是越短越好。
如果把通知用户的过程放在持锁里面，会将持锁时间拉长，如果通知用户涉及到网络通信了，那时间就更长了。
这两个操作在正确性上是没有问题的。
最后的commit日志在释放锁之前还是之后。
commit日志表示记录操作完成，防止宕机这种干扰。如果宕机，发现commit日志的记录，说明操作完成，可以放锁。
这种会出现错误。
比如有O1和O2两个操作，O1要将共享变量x（init:0)变为2,O2要将共享变量x（init:0)变为5.
但是 如果在O1结束后就释放锁，但此时防宕机的x=2的操作完成的commit记录还没有写回磁盘。但O2的操作完成并且commit已经写回磁盘了。
此时在O1commit未写回，O2commit写回的过程中，宕机。
复原时，查看Log，发现O1未commit，即O1未完成，此时复原，将x=5又复原为2，但此时O2已经commit了，说明记录过了。故此时相当于O2跟没做一样。
