JamhusTao の Blog

引入：什么是一致性哈希？ 分布式集群与负载均衡 一个服务，例如一个网站为了方便管理通常由两部分组成：web 服务和对象存储服务。web 服务直接与用户建立连接，并且对用户请求进行解析、逻辑处理与响应。但是 web 服务通常是无状态的（可能会有一些缓存），这时就需要对象存储服务用来保存用户数据等信息。因此我们首先假设我们的架构由 web 服务（websvr）和对象存储服务（osssvr）两层组成。 当业务增长，服务的使用数量上升，这时就需要将 web 服务和对象存储服务拆分到两台机器上；当业务继续增长 ，一台 web 服务器和一台存储服务器无法继续承受业务压力，这时就需要构建 ​分布式集群 。 对于 web 服务来说这个过程很简单，由于 web 服务是无状态的，因此任何 web 服务可以处理任何用户的请求。但对象存储不同，不同的数据需要被路由到正确的位置。例如 userid = 100 的用户第一次接入到 websvr1，websvr1 随意（例如就近）将该用户的一个操作信息（例如注册）存储到了 osssvr1；第二天该用户接入到了 websvr4，于是 websvr4 路由到 oss ...

引入：一个有趣的游戏先丢给大家一个著名的问题： 监狱中甲乙两人密谋越狱，这需要找到逃离监狱的秘密出口。在狱长的房间中有一个国际象棋棋盘，在它 8×88 \times 88×8 的棋格上各有一枚硬币，有正有反；同时秘密出口恰好可能出现在监狱的 646464 个角落。甲、乙两人事先并不知道棋盘上硬币正反，当然也不知道秘密出口的位置，不过他们在一天晚上商量出了逃离监狱的方案。 第二天甲乙两人分开了。这天早上甲看到了棋盘上所有硬币的正反，同时也知道了钥匙的位置，但他没有机会与乙进行任何交流。甲找到机会偷偷翻动了一枚硬币，然后离开了狱长的房间。下午乙看到了甲留下的棋盘，于是就计算出了秘密出口的位置，并成功逃离。 请问甲乙协商了怎样的方案成功越狱？已知甲乙约定 8×88 \times 88×8 的棋格对应恰好 646464 个角落；同时约定中甲翻动一枚棋子，约定中甲不可能不翻动棋子。 这个有趣的问题就与我们今天要讲的海明校验码非常相关。我相信你在看完这篇文章后也能解决这个问题，当然你也可以尝试直接解决这个问题，直接解决这个问题可能非常有挑战性。 好吧，跳过这个问题完全不影响对后文海明校验码的理解。 ...

前言 一直在想是否要写这篇题解，但最后还是打算整理帮助有需要的人，因为到现在没看到有人正经写过一篇题解。 这篇题解包含标准答案，最后几题同样给出暴力做法。 另外这些是赛后回顾代码，可能存在赛时代码正确，此处代码存在瑕疵的问题。关于解释有问题的欢迎喷。 实测最后三题都只拿暴力分的话 国一 是稳稳前排；身边数据，约莫再丢一整题分（20），大概 国一 后排。身边有不少有水平的选手，但是先天对 OI 赛制不适没能拿到好成绩，当然真有水平的选手也不会在意这点得失；另外就是太追逐正解，导致该拿到的分没有拿到，拿我个人举例，这是我第二次参加蓝桥杯，去年因为太较真拿了国二。这次本来没有打算较真附上正解，但最后想着想着就都写了正解，希望对你有帮助。 A 题：合法密码 枚举 check 一下就好，个人认为答案应该是 400，不少人答案是 618 还是对题意理解不一样。我觉得 618 的题意理解也算合理的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748// A: 合法密码#inc ...

前言 这个部分来自课程 MIT6.824，这门课每节课都会精读一篇分布式系统领域的经典论文，并由此传授分布式系统设计与实现的重要原则和关键技术。 个人认为阅读论文比课程本身更加重要，课程围绕论文展开，可以快速获取论文的核心观点，课程的一切细节以及未提及的内容在论文中具有最详细的解释。另外教授会从当今立场（2022）评价论文的意义和缺陷，同时可能补全论文中缺失的信息解释，教授对学生提问的一些回答具有很好的启发意义，这些内容不被包含在论文中。 本文综合课程内容和论文核心观点，并参考一些其他资料整理，希望对你学习课程有所帮助。 课程官方：https://pdos.csail.mit.edu/6.824/ 博主整理：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824 B 站录屏：https://www.bilibili.com/video/BV1qk4y197bB ​请阅读论文 VMware FT： https://pdos.csail.mit.edu/6.824/papers/vm-ft.pdf 相关推荐：Debuggin ...

前言 这个部分来自课程 MIT6.824，这门课每节课都会精读一篇分布式系统领域的经典论文，并由此传授分布式系统设计与实现的重要原则和关键技术。 个人认为阅读论文比课程本身更加重要，课程围绕论文展开，可以快速获取论文的核心观点，课程的一切细节以及未提及的内容在论文中具有最详细的解释。另外教授会从当今立场（2022）评价论文的意义和缺陷，同时可能补全论文中缺失的信息解释，教授对学生提问的一些回答具有很好的启发意义，这些内容不被包含在论文中。 本文综合课程内容和论文核心观点，并参考一些其他资料整理，希望对你学习课程有所帮助。 课程官方：https://pdos.csail.mit.edu/6.824/ 博主整理：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824 B 站录屏：https://www.bilibili.com/video/BV1qk4y197bB ​请阅读论文 VMware FT： https://pdos.csail.mit.edu/6.824/papers/vm-ft.pdf VMware FT 是应用 ...

前言 这个部分来自课程 MIT6.824，这门课每节课都会精读一篇分布式系统领域的经典论文，并由此传授分布式系统设计与实现的重要原则和关键技术。 个人认为阅读论文比课程本身更加重要，课程围绕论文展开，可以快速获取论文的核心观点，课程的一切细节以及未提及的内容在论文中具有最详细的解释。另外教授会从当今立场（2022）评价论文的意义和缺陷，同时可能补全论文中缺失的信息解释，教授对学生提问的一些回答具有很好的启发意义，这些内容不被包含在论文中。 本文综合课程内容和论文核心观点，并参考一些其他资料整理，希望对你学习课程有所帮助。 课程官方：https://pdos.csail.mit.edu/6.824/ 博主整理：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824 B 站录屏：https://www.bilibili.com/video/BV1qk4y197bB ​请阅读论文 GFS： https://pdos.csail.mit.edu/6.824/papers/gfs.pdf 什么是 GFS？ 在 GFS 出现之前，分 ...

前言 这个部分来自课程 MIT6.824，这门课每节课都会精读一篇分布式系统领域的经典论文，并由此传授分布式系统设计与实现的重要原则和关键技术。 个人认为阅读论文比课程本身更加重要，课程围绕论文展开，可以快速获取论文的核心观点，课程的一切细节以及未提及的内容在论文中具有最详细的解释。另外教授会从当今立场（2022）评价论文的意义和缺陷，同时可能补全论文中缺失的信息解释，教授对学生提问的一些回答具有很好的启发意义，这些内容不被包含在论文中。 本文综合课程内容和论文核心观点，并参考一些其他资料整理，希望对你学习课程有所帮助。 课程官方：https://pdos.csail.mit.edu/6.824/ 博主整理：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824 B 站录屏：https://www.bilibili.com/video/BV1qk4y197bB ​请阅读论文 MapReduce： https://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf 什么是 MapRe ...

本文将首先介绍布隆过滤器 (Bloom Filter) 是如何工作的，然后我们将形式化推导布隆过滤器的误判率。布隆过滤器是一种使用多哈希的方式判断元素是否属于集合的数据结构，他的优势在于不需要存储任何键值，非常节约空间且高效。

时间线 流程概况 240425 笔试 应该都写出来了，个别问题存疑。 240527 拒绝了面试邀约，因为这段时间没什么时间。 笔试 Part1 选择题 回忆几道印象深刻的题，其余部分概括一下。 甲乙丙丁戊其中四人发言说 “XX 是我的 XX (亲戚) 的 XX (亲戚)”，请问谁未发言。（岳母和女婿是啥来着…） 有三个小组各 10 / 15 / 25 人，其中女生 3 / 7 / 5 人，问随机从其中一个组选两人，已知后选出的为男生，则先选出为女生的概率？ A. 13;  B. 29;  C. 2061;  D. 2990;A.~\frac{1}{3};~~B.~\frac{2}{9};~~C.~\frac{20}{61};~~D.~\frac{29}{90};A. 31​;  B. 92​;  C. 6120​;  D. 9029​; （完全不会，五次算出五个答案，没一个在选项里） 一副扑克 54 张，均分 3 副，一副 18 张。问大小王在同一人手中的概率是多少？（吉比特你超爱考概率啊！） 剩余一道读代码题：本质是数二进制 111。 两道时间复杂度分析，余下都是 ...

前言 本章我们将通过几个示例，本文以 Linux 系统为例，深入 C 语言的汇编代码，这能帮助我们更好理解程序的工作原理，例如栈的工作机制。 本文需要 C 语言基本语法、GCC 编译、GDB 调试的前置芝士。 如何调试 C 语言汇编代码 不需要安装额外的工具，直接使用 GDB 进行汇编代码调试即可，当然通过配置你的 IDE 也可以进行更舒适的调试。 首先书写源文件，假设我们已经书写了 main.c 文件，然后按照下面的方法编译： 12gcc main.c -o main.s -S # 生成汇编代码gcc main.s -o main -g # 附加调试信息 我们只要不在源代码中添加调试信息，而只在汇编代码中添加调试信息，即可直接使用 GDB 调试汇编代码。 12gdb main# 正常添加断点和运行代码, 使用形如 p $eax 查看寄存器 一段简单的汇编代码 在这段代码中，我们不对代码如何工作作介绍，仅用于介绍 C 语言汇编代码的基本框架。在之后的代码中，我们将不再解释框架性质的代码。 源码解释 1234567#include <stdio.h>int ma ...