分布式系统,程序语言,算法设计

概述

记录下在实现6.824 lab2 raft 的一些想法和经验,聊以备忘。

实验概述

6.824是MIT的一门分布式课程,我跟的是2018 spring 。在第二个实验中要求简单实现一个分布式一致性协议–raft

这是一个专为方便教学和工程实现所设计的协议,它将协议拆解为几个相对独立的模块–leader选举,log复制,安全保证。论文里图二基本给出了Raft的所有实现细节,可谓字字珠玑。但也因为太微言大义了,导致有些状态转换分散在不同描述中,假如你真只照着这幅图实现,很容易遗漏些细节。

阅读全文 »

概述

以前对二分查找的认识只停留在有序数组查找给定整数上,后来发现一类问题都可以用二分的思想来做,概括来说就是:如果要求的结果所在的集合(值域)和要搜索的数的集合(定义域)存在单调(映射)关系,就可以通过二分思想来解决,说起来有点抽象,后面将用几个例子来说明。

二分思想以其每次迭代将规模砍一半的效率,有着极其广阔的应用。

本文分两大部分,第一部分对二分查找的各个细节探讨;第二部分拓展二分查找为一般的二分思想。

阅读全文 »

问题

在进行模块化的时候,试图将诸如SearchListener, CallManager 的模块从MainActivity中拆出来,然而在响应事件的时候,不可避免的需要改变其他资源状态,那么就需要获取其句柄。由此还需要把MainActivity作为句柄传入代码。

阅读全文 »

写程序的时候,规模小,尚不能感觉设计模式的重要性。等规模一上来,需求一迭代,一个应用了恰当设计模式的工程,总能以最小的代价进行最快的迭代。
但是一个奇怪的点是,我总记不住具体的实现所对应的设计模式的名字,但是对他们背后的设计思想,却是念念不忘——依赖于抽象而非具体;对扩展开放,对修改关闭;

阅读全文 »

FileSystem

FileSystem是一个抽象基类,为LocalFileSystemDistributedFileSystem提供一些公共方法。通过HashMap:name-> filesystem,维护所有使用的的文件系统,其key或者为“Local”,或者为“Host:Port”(标识一个NameNode)。
继承了Configured类,可以通过配置加载一些基本参数,保存在Configuration中。
为了提高可靠性,给每个文件生成一个校验和,保存在.*.crc隐藏文件中。

编程中有很多有意思的细节,看到了,就记在这里。

| 简化判断

一堆数按位或,只要有多于一个数为负,则结果为负。

1
2
3
4
5
6
7
8
public void write(byte b[], int off, int len) throws IOException {
if ((off | len | (b.length - (len + off)) | (off + len)) < 0)
throw new IndexOutOfBoundsException();

for (int i = 0 ; i < len ; i++) {
write(b[off + i]);
}
}

from: FilterOutputStream

上一篇把一些零碎的小类集在一起,凑成一篇。这篇打算对比较长的一个类DataNode读读。
每个DataNode代表一个数据节点,对应某台机器的一个文件夹,本质上是一定数量的Block的集合,能够和NameNode,client以及其他DataNode进行通信,以对该Block集合进行操作,主要包括client的读和写,其他DataNode block的复制,以及响应NameNode操作,进行删除等操作。
具体实现来说,数据结构上,维持了一个block到byte array的表;执行时,DataNode内部是一个无限循环,不断询问NameNode,报告状态(心跳),执行命令(RPC)

  1. 状态信息。DataNodeInfo:总大小,剩余大小,上次更新时间。
  2. 执行命令。
    • 客户端读写Blocks
    • 让其他DataNode复制Blocks
    • 删除某些Blocks

此外,DataNode还维持着一个Server Socket以处理来自Client或者其他DataNode请求。DataNode会将其对外暴露的host:port提交给NameNode,后者会将该信息进一步下发给相关的其他DataNode或者client。
(摘自类注释)

阅读全文 »