存储设计总感觉

1. 限制和要求
2. 事务支持
3. 分布式？
4. 数据格式设计，索引设计
5. 物理文件设计
6. 单机运行设计

1. 限制和要求

涉及到选介质，选索引，是否分布式。

• 延时？
  介质（内存，SSD, 磁盘）。全内存操作要对数据格式要求极高。
• 读多？
  数据量中的 3 最多一次小 index+ 数据，适合大量读。磁盘每页随机写。单次为何还比 SSD 慢呢？一个是 SSD 都是顺序，为何差 10 倍写，mysql 对事务的支持中间操作很多。
• 写多？
  数据量中的 2 一般与 SSD 一起用，大量操作 SSD 很快，擦除影响寿命 =》追加，适合写多。读性能和 mysql 差不多
• 数据量？
  1. 数据量少，内存足够，类似 redis，index 不需要排序
  2. 大，顺序 +hash。每个 hash 要全部载入内存。16M/G。适合大数据或者单词查询。
  3. 与 2 一个量级，B+。以页为答案为索引，前几层基本都在索引中，
  4. 很大。大到 mysql 操作同步，事务支撑不了。放弃事务。leveldb+ 分区。将文件 + 内存分区等

2. 事务

不同日志和锁实现方式。
并发（锁）或者 串行？

2.1 原子

undolog。基本也只有 mysql 支持 。问题就只有为啥 mysql 的 undolog 不用于持久化。因为计算太多。
不需亚多条显示提交回滚。比如 redis,leveldb 的 KV 形式。则按照上文的 WAL+ 操作。日志有就重做。注意加 seqid 去重
否则 WAL(begin)+ 操作 +WAL(end)
涉及到复杂的性能提升的批量刷盘像 mysql 一样加 redolog 或者顺序操作不需要

2.2 隔离与一致

redis 读写都是串行解决众多问题。
leveldb 写入是串行。recoksdb 写入单个 family 串行。所以只有一个可重复读需要解决
其他基本上都是 MySQL 的问题

• 1. 脏写：
  行写锁。leveldb 的锁是整个 mem 的。
• 2. 脏读：
  锁代价大 =》持有写入锁可以设置新值，读旧数据。读已提交的隔离级别，只需要保留一个版本
• 3. 可重复读：
  事务 id/seq 比较。
  多版本 保存方法：
  leveldb 全部保存。内存 key 就带了 seqid，每个都保留，live 的读 manifest 里有最小最大 seqid，内存 compact 是 seqid 决定删除否。文件不删除，多份。
  mongodb B 树的多节点，当前 checkpoint 的东西在页节点的 updatelist 和 insertlist。多个 checkpoint 的引用多个树。
  mysql: 单独 updatelist，回查。节点只存最新的。
• 4. 丢失更新等:
  select v;update v=v+1; leveldb 单独加 1 操作，mysql 间隙锁，for update 等扩大锁定范围
  唯一 select empty;insert 冲突；leveldb 不支持这么复杂的约束
• 5. 串行
  SSI 序列化快照隔离：悲观锁 =》乐观锁（先执行到提交时再检查是否与隔离违背，违背则中止重试）。快照隔离 + 检测写入序列化冲突。（读之前存在未提交的写入）MVCC 的读在提交时检查是否有被忽略的写入已经被提交。写入数据时通知所有最近读取的其他事务（读之后发生写入）

2.3 持久

区别在 前 log 还是在后 ，是 逻辑还是物理。

• redis 的持久：
  执行完一个写命令后，会以协议格式将命令追加到 aof_buf 缓冲区末尾。AOF, 子进程 rewrite，重写过程中新的继续写入缓冲区。也算类似 checkpoint 吧
• leveldb
  内存前 WAL。还有每个事务引用不同的 version 在内存中需要恢复，这部分每个 version 的持久化在 manifest 中，compact 生成新 version 后写入
• mysql
  redolog 的覆盖。内存的刷新，更新 lsn，写入 checkpoint 点，此后的日志可以覆盖了。如果事务执行太快，redolog 来不及刷盘，2G 内存会被覆盖，会对 log 进行 checkpoint 落盘。这点之前的可以安全覆盖

3 分布式？

3.1 备份

高可用的备份：高性能的负载，地理就近进行数据复制，一般三个副本可以保证 11 个 9

• 复制方法
  快照 + 新命令传播（mysql redo 和 binlog 两种，语句注意 rand 等，逻辑行复制）
  不重 要么 log 幂等，要么全局 id。
  事务是否结束 binlog 只有结束才写，oplog 作为 WAL 但结束转移 id 队列。
  都是 从主动 拿 offset.顺序 保证 offset
• 主从切换
  从库上报心跳，选主，对比 term 和 seq，（ISR 中选择）。
  从库延时超过几个 seq 后 down 剔除同步集合。
  谁来做切换？一个哨兵集群或者 proxy/zk 来做(固定心跳集)，自动 gossip+raft。redis 1s 频次，mongodb 2s。10s 未收到有问题，bully。rocksdb 30s，2 分钟
• 复制方案
  同步，异步（绝大多数领导者形式都是这个），半同步（ISR,pipeline）
• 访问方式
  几种保证：读写一致性（自己更新自己立刻可看），单调读（同一用户多次读取一致），一致性前缀读（保证读取顺序按写入顺序），最终一致性。
  1）读主库，刚更新数据读主库，记录时间戳；自己请求读主库，注意不同网络和设备，分布打到多个数据中心的需要路由到主库的数据中心
  2）同一用户读固定从库，防止更旧
  3）依赖事务有因果关系的写入 同一个分片。不同分片不保证顺序一致
  单主 写主。除非上述，否则读从。冷备，温被，热备
  多主 同上
  无主 全部多读多写，返回数量足够成功

• 一致性解决方案
  单主 多库事务，主从延时（redo 取代 binlog，反读主 +cache）
  多主

  多主写入要同步，夸机房多主写入前通信延时不行，业务上很难保一个分类始终在一个机房，小流量等；写后 ` 冲突处理 `，（1. 每次请求带最大 id，lamport 时间戳；2. 保留多版本，按时间戳覆盖）数据保证不丢，mq。redis 的

  无主 类似 raft，每个写入前协商，但是一般 mysql 夸机房这种商议基本不可能等。
  全局有序，线性一致性
  zk 这种的数据，全放入内存的，选主更新 term，数据同步（收集, 确认同步范围），投票决议，提交，同步

• 多存储事务
  无核心的：二阶段提交，三阶段提交，一致性协议
  有核心的：binlog 同步，cache 解决

3.2 可扩展的分片

• 分片方式
  hash
  键值 +hash(重新分片可以直接计算，变化范围还可控)
  一致性 hash
  range(hbase热点) 扫描和范围查询
• 重新分片
  1.hash 提前分配 slot（如果任意，要记录 slot。比如 1024 要记录 1024 个，16384 这种记录 slot 范围，key 到槽固定，槽到机器不确定），如果非任意，2，4，8 这种扩展可以不需要元数据。
  2. 动态分区，合并和拆分（需要记录范围）
  3. 新加入节点在旧节点中随机拿一部分。比如一致性 hash 基础上，每个机器节点 256 个虚拟节点，配置范围，新节点取 82%~102% 的部分。维持总节点数不变，每个机器持有节点变少。（需要记录范围）
  4.CRUSH（ 不需要元数据）固定虚拟节点 gid 第一层 hash。gid 与节点 id 生成随机，只跟二者相关的伪随机，所有节点 id 中选择随机数 * 权重最大的，新增只需要把更大的移走，减少只需要移动到次大的。
• 元数据存储：
  单独 zk。codis,zk 负责分片排队
  每个都存在节点上做同步。redis 的集群每个转发，迁移过程中 ASK 标识，重新分片需要个单独东西排队。或者 mongodb 的抢锁迁移（分布式锁问题，比 zk 代价还是小的）。自己做 name 集群，每个同步。
• 增量元数据何时切
  增量全转到新的，快照同步完就切。

4. 数据格式设计、索引设计

myssql B+ 页索引。页中仍有索引（4- 8 一个）。
leveldb 一页一个 index 值。hash 有序。无继续索引。bloom 过滤器 。其他过滤器。
redis 直接 hash。rehash
列存储：倒排索引。bitmap(布尔查询)
删除：mysql: 标注和 update 类似处理，仍然要改到页上.leveldb 也和 update 一样，新文件。原地整理

5. 物理文件设计

• leveldb
  manifest 存储当前版本每层文件，文件最大和最小序号，
  data ;bloom filter;filter;meta ; filter index;data index;footer。
• mysql
  元数据每个索引根节点 page no。表 =》段 (一个表最多 85 个)=》区(一个区一个区分配，64 页，每 256 个区一个索引)=》page 到 page 后根据树搜索。
  数据，索引，插入缓存 Bitmap 页等 独立文件或者一个文件。共享：undo 信息，二次写缓冲 一个文件
  表空间 ibdata=> 段 =》区 extent=>page（1M 区，4kpage 的话 256 个。默认 1M，64 页，16k）=》行（每页最多 7992 行）（页有不同的类型，如果表空间管理页，INODE 节点页，插入缓存页以及存放数据的索引页等）
  1. 表空间第一页是表空间管理，管理 256 个区（spaceid, 下一个段 id）。
  2. 第三页为 Inode page，维护段（数据段 / 索引段 /undo 段）的使用信息，当前段的 free extent list 等。除了维持当前 segment 下的 extent 链表外，为了节省内存，减少碎页，每个 Entry 还占有 32 个独立的 page 用于分配，每次分配时总是先分配独立的 Page。当填满 32 个数组项时，再在每次分配时都分配一个完整的 Extent。一个 Innode page 里最多存放 85 个 entry，除非为一张表申请 42 个索引，否则一个 Innode page 足够使用。如果未开启 innodb_file_per_table 选项的数据库来说，所有的信息都存储在 ibdata 文件，可能需要多个 Inode page 来维护段信息。Innodb 将这些 Inode page 通过链表的方式组织起来。当创建一个新的索引时，实际上构建一个新的 btree(btr_create)，先为非叶子节点 Segment 分配一个 inode entry，再创建 root page，并将该 segment 的位置记录到 root page 中，然后再分配 leaf segment 的 Inode entry，并记录到 root page 中。
  3. 第 8 页为数据字典：当我们需要打开一张表时，需要从 ibdata 的数据词典表中 load 元数据信息，其中 SYS_INDEXES 系统表中记录了表，索引，及索引根页对应的 page no，进而找到 btree 根 page，找到 inode, 就可以对整个用户数据 btree 进行操作。
  4.index page。页头(页信息，slot 个数，记录数，level 等)。数据。索引(infi slot supre，每 4~8 个分一个。二分查找)

6. 压缩（适用于索引，cache, 文件）

• 有序的可以 前缀压缩.snappy,zlib(慢，压缩比很高)
• 德鲁伊中列三种类型：时间，列，统计
  1. 时间戳和统计：变长整数编码 +LZ4 压缩的整数或浮点（比 snappy 两者都好点），DC 动态词典编码
  2. 列： 字典 + 列字典值 + 倒排索引
  1）将值（总是被视为字符串）映射到整数 ID 的字典，
  2）列的值列表，使用 1 中的字典编码，和
  3）对于列中的每个不同值，一个位图指示哪些行包含该值。倒排索引：posting list 采用压缩的 bitmap 位图索引，
• redis
  ziplist. 连续空间取代链表，前面节点固定 1 / 5 字节。encodinng/length/content字节编码标识长度
  zset 整数固定长度
• pb 的
  1. 连续位标识
  以上数字的转变全是基于 VLQ 可变长二进制数字编码 的变体。最低位加 0 表示整数，1 表示负数，然后 7 位一个分割。从最后开始，每个后面有第一位是 1，否则是 0.
• EC 编码：N 个数据块和校验，可以任意丢 k 个相互恢复

7. 单机运行设计

• 网络模型
  进程 / 线程通信（pipe，socketpair，文件 / 匿名共享内存）
• cli
  协议
• cache 索引 cache 数据 cache
  lru(分成多组，活跃 / 非活跃 3 /8)。
  redis 的没有用 lru 的列表。在记录上记录时间，搜索记录删除。
  rocksdb lru 在改时要锁。CLOCK LRU 介于 FIFO 和 LRU 之间，不需要加锁，首次装入主存时和随后再被访问到时，该帧的使用位设置为 1。循环，每当遇到一个使用位为 1 的帧时，操作系统就将该位重新置为 0，遇到第一个 0 替换
• 并发
  网络
  WAL+mem 写入批量并发，rocksdb 的内存 CAS
  写 log 并发（hbase 分区 /mongo 的 预分配 slot）
  落盘（积累数据，单独 flush 线程，redis 的 async 也是单独线程）
  compact 并发（rocksdb 的 多线程 compact,mysql 的 日志重放每个 db 一个线程）
• 内存池
  对其的内存 （连续小块）。 大块内存不需要对其，没啥意义了。
• IO
  写入的buf,flush,sync。（数据 4k write（flush）一次，64k 补一个 fsync，日志 32k 读一次,buf,32kflush 一次）页保证完整性(校验和 + 丢弃一整块，按最小原子写入，mysql 的二次写)