深入 MIT 6.824:实现 LeaseRead 和全异步 shardkv

深入 MIT 6.824:实现 LeaseRead 和全异步 shardkv

「生活,就是当你忙着做其它计划时,发生在你身上的事」:要问起开始学 MIT6.824 的缘由,这是一句恰如其分的描述。一个学期结束,原本的计划是深入研究一下编程语言和形式化验证,然后换到一个和操作系统关系更大的岗位;不知不觉却变成了写个数据库,在做操作系统相关的工作前先试试存储的方向——刚放假时我还对自己说,我是绝对不会喜欢上存储的。也许人们对自己还没下过苦功的事情,就是提不起劲的吧?

于是春节假期开始,明显一年比一年淡漠的气氛(今年甚至没看拜年祭)环绕,倒也是为思考提供了较好的场所:没有多少亲戚前来拜访,也就没有多少生硬蹩脚的玩笑和紧张尴尬的时刻需要消化。到现在,整一个月,算是把 MIT6.824 彻底完成了。

老实说,这并不如我想象中的难。在上手之前总觉得 824 的高不可攀,非顶尖学府的高手不可;但在自己突然完成之后却发现虽然过程并不是「出乎意料地」顺利,但产出确实是出乎意料地好。

我已开源了这份实现。这一实现稳定通过了 Lab 1 到 Lab 4 的每一个测试点(至少 1000 次,通常 2000 次;其中 Linearizability2B 通过了 10000 次——这么做是因为在提出 porcupine 的文章中,作者说TA “没有找到任何一个线性一致性测试不能发现的错误”),完成了 Lab 4 的两个 Challenges(即标题中的全异步 shardkv),同时还额外实现了 LeaseRead with noop 的优化,使得读请求无需经共识层——本文中提出的解决方案或许是对如何在 MIT 6.824 中实现这一优化的较好参考。另一方面,我谨慎地组织了代码结构,保证代码的粒度适宜——既不引入过多重复,又不引入过多函数(是不是想起了洗试管的原则?嘿嘿),每一次修改都执行了充分的回归测试,并且非常谨慎地操作 squash 和 cherry-pick,保证修改最少、最必要,且和我完成 Lab 的进度严格对应:这意味着读者可以从代码的提交历史中明确看到某个 Lab 和下一个 Lab 之间应要做哪些修改。

阅读更多
Self:编程语言的变革仍未到来

Self:编程语言的变革仍未到来

本文是一篇小作品

本文引用并翻译了在 HOPL III 上发表的论文 Self(DOI: 10.1145/1238844.1238853)中的倒数第二节。在 ACM Digital Library 收录的所有 HOPL(History of Programming Languages 论文中,这篇论文的下载量排到了第八位。

我将要引用并翻译的段落出自论文的倒数第二节 “8. Conclusion”(8. 结论) 。在读完全文后,我在我的私人群里如此表达我的感受:

阅读更多
计算机领域的三个重要思想:抽象,分层和高阶

计算机领域的三个重要思想:抽象,分层和高阶

昨晚看了点比较有意思的东西,于是决定写一篇文章简单讲一下。

本文致力于概括我对计算机界三个重要思想的体会和认识。我希望做的并不是简单的百科全书式的列举(“A 体现了抽象思想;B 体现了分层思想…”),而是从这些思想中选取几个我个人较有体会(或者是我单纯觉得十分有趣)的侧面拿来细讲。这些侧面仅仅能覆盖这些思想应用范围中十分微小的一部分,它们并不是最有代表性的、亦非最为重要的——仅仅因为,我个人对这点侧面有些体会,或者我个人认为它比较有趣而已。

同样需要强调,和本博客大多数文章一样,本文个人意见色彩浓厚——本文并不客观,更绝不权威。

为方便行文,文中提到的大量引述来源不会标号、也不会在文中注明。关于攥写时参考的资料,请参见文末 “参考文献”。

阅读更多
从 SML 到 Scala:简单考察 typeclass 范式的演变和各种实现,以及🎉🎉🎉

从 SML 到 Scala:简单考察 typeclass 范式的演变和各种实现,以及🎉🎉🎉

本文是一篇「小作品」

这次要是还写巨长我就吃了渚薰((((大雾)

Typeclass 范式是对于 表达式问题 Expression Problem 的一个重要的解。在我了解的编程语言范式中,个人认为,typeclass 范式是较为优雅的一个。本文将简要考察这一范式本身,以及更加重要的:它在各种编程语言中到底如何落地。具体而言,本文将在各种落地语言中构造同一个示例:一个类似 Ruby 中的 Comparable mixin,或者 Java 中的 Comparable 接口,并且演示这些结构如何对既有的类型同样具备可扩展性。

阅读本文需要一定的代码基础,尤其是对 typeclass 范式的认识和相关的编码经验。本文并不会对文中的举例作详尽解释。

阅读更多
简单聊聊编程语言的哲学,以及关于 Rust 的一些想法 (1)

简单聊聊编程语言的哲学,以及关于 Rust 的一些想法 (1)

本文是一篇「小作品」。

草,写着写着发现越写越长,一点也不「小」嘛。

或许我真的应该尝试一下「小」作品的体例才是。

我的长期TODO列表里已经躺着五六篇以“博文”开头的条目——原本想着寒假一周一篇很快就能写完,然而到现在也没动笔。爆肝填坑了一个星期,今天实在有点累,不大想打开 RustLion,于是把这篇坑了很久的文章写一写。

在这几篇坑了这么久的文章中其实有一篇已经写了前半部分了,然而咕了太久后半部分要写什么都有点不大记得,于是只能前功尽弃…

本文的主要内容是从我个人的经验出发,简单聊聊对于 Rust 的一些想法和体会。我会尽量避开诸如 “文档质量良好”、“很有特点” 这类宽泛的概括,而尽量将自己在使用 Rust 编程的过程中感受到的一些特别之处、尤其是和此前经历的不同之处拿来说说。我期望如此行文能使得本文对无论是 Rust 初学者、还是仍在观望的开发者甚至是 Rust 老手们都能带来一定启发。

  可能过时

2022/11/17:经过快两年的学习和工业实践,我对编程语言又有了新的认识。本文中对于 Ruby 的评论、尤其是对于 Ruby 优于 Python 的评论,已不再是我当前的看法。不过,很大程度上我仍然保持着占本文主要篇幅的对 Rust 的各种见解,但由于在过去的一年间我的兴趣发生了重大转移(转向系统、尤其是数据系统的领域),我现在较少使用 Rust 语言(这恰恰是由于在本文中提出的一系列 Rust 语言设计不尽人意的原因),较少关注 Rust 语言社区,也更少广泛地思考编程语言本身,本文中的许多观点可能不再能反映编程语言发展的最新情况。

如上文所述,占本文主要篇幅的观点并未明显改变,如果将来发生这种情况,我会修订或补正本文。

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×