存储设计总感觉

jiezi

5 年前

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

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

延时？
介质（内存，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+ 分区。将文件 + 内存分区等

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

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

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 的读在提交时检查是否有被忽略的写入已经被提交。写入数据时通知所有最近读取的其他事务（读之后发生写入）

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

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

高可用的备份：高性能的负载，地理就近进行数据复制，一般三个副本可以保证 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 解决

分片方式
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 集群，每个同步。
增量元数据何时切
增量全转到新的，快照同步完就切。

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

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 个分一个。二分查找)

有序的可以 前缀压缩.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 个相互恢复

网络模型
进程 / 线程通信（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 的二次写)

存储设计总感觉

1. 限制和要求

2. 事务

2.1 原子

2.2 隔离与一致

2.3 持久

3 分布式？

3.1 备份

3.2 可扩展的分片

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

5. 物理文件设计

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

7. 单机运行设计