mongodb
本文分两部分，分布式和单机。单个db的存储引擎，物理和数据存储简介，事务实现等。分布式架构，分布式涉及的复制集，分片等可靠性和扩展性保障。
第一部分 单机存储引擎介绍
引擎
wiredTiger（简称WT）支持行存储、列存储以及LSM等3种存储形式，Mongodb使用时，只是将其作为普通的KV存储引擎来使用，mongodb的每个集合对应一个WT的table，table里包含多个Key-value pairs，以B树形式存储。mongodb的集合和索引都对应一个wiredTiger的table。并依赖于wiredTiger提供的checkpoint + write ahead log机制提供高数据可靠性，目前支持单机事务。
按照Mongodb默认的配置，WiredTiger的写操作会先写入Cache，并持久化到WAL(Write ahead log journal)，每60s或log文件达到2GB时会做一次Checkpoint，将当前的数据持久化，产生一个新的快照。Wiredtiger连接初始化时，首先将数据恢复至最新的快照状态，然后根据WAL恢复数据，以保证存储可靠性。
Wiredtiger的Cache采用Btree的方式组织，每个Btree节点为一个page，root page是btree的根节点，internal page是btree的中间索引节点，leaf page是真正存储数据的叶子节点；btree的数据以page为单位按需从磁盘加载或写入磁盘。
Wiredtiger采用Copy on write的方式管理修改操作（insert、update、delete），保证一致性，并且不像InnoDB一样，需要一个DoubleWriteBuffer保证非disk block 512B写时对原有页可能发生conrrupt。修改操作会先缓存在cache里，持久化时，修改操作不会在原来的leaf page上进行，而是写入新分配的page，每次checkpoint都会产生一个新的root page。
内存结构：B树，索引页和数据页，新插入跳表（有序）更新list(变更)，wal,copy onn write
物理结构：
写入：写入页的跳表，不改变原值
更新：写入更新数组中
读取：若有update合并
做checkpoint时，将更新和写入到新的页中，生成新的page_root快照。
ACID：隔离用的未提交快照。注意这个快照只是读用的。写还是到最新页。
journal:并发，预先分配slots,申请用CAS，buffer和lsn 刷盘
关于快照,缓存，数据
每个事务有自己的快照(可能是旧的page_root)，新的事务会获取当前最新page_root，checkpoint对最新的最持久化和生成新page_root到磁盘，按需读取到内存。新建连接会先进行磁盘的数据的数据恢复，最新快照+WAL，按需读入内存
cache 驱逐：略
数据清理：
- compact 加的是DB级别的互斥写锁，同一个DB上的读写都会被阻塞
- compact基本不需要额外的空间，wiredtiger compact的原理是将数据不断往前面的空洞挪动，并不需要把数据存储到临时的位置（额外的存储空间）。
运行中内存占用
存储引擎cache，集合，索引元数据，新写入数据
MongoDB Driver 会跟 mongod 进程建立 tcp 连接，并在连接上发送数据库请求，接受应答，tcp 协议栈除了为连接维护socket元数据为，每个连接会有一个read buffer及write buffer，用户收发网络包，buffer的大小通过如下sysctl系统参数配置，分别是buffer的最小值、默认值以及最大值。500个类似的连接就会占用掉 1GB 的内存 ，ss -m
其他并发大时排序等
主备节点差异，备节点buffer存储oplog
分布式
扩展性
分片：范围，hash
迁移步骤：
集合分片开启后，默认会创建一个新的chunk，shard key取值[minKey, maxKey]内的文档（即所有的文档）都会存储到这个chunk。当使用Hash分片策略时，可以预先创建多个chunk，以减少chunk的迁移。
一个 Sharded Cluster 里可能有很多个 mongos，如果所有的 mongos 的 Balancer 同时去触发迁移，整个集群就乱了，为了不出乱子，同一时刻只能让一个 Balancer 去做负载均衡。
Balancer 在开始负载均衡前，会先抢锁（config.locks集合下的一个特殊文档），抢到锁的 Balancer 继续干活，没抢到锁的则继续等待，一段时间后再尝试抢锁。
Step1: mongos 发送 moveChunk 给源 shard
mongos 接受到用户发送的迁移 chunk 命令，或者因负载均衡策略需要迁移 chunk，会构建一个 moveChunk 的命令，并发送给源 shard。
Step2：源 shard 通知目标 shard 开始同步 chunk数据
源 shard 收到 mongos 发送的 moveChunk 命令后，会向目标 shard 发送 _recvChunkStart 的命令，通知目标 shard 开始迁移数据（真正的数据迁移由目标shard 主动发起）。接下来，源 shard 会记录该 chunk 在迁移过程中的所有增量修改操作。
Step3: 目标 shard 同步 chunk 数据到本地
目标 shard 接受到 _recvChunkStart 命令后，就会启动单独的线程来读取 chunk 数据并写到本地，主要步骤包括：
目标 shard 创建集合及索引（如果有必要）
如果迁移的集合在目标 shard 上没有任何 chunk，则需要先在目标 shard 上创建集合，并创建跟源 shard 上集合相同的索引
目标 shard 清理脏数据 （如果有必要）
如果目标 shard 上已经存在该 chunk 范围内的数据，则肯定为某次迁移失败导致的脏数据，先将这些数据清理掉。
目标 shard 向源 shard 发送 _migrateClone 命令读取 chunk 范围内的所有文档并写入到本地，即迁移 chunk 全量数据，迁移完后更新状态为 STEADY（可以理解为全量迁移完成的状态）。
源 shard 会不断调用查询目标 shard 上的迁移状态，看是否为 STEADY 状态，如果已经是 STEADY 状态，就会停止源 shard 上的写操作（通过对集合加互斥写锁实现）。接下来发送 _recvChunkCommit 告诉目标 shard 不会再有新的写入了。
目标 shard 的迁移线程不断向源 shard 发送 _transferMods 命令，读取迁移过程中的增量修改，并应用到本地，增量迁移完成后，向源确认 _recvChunkCommit 的结果。
源 shard 收到 _recvChunkCommit 的结果，整个数据迁移的步骤完成。
Step4：源 shard 更新 config server 元数据
数据迁移完成后，源 shard 就会向 config server 更新 chunk 对应的 shard 信息，同时也会更新 chunk 的版本信息，这样 mongos 发现本地版本更低就会主动的 reload 元数据，具体机制参考 MongoDB Sharded Cluster 路由策略。
Step5：源 shard 删除 chunk 数据
chunk 迁移到目标 shard 后，源上的 chunk 就没有必要再保存了，源 shard 会将 chunk 数据删除，默认情况下源 shard 会将删除操作加入到队列，异步删除，如果 moveChunk 时，指定了 _waitForDelete 参数为 true，则同步删除完再返回。
一旦源shard 查询到目标 shard 进入到 STEADY 状态了，源 shard 就会进入临界区，测试源上的写就会排队等待。等整个迁移完了，这些等待的写操作就会继续执行，但此时 chunk 的版本号已经更新了，会告诉客户端版本过低，客户端重新从 config server 读取配置，此时拿到的路由信息里 chunk 已经在目标 shard 了，然后写会发往目标 shard 。复制集：
数据同步
Secondary初次同步数据时，会先进行init sync，从Primary（或其他数据更新的Secondary）同步全量数据，然后不断通过tailable cursor从Primary的local.oplog.rs集合里查询最新的oplog并应用到自身。
oplog: 幂等（incr会转为set），循环覆盖，
顺序保证：写入 oplog前，会先加锁给 oplog 分配时间戳，并注册到未提交列表里，正式写入 oplog，在写完后，将对应的 oplog 从未提交列表里移除，在拉取 oplog 时若未提交列表为空，所有 oplog 都可读，否则只能到未提交列表最小值以前的 oplog
Secondary 拉取到一批 oplog 后，在重放这批 oplog 时，会加一个特殊的 Lock::ParallelBatchWriterMode 的锁，这个锁会阻塞所有的读请求，直到这批 oplog 重放完成
故障检测恢复
client与复制集心跳，复制集之间心跳
复制集成员间默认每2s会发送一次心跳信息，如果10s未收到某个节点的心跳，则认为该节点已宕机；如果宕机的节点为Primary，Secondary（前提是可被选为Primary）会发起新的Primary选举。Bully算法
每个节点都倾向于投票给优先级最高的节点（oplog时间戳，一样谁先就谁）
优先级为0的节点不会主动发起Primary选举
当Primary发现有优先级更高Secondary，并且该Secondary的数据落后在10s内，则Primary会主动降级，让优先级更高的Secondary有成为Primary的机会。
如果Primary与大多数的节点断开连接，Primary会主动降级为Secondary
当复制集内存活成员数量不足大多数时，整个复制集将无法选举出Primary，复制集将无法提供写服务，处于只读状态
当Primary宕机时，如果有数据未同步到Secondary，当Primary重新加入时，如果新的Primary上已经发生了写操作，则旧Primary需要回滚部分操作，以保证数据集与新的Primary一致。旧Primary将回滚的数据写到单独的rollback目录下，数据库管理员可根据需要使用mongorestore进行恢复。
Bully
如果P是最大的ID，直接向所有人发送Victory消息，成功新的Leader；否则向所有比他大的ID的进程发送Election消息 如果P再发送Election消息后没有收到Alive消息，则P向所有人发送Victory消息，成功新的Leader 如果P收到了从比自己ID还要大的进程发来的Alive消息，P停止发送任何消息，等待Victory消息（如果过了一段时间没有等到Victory消息，重新开始选举流程） 如果P收到了比自己ID小的进程发来的Election消息，回复一个Alive消息，然后重新开始选举流程 如果P收到Victory消息，把发送者当做Leader
部署
Secondary
Arbiter节点只参与投票，不能被选为Primary，并且不从Primary同步数据，偶数时加入
Priority0节点的选举优先级为0，不会被选举为Primary
Vote0复制集成员最多50个，参与Primary选举投票的成员最多7个，其他成员（Vote0）
Hidden（Vote0）可使用Hidden节点做一些数据备份、离线计算的任务，不会影响复制集的服务。
Delayed节点必须是Hidden节点，并且其数据落后与Primary一段时间（错误恢复）