沧海月明

With great power comes great responsibility

0%

Extendible Hash Table 属于动态哈希的一种,网上有很多关于它的介绍,但是真的在实现它的时候,或多或少有着很多问题。网上很多教程光讲怎么扩容,不讲收缩,而且网上很多都是概念性的东西,不讲代码实操。因 CMU 15-445 的课程需要,自己捣鼓了一下算法流程,这里分享一下。

在看之前请自行了解 Extendible Hash Table 的概念:

https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/

http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/3-index/extensible-hashing.html

约定

在开始讲解算法前,我们先进行一些规则的约定。

  • 目录叫 Directory, 桶叫 bucket,bucket 在 directory 的序号叫 index。
  • 每一个 bucket 的空间指向一个 page,存在多个 bucket 公用同一个 page 的情况
  • 扩容叫 grwo,收缩叫 shrink。
  • 初始的 $GlobalDepth=0$,且只有一个 Bucket,该 bucket 的 $LocalDepth=0,Index=0$。
阅读全文 »

因为目前 CS 144 的实验项目没有全部放出,本笔记会随着课程的更新而更新。

如果需要代码,可以邮件联系我。

环境搭建

这个实验是在虚拟机进行,我们不可能使用 vim 敲代码,更不可能在虚拟机里面装一个图形化界面,然后在里面开发(套娃?)

这里给出两种方法:

VS Code 远程开发

阅读全文 »

因为目前 cmu 15-445 的实验项目没有全部放出,本笔记会随着课程的更新而更新。

只有我的实验满分通过 gradescope 我才会分享我的心得,帮助大家少踩坑。

Project 0

Project 0 相当于一个热身项目,用于检查学员是否具备正常的 C++ 能力来进行这一门课程。

因为我学习这门课程前不会 C++,所以我没能力,因此我没做。。。

阅读全文 »

满打满算花了 25 天完成了 2021 MIT 6.824 的 4 个 lab,这里记录下自己遇到的坑和设计思路,为后续者参考。

这里个人给的难度评级是 Lab 2 > Lab 4 >> Lab 3 = Lab 1。

这里我就简单的记录下自己的设计思路和遇到的坑。

如果大家想要参考更加具体的代码实现,可以看看 https://github.com/LebronAl/MIT6.824-2021

Lab 1 MapReduce

阅读全文 »

FLP 这篇论文在分布式领域有着重要的作用,当然,这篇文章也写得晦涩难懂。这是第一篇我死扣每个字读下来的分布式论文,十分吃力,在此记录下,并且竟可能写的简单,希望能够帮助初入分布式计算的新人们够更加容易理解 FLP 论文。当然再怎么简单,数学的符号是跑不了的,但是不要害怕,一个一个字看下来即可。

论文原文的名字叫:Impossibility of Distributed Consensus with One Faulty Process。简单的叫法是 FLP-Impossibility。

如果文章中有些地方写的不对,请留言指正。

前言

FLP 定理相当于给分布式一致性算法订上了棺材板,它证明了根本不可能实现一个真正意义上的一致性算法。

阅读全文 »

此文章仅为笔记,不推荐大家观看。

TCP Header

img

上面每一个方格代表 8 位,所以序列号有 4x8 = 32 位

  • 源端口,目标端口:TCP 里面不包含 IP 地址,因为那是网络层(IPv4)应该干的事情。
    • TCP 通过源 IP,端口,目标 IP,端口 4 个特征标识一个 TCP 连接。
    • 本地向远程80端口发起请求时,本地的端口是随机申请的。
  • 序列号:Sequence number,为 32 位的无符号整数。用于接收端收到数据进行排序,因为 IP 层不保证数据有序。
    • 一开始序列号会随机生成一个初识序列号。在建立连接时,通信双方通过 SYN 报文交换彼此的 ISN。
    • 序列号回绕处理,因为序列号随机生成,所以同一个连接的序列号是有可能溢出回绕(sequence wraparound)的。Linux 通过 (_s32)(seq1-seq2) < 0 来处理,即使绕回了,因为从无符号强制转换为符号,也会变成负数。
  • 确认号:TCP 使用确认号(Acknowledgment number, ACK)来告知对方下一个期望接收的序列号,小于此确认号的所有字节都已经收到
    • 不是所有包需要确认,比如 ACK,不然不是无限循环确认了。
    • 不是收到了数据包就立马需要确认的,可以延迟一会再确认。
    • 确认号永远是表示小于此确认号的字节都已经收到。
  • Flags:我们通常所说的 SYN、ACK、FIN、RST 其实只是把 flags 对应的 bit 位置为 1 而已,这些标记可以组合使用,比如 SYN+ACK,FIN+ACK 等
    • SYN(Synchronize):用于发起连接数据包同步双方的初始序列号
    • ACK(Acknowledge):确认数据包
    • RST(Reset):这个标记用来强制断开连接,通常是之前建立的连接已经不在了、包不合法、或者实在无能为力处理
    • FIN(Finish):通知对方我发完了所有数据,准备断开连接,后面我不会再发数据包给你了。
    • PSH(Push):告知对方这些数据包收到以后应该马上交给上层应用,不能缓存起来
  • 窗口大小:上面只有 16 位(窗口最大只有64KB),这是历史设计问题。所以现在 TCP 引入了 窗口缩放因子。缩放因子可以把窗口扩大到原来的 $2^n$ 次方。比如缩放因子为7,则原来的窗口大小乘以 $2^7=128$ 。例如下图,窗口大小为 $6379 \cdot 64=408256$ 。
阅读全文 »

Terms

  • Critical section: piece of code that accesses a shared resource.
  • Race condition: 多个线程同时进去 critical section。
  • Indeterminate:指程序在多线程情况下,程序结果不唯一。
  • Mutual exclusion:排他。

Locks

Evaluating Locks

  • Mutual exclusion
  • Fairness 当大量线程同时访问时,是否存在某些 thread starve 的可能。
  • Performance
阅读全文 »

布隆过滤器可以使用极少的空间来判断一个元素是否存在某一个集合中,本文不具体讨论布隆过滤器的原理,而是探讨如何实现一个可用的布隆过滤器。

实现源代码:https://github.com/Smith-Cruise/java-bloom-filter

本文代码提取自 Apache ORC 项目。

基本概念

这里附带一些链接,适合不了解布隆过滤器的人阅读。

阅读全文 »

最近阅读 HDFS 的源码,看到在 DFSClient 中很多地方用到了 HTrace 这款框架,所以特意学习下。

HTrace 是一款由 Cloudera 开发的分布式追踪框架,在设计上借鉴了 Google 的 Dapper 论文,虽然 HTrace 已经停止了更新,在 Apache 里面孵化失败了,但是它现在任然被 Hadoop 和 HBase 所采用。

HTrace 产生的数据通常不够直观,我们还会使用 Zipkin 进行数据的可视化。

作用

在分布式系统中,用户发送的一个 RPC 请求,会在后台产生多个请求。例如用户通过 HDFS Client 上传一个文件,中间可能涉及到从 Client 到 NameNode,Client 到 DataNode,NameNode 到 DataNode 的 RPC 请求。但是我们该如何追踪这些具体 RPC 请求的性能呢?传统的方法只能监控到 Client 上传文件整一个过程的耗时,而无法捕捉到其间各个请求的性能,从而无法定位性能产生瓶颈的地方。这也就是 HTrace 所需要解决的问题。

阅读全文 »