-
TinyKV Project4 Transactions
这一节实现的事务本应该需要和 TinySQL 配合使用，但是因为我们只有实现 TinyKV 部分，所以有些地方看起来有些割裂。 Percolator 首先说明的一点是，Percolator 基于单行事务实现了多行事务，Google BigTable 能够提供单行事务。在这里 TinyKV 也会通过锁来保证单行数据的原子性（但是单行事务好像没有，可能要结合 TinySQL）。Percolator 这…- 13.7k
- 0
-
TinyKV Project3 MultiRaftKV
这一节中，最难的就是 Project 3B，引无数英雄竞折腰！！当然撑过 3B，你就解放了。 Membership Change 在 Project3A 中我们需要实现 Leader Transfer 和新增或移除一个 Region 里面的节点，这里并不是很难但是你要处理好细节，不然就是 BUG 满天飞。 Leader Transfer Leader transfer 会作为一条 Admin 指令… -
TinyKV Project2 RaftKV
这一节需要我们实现 Raft，TinyKV Raft 这部分很多都是抄 Etcd 的 Raft 模块。你可以注意到连测试用例都很像。所以这一节我拿到手就会做啊，首先去 Etcd clone 一份源码。我抄的是 Etcd 3.5.1 版本，也就是目前最新版。 TinyKV 中的 Raft 和 6.824 中的 Raft 有很大的不同。这里将整个 Raft 设计为一个状态机，从一端输入消息，从另一端输…- 1.5k
- 0
-
TinyKV Project1 Standalone KV
这一节实验要求我们基于 badger 实现一个支持 Column Family 的 KV 数据库。 Column Family，也叫 CF，这个概念从 HBase 中来，就是将多个列合并为一个CF进行管理。这样读取一行数据时，你可以按照 CF 加载列，不需要加载所有列（通常同一个CF的列会保存在同一个文件中，所以这样有很高的效率）。此外因为同一列的数据格式相同，你可以针对某种格式采用高效的压缩算法…- 1.2k
- 0
-
Raft 成员变更的相关问题
之前一直没有深入了解过 Raft 的成员变更，实现也就是在 TinyKV 中搞了一个单步成员变更，以至于在面试的时候，甚至想当然以为成员变更一定要被 apply 后才生效，结果就被挂了。故这里重新梳理一遍，内容是到处扒来的，不一定正确。 直接成员变更存在的问题 如果我们把成员变更当做和普通日志一样，在 apply 时直接应用，可能会使得整个集群产生两个 leader。 当然这些问题只有当原 lea… -
分布式原子提交协议大全
在单机上实现原子提交没啥好说了，可以通过 logging 来保证，但是在分布式系统中，情况就不简单。很多人会把 2PC/3PC 这类算法叫做分布式一致性算法，但是我个人觉得它们叫原子提交协议更合适（atomic commitment protocol ），因为它们只是把多个操作融合为一个原子操作，要么全部成功，要么全部失败。具体可以看 https://exactly-once.github.io/…- 1.4k
- 0
-
Talent Plan TinyKV 白皮书
前言 最近参加了 PingCAP 的 2021 Talent Plan KV 学习营，大概就是在不到两个月的时间里完成 TinyKV。之前做完了 MIT 6.824 就被人安利过，不过那时候看了一眼 README 就被劝退了，太复杂了。好在项目最后是完成了，就是拿了个低分，挺抑郁的。 正确性：4 个项目的正确性接近了 100%，意料之中，自己是跑了 150 次 bug free 才交上去的。文档：…- 5.5k
- 0
-
2021 MIT 6.824 札记
满打满算花了 25 天完成了 2021 MIT 6.824 的 4 个 lab，这里记录下自己遇到的坑和设计思路，为后续者参考。 这里个人给的难度评级是 Lab 2 > Lab 4 >> Lab 3 = Lab 1。 这里我就简单的记录下自己的设计思路和遇到的坑。 如果大家想要参考更加具体的代码实现，可以看看 https://github.com/OneSizeFitsQuoru…- 5.6k
- 0
-
理解 FLP-Impossibility 论文
FLP 这篇论文在分布式领域有着重要的作用，当然，这篇文章也写得晦涩难懂。这是第一篇我死扣每个字读下来的分布式论文，十分吃力，在此记录下，并且竟可能写的简单，希望能够帮助初入分布式计算的新人们够更加容易理解 FLP 论文。当然再怎么简单，数学的符号是跑不了的，但是不要害怕，一个一个字看下来即可。 论文原文的名字叫：Impossibility of Distributed Consensus wit…- 2.7k
- 0
-
Amdahl’s law（阿姆达尔定律）公式推导与思考
介绍 Amdahl's law（阿姆达尔定律） 由计算机科学家 Gene Amdahl 在 1967 年提出，旨在用公式描述在并行计算中，多核处理器理论上能够提高多少倍速度，公式如下：$$S=\frac{1}{1-a+\frac{a}{n$$$S$ 为 speedup，代表全局加速倍速（原来总时间/ 加速后总时间），$a$ 为并行计算所占比例（可以并行计算代码量 / 总代码量），$n…- 3.3k
- 0
-
分布式系统中的 Partial ordering 和 Global ordering 的理解
在分布式系统中，我们在阅读关于事务一致性的论文中，经常会看到 partial ordering 和 global ordering。这里简单的说明下。 Partial ordering 部分有序。指在一系列的事件中，只保证部分的事件按照一定的顺序进行处理。 Global ordering / Total ordering 全局有序。很简单，就是所有的事件均按照一定的顺序处理。例如在一个单核系统中，… -
Lamport 逻辑时钟（Lamport Timestamp）和 Vector Clock 简单理解
Lamport 逻辑时钟（Lamport Timestamp） Lamport Timestamp 是一种衡量时间和因果关系的方法。现实生活中，很多程序都有着因果（causality）关系，比如执行完事件 A 后才能执行事件 B。 int main { create_photos(6); view_photos(6); return 0; } 比如上面的代码，我只有创建完照片 6 才能访问照片 6…
扫码打开当前页
-
￥优惠劵使用时效：无法使用使用时效：
之前
使用时效：永久有效优惠劵ID：×