个人理解，欢迎指正

数据库

引擎

写数据

读数据

补充

MySql

InnoDB：支持事务，高速读写性能一般

Myisam：不支持事务，高速读写性能好

以InnoDB更新一条记录为例

1、B+Tree搜索找到这行记录，如果数据页在内存直接返回给【执行器】，否则从磁盘读入内存再返回

2、【执行器】更新数据，再调用【引擎】接口写入这行新数据

3、【引擎】将旧数据备份到undo log，然后更新内存中数据页的这行数据，同时将操作记录写到redo log里，此时redo log 处于prepare状态

4、【执行器】记录binlog日志

5、【执行器】调用引擎接口，【引擎】将redo log改成commit状态

6、此时更新就算完成了，【InnoBD引擎】会在适当的时候将操作记录批量刷到磁盘，并清理redo log

其基本流程是：先去缓存页查找，若没有则通过B+Tree检索到叶子节点对应的数据页，然后加到缓存页并返回

redo log（重做日志）和 binlog（归档日志）

1、redo log 是 InnoDB 引擎特有的；binlog 是 MySQL 的 Server 层实现的，所有引擎都可以使用。

2、redo log 是物理日志，记录的是“在某个数据页上做了什么修改”；binlog 是逻辑日志，记录的是这个语句的原始逻辑，比如“给 ID=2 这一行的 c 字段加 1 ”。

3、redo log 是循环写的，空间固定会用完；binlog 是可以追加写入的。“追加写”是指 binlog 文件写到一定大小后会切换到下一个，并不会覆盖以前的日志。

Hadoop

存储：HDFS

计算：MapReduce

HDFS写数据

1、Client向NameNode请求上传Block(文件块)

2、NameNode向Client返回DataNode地址

3、Client以Package为单位向DataNode依次写入，直到写完整个Block

4、每传输完一个Package，DataNode会向Clent返回一个ack，若失败会重试

HDFS读数据

1、Client向NameNode请求下载文件

2、NameNode按负载均衡和节点距离返回DataNode给Client

3、Client读取DataNode，以Package为单位拉取，先存入缓存，最后生成文件，中间有checksum校验

MapReduce运算

1、InputFormat会从DataNode拉取一个个Bolck块

2、然后启动若干个MapTask对Block数据做运算

3、运算后的结果经过Shuffer落到磁盘

4、然后启动若干个ReduceTask从磁盘读取数据进行聚合

5、最后通过OutputFormat把结果写到HDFS或其他存储介质里

BigTable

SSTable

其实SSTable文件也是存在GFS上，但GFS不支持随机写【增删改】，那么BigTable是如何实现的呢？

1、其实BigTable在内存里维护了一个内存表（MemTable），每次数据【增删改】都会增加一条记录，并附带版本。当容量到达阀值的时候会把MemTable转成SSTable【顺序写】到GFS上，后续数据继续写新的MemTable

2、另外，会启动一个后台进程（Major Compaction机制），不断的合并SSTable，只保留【增删改】的最终数据，老版本的数据被删除

当查询数据时，会去读取索引数据，找到数据块返回给Tablet Server，再从这个数据块里提取出对应的 KV 数据返回给客户端

1、内存里缓存 BloomFilter，使得对于不存在于 SSTable 中的行键，可以直接过滤掉，无需访问 SSTable 文件才能知道它并不存在

2、通过 Scan Cache 和 Block Cache 这两层缓存，利用局部性原理，使得查询结果可以在缓存中找到，而无需访问 GFS 上的硬盘

3、经过前2步还没找到，会通过SSTable索引来查找，底层是AVL红黑树或跳表，随机读写都是O(log n)

1、SSTable 的文件格式是由两部分组成：

数据块（data block），就是实际要存储的行键、列、值以及时间戳，这些数据会按照行键排序分成一个个固定大小的块（block）来进行存储。

元数据块（meta block），是一系列的元数据和索引信息，这其中包括用来快速过滤当前 SSTable 中不存在的行键的布隆过滤器，以及整个数据块的一些统计指标。

另外还有针对数据块和元数据块的索引（index），这些索引内容，则分别是元数据索引块（metaindex block）和数据索引块（index block）

2、因为 SSTable 里面的数据块是顺序存储的，所以Major Compaction做的是一个有序链表的多路归并，这个过程中在磁盘上是顺序读写

Clickhouse

表引擎主要是MergeTree系列，还有Log系列等其他引擎

1、一个Table是由多个Partition组成，一个Partition是由多个Part组成，Part里按column【列式存储】

2、旧数据在一个Part，新数据会写另一个Part，然后通过MergeTree引擎将多个Part异步合并（按排序键归并排序）

因为是按排序键已经排好序了，所以索引结构不需要像其他引擎设计的那么复杂；

底层是稀疏索引（默认8192为一个步长），通过【稀疏索引+标记的偏移量】就能很快找到Block的位置

1、Clickhouse通过【批处理+预排序】将数据提前排好序

2、Clickhouse能处理的最小单位是block，block就是一群行的集合，默认最大8192行组成一个block

相关资料

HDFS设计原理

日志系统：一条SQL更新语句是如何执行的？

SSTable存储引擎

Clickhouse的优化手段之block+lsm

Clickhouse索引结构

Clickhouse存储引擎

Clickhouse官方文档：MergeTree系列