Distributed Storage System Basic

发布于 2020-06-12 | 标签: 存储、分布式 | 5分钟 | 723字数 | 浏览量::

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

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
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)

Benchmark & Testing

sysbench (Optional)
go-tpc (Optional)
- https://github.com/pingcap/go-tpc
go-ycsb
Chaos

Summary

Index

Disk I/O

B-Tree

Database Internal B-tree Summary

本文作者： Elvis Zhang
本文链接： https://blog.shunzi.tech/post/distributed-storage-system-basic/
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

# 存储 # 分布式

Flavor of IO 上一篇

Head First Golang 下一篇