• Distributed Storage System Basic.

• Distributed Storage System Basic.
• Here is the basic of storage and distributed system, including the knowledge of data structure and some benchmarks.
• The content is based on the reading list recommended by TinyKV and I will present my understanding.
• Only summary, not details.

Basic

• TinyKV Reading List

Index of Reading List

• It may not be newst version, so you can view the newst index by clicking the above link. And here is following the commit a5c29fcf0702f90e969af5b7bcdc8797ce1898a0

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

Summary

Index

Disk I/O

• Flavors of I/O
• Amplification and RUM

B-Tree

• Database Internal B-tree Summary