深入 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 之间应要做哪些修改。

阅读更多
记忆、目光、另一种迷惘:the end of 2021

记忆、目光、另一种迷惘:the end of 2021

和这里的许多文章一样,本文的标题依然是仿照了某篇令我印象深刻的文章的标题。:-)

最近考完试就在忙课设,这两天才终于有时间把这篇文章写完…

「时间之矢向前飞逝 / 祂飞离时震颤的双翼总拍伤我的灵魂」,几个月前读到的这句诗如今无论是它的作者(是里尔克吗?)还是其全貌都已无从知晓,只觉得以这句想象力奇绝的诗句概括行将结束的整整一年,确实恰如其分。

写下上一篇年终总结(不知为何我很不喜欢「年终总结」这个词——如你所见,标题很努力地做到了不用这四个字)至今已有一年有余,而 2021 这一年,可以说是空前的烂漫和精彩。这一年,无数美好的事情,以我此前从来不敢想望的方式,完全不可预料地扑面而来(未来像盛夏的大雨,在我们还不及撑开伞时就扑面而来1):今年的许多许多段回忆都是出奇的美好,它们是如此的弥足珍贵,冥冥之中我总觉得,即便是以一个人整整一生的时间尺度来衡量,这些回忆都将在时间的长河中熠熠生辉,就像华兹华斯笔下那些总能「让我们在困顿之时为之一振」的「卓越超群、瑰伟壮丽的若干时间点」2

可是,正当世界向我们显露它那丰富多彩的衬里的同时,祂却又向我们徐徐展开了一副人们受苦受难图景的画卷。大三上已经结束,大家突然都紧张了起来,似乎才刚品尝到青春这甘醇甜美的琼浆,就要去体会人们这毫无意义地辛苦劳作、不得休息的无望图景。人们出于经济富足、出人头地等种种平凡低微的原因,在日常生活中从事各个琐碎、侮辱人才能又耗费人精神的工作,无论是不是心甘情愿,都要在就在这无尽的琐事中逐渐被「磨损」,逐渐只觉得,生活,永远在触不可及的地方,因为「此时此刻」永远是那么的无聊、那么的缺乏诗意、那么的死气沉沉——生活永远不在这里,因为生活永远在别处

这是另一种迷惘。人总要在不断的学习中成长,可是只有很少的人能够对一个领域怀有足够纯洁的热诚,从而主动地学习并自得其乐;任何成就的取得都需要决绝的努力,可是人们很难为一个虚无缥缈、触不可及的目标和「理想」长久地坚持,并摒弃种种安逸的生活方式。时日无多,回首你这过去的日子,几乎都在随性而为的自由和放纵中度过,你是否已经失去了(甚至是从未拥有过?)沉着刻苦的品格?考研还是工作?你能坚持下去吗?曾以为坦荡无比的生活最终坍缩(是的,在目光观测下)成区区几个选择而已,怎样做你才不会后悔?在被抛入 “就像海洋的生活”(广东孩子请会意地笑笑)之前,你还要做些什么?你到底想要怎样的生活,又到底是否有相称的品格和毅力来得到它?

我依然没有答案。或者确切的说,自从一个月前学期仿佛是毫无预兆地结束以来,我一直在逃避这些问题,因为我实在是无从回答。我只希望当我完成本文,为这飞快过去的 2021 做完注时,我能有一丁点儿的头绪。

  关于头图

头图摄于 2020 年 12 月,是我们乐队在学校一年一度的音乐节演出前最后一次排练。那次排练效果很好,大家都非常高兴,那晚就是这美好、珍贵回忆中的一段。图中两人未出镜:我(因为这张照片是我拍的)和我们的贝斯手(我真的没有黑贝斯——至少当时没有!)。
阅读更多

还有什么应该去写的事情?

大概两个星期以前,被朋友问到了一个问题。她问我:如果明天就是世界末日,你有没有什么想做的事?

她自己的回复是要立刻到重庆(原话大意是 “不管发生什么我都要立刻飞过去”)去吃正宗的重庆火锅,因为在这边吃到的所有火锅都不怎么样。她说,这种回复其实表明她并不对自己当下的生活感到全然满意,因为明天就是世界的终结也会想去「最后疯狂一把」,而如果是真正满意自己的生活的话,回复应该是 “该怎么过就怎么过” 才是。

这几天我也一直在想这个问题。如果明天就是世界末日,我又会去做什么呢?

阅读更多
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

×