存储设计总感觉

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的二次写)