Reading-List

[0XFF-96]

记录阅读历史的 Issue

(整理为 todo 的形式）

• [ ] Storage Engine
  • [ ] Disk I/O
  • [ ] Flavors of I/O
    • [ ] https://medium.com/databasss/on-disk-io-part-1-flavours-of-io-8e1ace1de017
    • [ ] https://medium.com/databasss/on-disk-io-part-2-more-flavours-of-io-c945db3edb13?
  • [ ] Amplification and RUM
    • [ ] http://smalldatum.blogspot.com/2015/11/read-write-space-amplification-pick-2_23.html
    • [ ] http://daslab.seas.harvard.edu/rum-conjecture/
    • [ ] http://smalldatum.blogspot.com/2019/05/crum-conjecture-read-write-space-and.html
  • [ ] B-Tree (Optional)
  • [ ] Reading Materials
    • [ ] Database Internals: 2. B-Tree Basics
    • [ ] Database Internals: 3. File Formats
    • [ ] Database Internals: 4. Implementing B-Trees
  • [ ] Reference
    • [ ] https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
    • [ ] https://github.com/etcd-io/bbolt
  • [ ] LSM-Tree
  • [ ] Reading Materials
    • [ ] Database Internals: 7. Log-Structured Storage
  • [ ] Reference
    • [ ] https://github.com/google/leveldb
    • [ ] https://github.com/facebook/rocksdb
    • [ ] https://github.com/syndtr/goleveldb
  • [ ] B-Tree vs LSM-tree
    • [ ] https://tikv.org/docs/deep-dive/key-value-engine/b-tree-vs-lsm/
  • [ ] LSM-Tree Evolution
  • [ ] Wisckey
    • [ ] https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf
  • [ ] HashKV (Optional)
    • [ ] https://www.usenix.org/system/files/conference/atc18/atc18-chan.pdf
  • [ ] Monkey (Optional)
    • [ ] https://stratos.seas.harvard.edu/files/stratos/files/monkeykeyvaluestore.pdf
  • [ ] Reference
    • [ ] https://github.com/dgraph-io/badger
    • [ ] https://github.com/tikv/titan
• [ ] Serializing & RPC
  • [ ] Protocol Buffer
  • [ ] Reading Materials
    • [ ] https://developers.google.com/protocol-buffers/docs/overview
  • [ ] Reference
    • [ ] https://github.com/dgraph-io/badger
    • [ ] https://github.com/protocolbuffers/protobuf
  • [ ] gRPC
  • [ ] Reading Materials
    • [ ] https://www.grpc.io/docs/quickstart/go/
  • [ ] Reference
    • [ ] https://github.com/grpc/grpc-go
• [ ] Data Partitioning
  • [ ] Range vs Hash
  • [ ] https://tikv.org/docs/deep-dive/scalability/data-sharding/
  • [ ] Partitioning of DynamoDB (Optional)
  • [ ] https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
  • [ ] https://dzone.com/articles/partitioning-behavior-of-dynamodb
  • [ ] Partitioning of TiKV
  • [ ] https://pingcap.com/blog/2017-07-11-tidbinternal1/
• [ ] Replication & Consistency
  • [ ] Reading Materials
  • [ ] Database Internals: 11. Replication and Consistency
  • [ ] CAP vs PACELE
  • [ ] http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf
  • [ ] Clock and Time
  • [ ] https://dzone.com/articles/tick-or-tock-keeping-time-and-order-in-distributed-1
  • [ ] Consistency
  • [ ] https://arxiv.org/pdf/1902.03305.pdf
• [ ] Consensus
  • [ ] Quorum
  • [ ] https://en.wikipedia.org/wiki/Quorum_(distributed_computing)
  • [ ] Paxos (Optional)
  • [ ] Reading Materials
    • [ ] Database Internals: 14. Consensus @ Paxos
  • [ ] Reference
    • [ ] https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
  • [ ] Raft
  • [ ] Reading Materials
    • [ ] Database Internals: 14. Consensus @ Raft
  • [ ] Reference
    • [ ] https://raft.github.io/
    • [ ] https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
• [ ] Scale & Balance
  • [ ] Multi-Raft
  • [ ] https://tikv.org/deep-dive/scalability/multi-raft/
  • [ ] Split & Merge
  • [ ] https://pingcap.com/blog/2017-07-20-tidbinternal3/
  • [ ] Balance
  • [ ] https://pingcap.com/blog/2017-07-20-tidbinternal3/
• [ ] Distributed Transactions
  • [ ] Reading Materials
  • [ ] Database Internals: 5. Transaction Processing and Recovery
  • [ ] Database Internals: 13. Distributed Transactions
  • [ ] ACID
  • [ ] https://en.wikipedia.org/wiki/ACID
  • [ ] Isolation (Optional)
  • [ ] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf
  • [ ] https://www.jianshu.com/p/3673e612cce2 (Chinese)
  • [ ] Spanner (Optional)
  • [ ] https://storage.googleapis.com/pub-tools-public-publication-data/pdf/45855.pdf
  • [ ] https://www.jianshu.com/p/f307bd2023f5 (Chinese)
  • [ ] Percolator
  • [ ] https://tikv.org/docs/deep-dive/distributed-transaction/percolator/
  • [ ] https://tikv.org/docs/deep-dive/distributed-transaction/optimized-percolator/
• [ ] Coprocessor (Optional)
  • [ ] https://blogs.apache.org/hbase/entry/coprocessor_introduction
  • [ ] https://zhuanlan.zhihu.com/p/89518391 (Chinese)
• [ ] Benchmark & Testing
  • [ ] sysbench (Optional)
  • [ ] https://github.com/akopytov/sysbench
  • [ ] https://www.percona.com/blog/2019/04/25/creating-custom-sysbench-scripts/
  • [ ] https://www.jianshu.com/p/30933e0bebe7 (Chinese)
  • [ ] go-tpc (Optional)
  • [ ] https://github.com/pingcap/go-tpc
  • [ ] go-ycsb
  • [ ] https://github.com/pingcap/go-ycsb
  • [ ] https://medium.com/@siddontang/use-go-ycsb-to-benchmarkdifferent-databases-8850f6edb3a7
  • [ ] https://www.jianshu.com/p/73d22befe47d (Chinese)
  • [ ] Chaos
  • [ ] https://principlesofchaos.org/
  • [ ] https://pingcap.com/blog/chaos-practice-in-tidb/
  • [ ] https://medium.com/@siddontang/use-chaos-to-test-the-distributed-system-linearizability-4e0e778dfc7d

[0XFF-96]

• Golang 相关工具：https://www.yuque.com/ksco/uiondt/nimz8b ， 测试有关的
• high performance go workshop: 值得细看的仓库。https://github.com/davecheney/high-performance-go-workshop
• data internals 这本书被提及得比较多。

[0XFF-96]

值得一看的相关文章

• 三篇文章了解 TiDB 技术内幕 - 说存储 , https://pingcap.com/zh/blog/tidb-internal-1
• 说计算， https://pingcap.com/zh/blog/tidb-internal-2

[0XFF-96]

说存储

基本要求：保证数据不丢不错只是一项最基本的要求

• 能否支持跨数据中心的容灾？
• 写入速度是否够快？
• 数据保存下来后，是否方便读取？
• 保存的数据如何修改？如何支持并发的修改？
• 如何原子地修改多条记录？

TiKV 的目标是什么？

• 讨论如何实现 TiKV 这样一个高性能高可靠性的巨大的（分布式的） Map。
• 可以将 TiKV 看做一个巨大的 Map 。
• 具体的数据落地由 RocksDB 负责， 开发一个单机存储引擎工作量很大。
• TiKV 利用 Raft 来做数据复制，每个数据变更都会落地为一条 Raft 日志，通过 Raft 的日志复制功能，将数据安全可靠地同步到 Group 的多数节点中。
• 讲到这里，我们可以提到一个 非常重要的概念：Region。这个概念是理解后续一系列机制的基础。

数据分散在多台机器的典型方案

• 一种是按照 Key 做 Hash
• 另一种是分 Range，某一段连续的 Key 都保存在一个存储节点上 （Tikv 选择这种）

Tikv 中的 Region

• 以 Region 为单位，将数据分散在集群中所有的节点上，并且尽量保证每个节点上服务的 Region 数量差不多
• 以 Region 为单位做 Raft 的复制和成员管理
• TiKV 是以 Region 为单位做数据的复制，也就是一个 Region 的数据会保存多个副本，我们将每一个副本叫做一个 Replica。Replica 之间是通过 Raft 来保持数据的一致（终于提到了 Raft），一个 Region 的多个 Replica 会保存在不同的节点上，构成一个 Raft Group

[0XFF-96]

说计算

需求： 关系模型到 Key-Value 模型的映射。

• 表的元信息
• Table 中的 Row
• 索引数据
• 对上面这些数据的操作需求，主要考虑 Insert/Update/Delete/Select 。

TiDB 对每个表分配一个 TableID，每一个索引都会分配一个 IndexID，每一行分配一个 RowID（如果表有整数型的 Primary Key，那么会用 Primary Key 的值当做 RowID），其中 TableID 在整个集群内唯一，IndexID/RowID 在表内唯一，这些 ID 都是 int64 类型。

如何进行元信息管理？ 表中的数据和索引是如何映射为 KV，本节介绍一下元信息的存储。Database/Table 都有元信息，也就是其定义以及各项属性，这些信息也需要持久化，我们也将这些信息存储在 TiKV 中。

• TiDB 使用 Google F1 的 Online Schema 变更算法。

SQL 架构层

[0XFF-96]

为什么需要调度？为什么需要 PD 这个组件。

TiKV 集群是 TiDB 数据库的分布式 KV 存储引擎，数据以 Region 为单位进行复制和管理，每个 Region 会有多个 Replica（副本），这些 Replica 会分布在不同的 TiKV 节点上，其中 Leader 负责读/写，Follower 负责同步 Leader 发来的 raft log。了解了这些信息后，请思考下面这些问题。（自己脑补）

[0XFF-96]

Tidb 101

course: https://learn.pingcap.com/learner/course/6