Project2

[0XFF-96]

其他相关概念

• LSTM 树
• Column Family 列簇

其他 DB

• rockdb, https://github.com/facebook/rocksdb/wiki/Terminology .
• rosedb,
• leveldb,
• boltdb,
• badger, kv

什么是 LSTM 树？

• LSTM,

1. 为什么会有基于 lsm 树的存储引擎出现？
2. LSM 树核心思想介绍 (解决哪些问题？怎么解决的？)
3. 基于 LSM 树的存储引擎（BitCask、Moss、LevelDB、Pebble 等）源码实现剖析

听众将获得：

1. 不仅知道有 B + 树存储引擎，而且还了解、掌握 LSM 树存储引擎，面试、2. 大型开源组件学习从此不再慌
3. 了解 LSM 树背后的思想，以及解决问题的一些思路。
4. 对基于 LSM 树的存储引擎开源项目实现有一个基本、全面的认识

B+ 树

#115理论结合实践详解 B+ 树存储引擎（InnoDB、BoltDB、BuntDB）

推导为什么选择 b + 树做索引数据结构
分析 b + 树存储引擎的正常读写流程、边界条件、异常情况
分析几款 b + 树存储引擎的事务、全表扫描实现思路 (innodb、boltdb、buntdb)
详细剖析 boltdb、buntdb 开源项目源码内部实现
扩展内容：讲解时间复杂度为 O (log n) 的几种数据结构的演变 (二叉查找树、avl 树、红黑树、b 树、b + 树、跳表等)

REFERENCE

• https://www.bilibili.com/video/BV1vo4y117Mv?spm_id_from=333.999.0.0
• slide window , https://en.wikipedia.org/wiki/Sliding_window_protocol
• oceanbase 数据库系统相关实现， https://oceanbase-partner.github.io/lectures-on-dbms-implementation/lecture-1 。
• https://github.com/OceanBase-Partner/lectures-on-dbms-implementation
• https://space.bilibili.com/1557732?spm_id_from=333.905.b_7570496e666f.2 【绕了一下到了别人的思路。】

[0XFF-96]

raft 的实现参考

一开始上来就直接撸，可能效果不太好。需要了解更多细节作为基础。 github.com/IvanProdaiko94/raft-protocol-implementation。

• [x] 观察这个 raft 的简单实现。
• [x] 比较大型的实现 https://github.com/lni/dragonboat

[0XFF-96]

Raft 论文阅读笔记

阅读资料

• [x] 论文， https://raft.github.io/raft.pdf 。 2
  • [x] 可视化 raft, http://thesecretlivesofdata.com/raft/
• [x] https://raft.github.io/ 资料大全
• [x] https://github.com/Alex1996a/tinykv/blob/course/doc/project2-RaftKV.md

视频资料

• [x] raft lecture , https://www.youtube.com/watch?v=YbZ3zDzDnrw&ab_channel=DiegoOngaro 。

其他相关资料

1、codedump.info/post/20180922-etcd-raft/

2、etcd raft 库解析， codedump.info/post/20180922-etcd-raft/ 。

3、raft 论文导读和 etcd 源码库解析， https://hardcore.feishu.cn/docs/doccnMRVFcMWn1zsEYBrbsDf8De#

4、etcd-raft 相关算法， https://blog.betacat.io/post/raft-implementation-in-etcd/ 。

5、hashcrop/raft 相关算法。

[0XFF-96]

Raft Basic

Definition: Raft is a protocol for implementing distributed consensus.

Novel Features

• Strong leader
• Leader election
• Membership changes:

Consensus

Consensus is a fundamental problem in fault-tolerant distributed systems. Consensus involves multiple servers agreeing on values

replicated state machines & Log Replication

Each state machine processes the same series of commands and thus produces the same series of results and arrives at the same series of states

• Keeping the replicated log consistent is the job of the consensus algorithm

5.3 Log replication

Resource

• note https://mubu.com/app/edit/home/5t9LAIo864_

[0XFF-96]

Raft 可视化

1. What is Distributed Consensus? ( 共识算法和一致性算法的区别 ）
2. the problem of distributed consensus.
3. three state , followers don't hear from a leader then they can become a candidate.

ref

1. http://thesecretlivesofdata.com/raft/

[0XFF-96]

Etcd

1、 Step 方法， 数据流转的中心。

func (r *raft) Step(m pb.Message) error