整体架构 🔗

  二层（1 sql层无状态，处理用户请求和sql运算逻辑，2 kv层存储kv）。
  三个组件（tidb-server, tikv-server, pd-server）

tidb: 支持mysql协议，以支持事务的分布式kv存储引擎为底层存储的数据库。

存储格式 🔗

  存储的数据持久化到磁盘上。table表如何映射为kv存储？
  主键的kv结构：key=tableID_primaryID, value=[col1, col2...]
  二级索引： key=tableID_索引ID_primaryID, value=null

行数据的kv格式
key: t{tableID}_r{rowID}
val:[col1, col2, col3]

unique index的kv格式
key: t{tableID}_i{indexID}_columnsValue
value: rowID

non-unique index
key: t{tableID}_i{indexID}_columnsValue_rowID
value: null

row和index的key具有相同的prefix，一个table内的数据在tikv的key空间内是排列在一起的。

窥探一二 🔗

有一些模块是make it work， 有一些模块是make it fast。

模块 🔗

tidb-server的入口tidb-server/main.go, tidb-server中分三层：
mysql协议解析和转换为ast，protocol layer: server包负责，
sql layer: Sesssion(), RecordSet(), Plan(), Logical Plan, Physical Plan, Executor, distsql, store/tikv client
kv api layer: Mock-Tikv

server/conn.go 大循环中不断读取数据包
server/conn.go#Dispatch函数处理sql文本
处理sql文本的函数handleQuery收到sql文本

session/session.go#ExecuteStmt 拿到ast。visitor 模式进行遍历.

compiler.Compile对sql的ast做验证，优化动作的入口

生成执行器executor/adaptor.go#Exec()..buildExcecutor(): plan -> executor。

select a from t where c1 > 1;

执行器 projection(a) -> filter(c1 > 1) -> table scan(t)。 获取数据时rs.Next()方法链式调用到底层，当前层的处理依赖于下层返回的数据。

server/conn.go#writeResultset写回client

client <-->sql处理 <--> 生成执行计划 <---> 生成执行器
执行器的执行是：在需要给客户端返回数据的地方调Next()方法获取结果数据。

tidb sql执行过程 🔗

主要的包：parser, planner, executor

虽然架构上分计算层和存储层，为了避免大量的rpc，需要将计算尽量靠近存储节点。

创建计划 🔗

planbuilder.go#Build 根据ast.Node节点的类型来创建计划， 例如Insert, LogicalJoin, DataSource

逻辑优化 🔗

利用关系代数的变换规则进行查询语句表达式的等价变换
逻辑优化是基于预先定义的规则列表logicalOptRule pass定义处理

逻辑算子：

• DataSource 负责数据源(可能包含下推的条件谓词)
• Selection 选择。 where id = 5 中的where过滤条件
• Projection 投影。 select c， a+b 中取c列的操作是投影, 也有表达式计算
• Join 连接。 from t1, t2 where t1.c = t2.d 把t1 和 t2内连接，还有很多其他join方式
• Sort。 select * from t order by c 中的order by
• Aggregation 聚合操作。 (select sum(d) from t group by e)中的group by， sum。
• Apply。 子查询

columnPruner 列裁剪（从上往下一路加column） plan/column_pruning.go

最大最小消除将max/min转为order by id + limit 1。 投影消除

PredicatePushDown谓词下推: 把过滤条件推到DataSource算子上，在leaf node中执行减少数据访问。

cop[tikv] root[tidb] 所有的 Join 操作都只能作为 root task 在 TiDB 上执行。

物理优化 🔗

物理优化是基于代价的方式。

dagPhysicalOptimize

tidb plan & executor 🔗

select name from person where age = 18

logical plan:

• scan table person
• selection age = 18
• projection name

逻辑计划 对应多种物理计划
逻辑计划 -> 物理计划（具体的操作算子）
例如： 逻辑算子datasource (物理算子IndexReader, TableReader, IndexLookUpReader)

Join (HashJoin, SortMergeJoin, Index Lookup Join)

• HashJoin: 估计出小表，小表生成hash表，大表执行constains key 匹配出结果
• Index Lookup Join： outer表的数据与inner表的index key范围
• Sort Merge Join： 通常在连接的列上有索引时可以考虑。按连接的列值进行排序，进行归并得到结果

执行计划的逻辑优化（基于规则的优化RBO），例如列裁剪，投影消除， 谓词下推（先筛选，再做数据连接）
执行计划的物理优化 (基于代价的优化CBO)， 等价转换，

executor 物理计划执行过程 🔗

//session/session.go
func (s *session) ExecuteStmt(ctx context.Context, stmtNode ast.StmtNode) (sqlexec.RecordSet, error) {
    ...
    compiler := executor.Compiler{Ctx: s}
    // 生成查询计划以及优化
    stmt, err := compiler.Compile(ctx, stmtNode)
    ...
    logStmt(stmt, s)
    // 去tikv上获取数据
    recordSet, err := runStmt(ctx, s, stmt)
    ...
    return recordSet, nil
}

volcano火山模型。 迭代器模型。
每个物理算子均实现Open, Next, Close方法

func (p Projection) Next() {
    row := p.children.Next()
    return row.name
}
func (s Selection) Next() {
    row := s.children.Next()
    if row != nil && row.age = 18 {
        return row
    }
    return nil
}
func (s Scan) Next() {
    return person.read()
}

tikv-client 🔗

todo tidb-server里模拟tikv中的计算逻辑mock-tikv

tikv 🔗

分布式 事务 k-v pair

单机存储靠rocksdb来存储到磁盘上。分布式数据复制靠raft。

row -> region -> store -> database

并发控制，mvcc。 🔗

Timestamp Oracle(TSO) 递增时间戳作为版本号。
prewrite时的冲突检查： 1、检查column family lock上key是否被lock了， 2、在cf write上key的版本号是否小于当前事物持有的TSO， 否则rollback
prewrite时选择多个key中的一个作为primary key， Lock列加锁；其他的作为secondry key，Lock列加锁，外加存储primary key(异步提交失败后，下次查询会查询primary key若提交后会补充提交)。

rocksdb 读写路径 🔗

write: memtable(skiplistt) --> immutable table --> String store table (SST)
read: the same path

对 DB 感兴趣可以看看 https://github.com/joaoh82/rust_sqlite