名词解释

FEC：Forward Error Correction，前向纠错

FEC 是一种通过在网络传输中增加数据包的冗余信息，使得接收端能够在网络发生丢包后利用这些冗余信息直接恢复出丢失的数据包的一种方法。

FEC 的基础理论：异或

异或的规则

两个值不相等则为 1，相等则为 0；

0 ^ 0 = 0
1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1

注：按位异或 ^，则是把两个数转换为二进制，按位进行异或运算。

异或的特性

恒等律：X ^ 0 = X
归零律：X ^ X = 0
交换律：A ^ B = B ^ A
结合律：A ^ (B ^ C) = (A ^ B) ^ C

注：可以通过数学方法推导证明，我们这里只需要记住这些规则即可，后面有大量的应用。

XOR 的应用案例

有了这些 XOR 的基础理论，我们看看它是怎么应用到实际中的 “校验” 和 “纠错” 的。

奇偶校验（Parity Check）

判断一个二进制数中 1 的数量是奇数还是偶数（应用了异或的 恒等律 和 归零律）：

// 例如：求 10100001 中 1 的数量是奇数还是偶数
// 结果为 1 就是奇数个 1，结果为 0 就是偶数个 1
1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1

这条性质可用于奇偶校验（Parity Check），每个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位粗略地判断接收到的数据是否有误。

磁盘阵列 - RAID5

使用 3 块磁盘（A、B、C）组成 RAID5 阵列来存储用户的数据，把每份数据切分为 A、B 两部分，然后把 A xor B 的结果作为 C ，分别写入 A、B、C 三块磁盘。最终，任意一块磁盘出错，都是可以通过另外两块磁盘的数据进行恢复的。

实现原理：应用了异或的 恒等律 和 结合律

c = a ^ b
a = a ^ (b ^ b) = (a ^ b) ^ b = c ^ b
b = (a ^ a) ^ b = a ^ c

基于 XOR 的 FEC

假设网络通信有 N 个 packet 需要发送，那么，可以类似上述 RAID5 的策略，每 2 个 packet 生成一个 FEC packet，这样，连续的 3 个 packet 的任意一个 packet 丢失，都能通过另外 2 个恢复出来的。

但考虑到每 2 个 packet 就产生 1 个 fec packet，冗余度可能有点高（比较浪费带宽），我们能否每 3 个或者每 N 个 packet 再产生一个 fec packet 呢？当然可以，我们以每 3 个 packet（A、B、C） 产生 1 个 fec packet（D）为例来推导一下：

d = a ^ b ^ c
a = a ^ (b ^ b) ^ (c ^ c) = (b ^ c) ^ (a ^ b ^ c) = b ^ c ^ d
b = (a ^ a) ^ b ^ (c ^ c) = (a ^ c) ^ (a ^ b ^ c) = a ^ c ^ d
c = (a ^ a) ^ (b ^ b) ^ c = (a ^ b) ^ (a ^ b ^ c) = a ^ b ^ d

由上述公式推导即可知道，这 4 个 packet，任意丢失 1 个 packet，均可以由其他 3 个 packet 恢复出来。

对象存储 - EC 纠删码

一些互联网云计算公司提供的对象存储服务，都会宣称自己具有极高的数据可靠性，使用了如三副本技术、EC 纠删码技术等等，后者大致方案如图所示：

图中采用的是 8+4 的纠删码策略（即：原始数据切割为 8 份，计算出 4 份冗余信息），将这 12 份分别存储在 不同机柜的 12 台不同节点上，即使同一时刻出现多台节点（至多 4 台）损坏或不可访问，只要有不少于 8 个节点可用，数据即可恢复。

不知道大家看出来点什么没有？相比于上面基于 N 个 packet 产生 1 个 FEC packet 的方案，这种 K + M 的纠删码策略具有更好的扛丢失能力，总结下来就是：

通过 K 个有效数据，产生 M 个 FEC 冗余包，这 K + M 个数据，任意丢失 M 个数据，都能把 K 个有效数据恢复出来。

其实这种方案，最早也是应用于网络传输领域的，只不过被借用到存储领域来提高磁盘的利用率。要实现这种 K + M 的 FEC 策略，使用简单的 XOR 异或来推导比较难，需要借助矩阵相关的计算，实现方案有很多种，下面简单介绍下最著名和常用的 Reed-solomon codes。

Reed-Solomon Codes

里德 - 所罗门码（Reed-solomon codes，简称 RS codes），利用该原理实现的 FEC 策略，通常也叫做 RS-FEC。网上关于它的介绍特别多，本文就不详细展开了，仅简单以示意图的形式给出大致的原理：

RS codes 编码过程

大致原理如下：假设有效数据有 K 个，期望生成 M 个 FEC 数据

1. 把 K 个有效数据组成一个单位向量 D

2. 生成一个变换矩阵 B：由一个 K 阶的单位矩阵 和一个 K * M 的范德蒙特 矩阵（Vandemode）组成

3. 两个矩阵相乘得到的矩阵 G，即包含了 M 个冗余的 FEC 数据

RS codes 解码过程

假设数据 D1，D4，C2 丢失了，则取对应行的范德蒙矩阵的逆 * 没有丢失的数据矩阵，则可以恢复出原始的数据矩阵。

大致原理如下：假设数据 D1，D4，C2 丢失了

1. 对矩阵 B 和 D，分别取没有丢失的行构成 B‘ 和 G’

2. 根据如下公式，即可计算恢复出有效数据向量 D

B' x D = G'  ->>>  D = B' 的逆 x G'

参考文章

• 感受异或的神奇
• 纠删码 Erasure Code
• https://zhuanlan.zhihu.com/p/104579290

介绍

目前，网络上可选择的Git远程仓库比较多，其中用的较多的可能就是github和bitbucket（当然，你也可以使用自己搭建的远程仓库）。github和bitbucket的主要区别在于：bitbucket创建私人库是免费的。如果你不介意自己的代码公开，那你就可以使用github。如果，你有些私人的代码的话，又需要版本控制，这时候bitbucket就满足需要了。

但是，在国内的主要问题是：网络不稳定。这样，就会经常发生git不能push的情况。所以，这时候如果你有个代理服务器，就可以通过设置使git通过代理访问远程仓库，达到家和公司代码同步的目的。

Git允许使用三种协议来连接远程仓库：ssh、http、git。所以，如果你要设置代理，

. . .

查询系统相关信息

$ cat /etc/centos-release
CentOS release 6.7 (Final)

[root@host ~]# uname -i
i386

安装gcc4.8

centos 6 的gcc版本太低才4.4.7, 要安装高版本的4.8才完全支持c++11

. . .

在了解一致性哈希算法之前，最好先了解一下缓存中的一个应用场景，了解了这个应用场景之后，再来理解一致性哈希算法，就容易多了，也更能体现出一致性哈希算法的优点，那么，我们先来描述一下这个经典的分布式缓存的应用场景。

场景描述

假设，我们有三台缓存服务器，用于缓存图片，我们为这三台缓存服务器编号为0号、1号、2号，现在，有3万张图片需要缓存，我们希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力。也就是说，我们希望每台服务器能够缓存1万张左右的图片，那么，我们应该怎样做呢？如果我们没有任何规律的将3万张图片平均的缓存在3台服务器上，可以满足我们的要求吗？可以！但是如果这样做，当我们需要访问某个缓存项时，则需要遍历3台缓存服务器，从3万个缓存项中找到我们需要访问的缓存，遍历的过程效率太低，时间太长，当我们找到需要访问的缓存项时，时长可能是不能被接收的，也就失去了缓存的意义，缓存的目的就是提高速度，改善用户体验，减轻后端服务器压力，如果每次访问一个缓存项都需要遍历所有缓存服务器的所有缓存项，想想就觉得很累，那么，我们该怎么办呢？原始的做法是对缓存项的键进行哈希，将hash后的结果对缓存服务器的数量进行取模操作，通过取模后的结果，决定缓存项将会缓存在哪一台服务器上，这样说可能不太容易理解，我们举例说明，仍然以刚才描述的场景为例，假设我们使用图片名称作为访问图片的key，假设图片名称是不重复的，那么，我们可以使用如下公式，计算出图片应该存放在哪台服务器上。

hash（图片名称）% N

. . .

Actor模型介绍

Actor模式是一种并发模型，与另一种模型共享内存完全相反，Actor模型share nothing。所有的线程(或进程)通过消息传递的方式进行合作，这些线程(或进程)称为Actor。共享内存更适合单机多核的并发编程，而且共享带来的问题很多，编程也困难。

随着多核时代和分布式系统的到来，共享模型已经不太适合并发编程，因此几十年前就已经出现的Actor模型又重新受到了人们的重视。MapReduce就是一种典型的Actor模式，而在语言级对Actor支持的编程语言Erlang又重新火了起来，Scala也提供了Actor，但是并不是在语言层面支持，Java也有第三方的Actor包，Go语言channel机制也是一种类Actor模型。

Actor的基础就是消息传递, Actor由状态(state)、行为(Behavior)和邮箱(mailBox)三部分组成 :

• 状态(state)：Actor中的状态指的是Actor对象的变量信息，状态由Actor自己管理，避免了并发环境下的锁和内存原子性等问题
• 行为(Behavior)：行为指定的是Actor中计算逻辑，通过Actor接收到消息来改变Actor的状态
• 邮箱(mailBox)：邮箱是Actor和Actor之间的通信桥梁，邮箱内部通过FIFO消息队列来存储发送方Actor消息，接受方Actor从邮箱队列中获取消息

. . .

最近因某些原因重装了Win10, 虚拟机也需要重装, 记录一下过程, 供以后查阅, 以免走更多弯路

一些常用命令

• scp :
  • 比如把自己windows上的某个文件test.py上传到某台linux上, 则在windows上用git bash到达这个文件所在的目录然后输入命令scp test.py hlh@192.168.80.8:/home/test_dir
  • 下载则把命令顺序反过来:
• make && make install 之前用configure的时候记得用--prefix指定安装目录, 这样就只会安装到这个目录不会分散到各处, 卸载的时候就很方便, 比如编译安装python3.8的时候就会有类似如这样的命令:

  $ ./configure --prefix=/usr/local/python3 --enable-optimizations $ make $ make install

需准备的工具和材料

• 虚拟机软件
• Ubuntu : 我用的是16.04版本的ubuntu的server版本(不是desktop桌面版)
• 建议给虚拟机分配20G硬盘空间
• 建议给虚拟机分配4G内存

. . .

最近因某些原因重装了Win10, 记录一下过程, 供以后查阅, 以免走更多弯路, 搞得新装的Win10都一堆广告…

目的

• 可以格式化系统盘
• 原版Win10, 正版激活(某宝买一个非一次性的可重装的激活码, 用这种激活码激活过的机器, 重装后会自动激活的)
• 装完没有广告和预装的垃圾软件 : 不要用大白菜和老毛桃之类的, 否则装完就会有一堆垃圾软件和改过的主页, 真是无利不起早.

. . .