Raspberry backup

Tools

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Partition
parted
partx, kpartx
fdisk, cfdisk

# Device
lsblk
blkid

# Filesystem
mount, umount
mkfs.vfat, mkfs.ext4
dump, restore
dumpe2fs
resize2fs
e2fsck

Insert sdcard to usb slot

Use sudo disk -l or sudo lsblk to checkout disk name, for example /dev/sda.

/dev/sda1 is the boot partition, which is fat32. /dev/sda2 is the root partition, which is ext4.

Prepare directories

1
2
3
4
5
6
mkdir backupimg/
mkdir backupimg/src_boot
mkdir backupimg/src_root
mkdir backupimg/dst_boot
mkdir backupimg/dst_root
cd backupimg/

Mount source disk

1
2
sudo mount -t vfat -o uid=pi,gid=pi /dev/sda1 ./src_boot    # Mount boot partition
sudo mount -t ext4 /dev/sda2 ./src_boot                     # Mount root partition

Then use sudo df -h to check it.

pi.img: Create empty file

Use df -h to checkout size of /dev/sda1 and /dev/sda2, caculate FILESIZE=/dev/sda1.Size+/dev/sda2.Used. It’s a good idea to add more size to FILESIZE, e.g. 1G.

Then create an empty file(example with FILESIZE=5G):

1
2
# bs*count = FILESIZE = 5G
sudo dd bs=1M count=5120 if=/dev/zero | pv -s 5G | sudo dd bs=1M of=./pi.img

pi.img: Make partitions

Use sudo fdisk -l /dev/sda1 to checkout start and end sector of /dev/sda1 and /dev/sda2.

1
2
3
sudo parted pi.img --script mklabel msdos
sudo parted pi.img --script mkpart primary fat32 8192s 122479s  # 8192s/122479s is start/end sector of `/dev/sda1`
sudo parted pi.img --script mkpart primary ext4  122880s -1     # 122880s is start sector of `/dev/sda2`, -1 is the last sector of device

After parted, use sudo parted pi.img --script print free to double check.

pi.img: Create loop device

1
2
3
4
sudo losetup -f --show pi.img                   # Create loop device with pi.img
sudo kpartx -va /dev/loop0                      # Create device map with partition tables of /dev/loop0
sudo mkfs.vfat -n boot /dev/mapper/loop0p1      # Format boot partition
sudo mkfs.ext4 /dev/mapper/loop0p2              # Format root pratition

Check /dev/mapper/loop0p1 and /dev/mapper/loop0p2, or use sudo lsblk.

pi.img: Mount filesystem

1
2
sudo mount -t vfat -o uid=pi,gid=pi /dev/mapper/loop0p1 ./dst_boot/    # Mount boot partition
sudo mount -t ext4 /dev/mapper/loop0p2 ./dst_root/                     # Mount root partition

Clone

1
2
3
4
5
6
7
sudo cp -rfvp ./src_boot/* ./dst_boot/                  # Copy boot files

sudo chown -R pi:pi dst_root
sudo rm -rf dst_root/*

cd dst_root/
sudo dump -0auf - ../src_root/ | sudo restore -rf -     # Dump filesystem from `src_root/`, and restore to `dst_root/`

On success DUMP IS DONE will be printed out. If there is Broken pipe error, use df -h to check if Avail of /dev/mapper/loo0p2 greater than Used of /dev/sda2.

Modify boot/fstab

Use sudo blkid to check PARTUUID of boot partition and root partition, print info as below:

1
2
/dev/mapper/loop0p1: SRC_TYPE="msdos"   LABEL="boot"    UUID="755C-729C"    TYPE="vfat" PARTUUID=="af2f8761-01"
/dev/mapper/loop0p2: UUID="xxx"    TYPE="ext4" PARTUUID=="af2f8761-02"

Modify ./dst_boot/cmdline.txt as below:

1
2
## Set root=PARTUUID=af2f8761-02
dwc_otg.lpm_enable=0 console=serial0,115200 console=tty1 root=PARTUUID=af2f8761-02 rootfstype=ext4 elevator=deadline fsck.repair=yes rootwait

Modify ./dst_root/etc/fstab, as below: 

1
2
3
4
5
## Mount boot partition to '/boot'
## Mount root partition to '/'
proc                  /proc           proc    defaults          0       0
PARTUUID=af2f8761-01  /boot           vfat    defaults          0       2
PARTUUID=af2f8761-02  /               ext4    defaults,noatime  0       1

Cleanup

1
2
3
4
5
sudo umount /dev/mapper/loop0p1 /dev/mapper/loop0p2 /dev/sda1 /dev/sda2
sudo kpartx -d /dev/loop0
sudo losetup -d /dev/loop0

sudo rm -rf src_boot src_root dst_boot dst_root

Message queue

不同的消息队列中间件对比

消息语义

通行概念解释

  • Consumer Group

通常指一个消费者的多个消费者实例，同一个Consumer Group的多个实例消费同一个队列，不同Consumer Group并行消费(订阅)同一个队列不互相影响。不同的消息队列对Consumer Group的定义方式有差别，但是语义上基本一致。

nsq

  • 订阅模型

nsq-topic

消费者订阅一个topic需要指定channel，所有订阅同一个topic/channel的消费者实例，构成一个Consumer Group。不同的Consumer Group需要订阅不同的channel。

  • 推拉模型

nsq采取消息推的模型，并且，消费者实例通过通告RDY告知nsq server同时可消费的消息最大值来控制消息推送速度。

  • 确认模型

消费者对每一个消息单独确认，或者REQUEUE。

  • 并发模型

一个channel对Consumer Group的多个消费者实例，消息并行通知。

  • 有序性

不保证有序性，因为一个channel对多个消费者实例会并行通知，并且消息单独确认(or REQUEUE)设计，nsq不保证消息的有序性。

kafka

  • 订阅模型

kafka-topic

每一个消费者需要指定Consumer Group ID，ID相同的消费者实例构成一个Consumer Group。Consumer Group可以对一个topic进行订阅，kafka内部会维护不同的Consumer Group的消费状态(offset)，互相不影响。

  • 推拉模型

kafka采取消费者拉取模型，由消费者决定一次拉取多少个

  • 确认机制

offset的批量确认机制，消费者自行调整offset对已经消费的消息进行确认

  • 并发模型

kafka通过partion支持topic的多消费者并发。topic进行多个partion，同一个partion只能同时由一个消费者实例进行消费，多个partion由多个消费者实例并行消费。partion和消费者是N:1的关系，一个partion最多有一个消费者，一个消费者同时可以处理多个partion。

  • 有序性

kafka保证topic的每一个partition是顺序的，但是多个partion之间的消息不保证有序。

pulsar

pulsar在Producer和Consumer端支持不同的模式，并且Producer和Consumer的模式互相是独立的，通过组合这些模式可以达到非常丰富的消息模型(例如可以组合出nsq/kafka相关的模型)。先说明一下这些模式

  • Subscription mode(Consumer)

pulsar-topic

Exclusive: 一个topic对于一个Consumer Group同时只能有一个消费者实例进行消费，如果有多个消费者实例，多余的消费者实例订阅的时候会失败。

Failover: 相比于Exclusive模式，可以有多个消费者实例同时订阅一个topic。但是Pulsar会选择其中一个消费者实例做为master(这个粒度可以是topic，也可以是每个topic的partition，取决于topic本身是non-partitioned还是partitioned，这个后面Producer模式会涉及)。如果Master断开了，Pulsar会选择下一个消费者实例做为Master。

Shared: 这个是最好理解的方式，一个Consumer Group的多个消费者实例共同消费一个topic，消息分发在Consumer Group多个实例间round robin模式负载均衡。这个模式跟nsq的订阅模型一样。

Key_Shared: 跟Shared模式类似，只是消息会根据消息的Key进行消费者选择，同一个Key的消息只会由一个消费者实例进行消费。

  • Partioned topics/Routing mode(Producer)

pulsar-partition

跟kafka一样，一个topic会进行多个partition，每一个partition的消息在队列里面也是有序的。partition会分配给一个broker，这样做的目的主要考量是topic在多个broker之间做系统负载均衡。一个topic的消息发布的时候，会分发到不同的partition，这个分发策略叫Routing mode，有以下几种

RoundRobinPartition: 消息通过Round robin的方式轮询发布到多个partition。如果消息有指定Key，消息会根据Key的hash规则找到指定的partition发布。

SinglePartition: 随机找到一个partition，把所有消息都发布到这个partition。如果消息有指定Key，消息会根据Key的hash规则找到指定的partition发布。

CustomPartition: 可以自定义每一个消息的发布routing规则，具体客户sdk有相应的接口。

接下来我们说明一下几个消息语义

  • 推拉模型

跟kafka一样采取客户端拉去模型，并且也可以批量拉取

  • 确认机制

支持单个消息确认(individual ack)，也支持类似kafka的累积确认(cumulative ack)。但是，cumulative只能在Subscription mode位Exclusive和Failover使用，因为这2种模式能保证同一个partition的消息在同一个消费者实例消费。

  • 并发模型

消费者端通过Subscription mode位Shared和Key_Shared都能做到多个消费者实例并行消费，这个方式类似nsq的模式。另外一种做法是，通过topic多partition，结合Subscription mode为Failover(因为Failover的选master粒度是每一个partition)，可以实现跟kafka同样的语义。

  • 有序性

跟kafka一样，topic的同一个partition是有序的

分布式集群

nsq

nsq本身不提供完整的集群方案，每一个nsq是一个独立的状态数据。由Producer自己决定把topic发布到哪个nsq实例，Consumer通过订阅多个nsq实例进行消费。nsq提供了nsq_lookupd来支持topic的路由，来简化应用的集群构建。消费者可以通过nsq_lookupd找到nsq集群地址，以及topic的路由信息，而不需要单独去找每一个nsq地址。

nsq-cluster-architecture

kafka

kafka-cluster-architecture

pulsar

pulsar-cluster-architecture

Gopher 2018 shanghai memo

记录一下参加gopher 2018的东西

Go在Grab地理服务中的实践

  • geohash
    基于坐标的hash，快速查找附近的司机

  • goreplay
    流量抓取

  • go-torch
    火焰图

Error handling in Go 2

  • github.com/mpvl/errc
  • github.com/mpvl/errd
  • try & handle
  • refer: Go: the Good, the Bad and the Ugly

Why we design a fast key-value database

  • motivation
  • levelDB, RocksDB
  • LSM Trees/B+ Trees
  • Separate keys from values.
  • Key stored in LSM Tree
  • Value stored in value log.
  • CGO evil

IPFS

  • DHT

Composition in Go

Bazel build //:go

  • Bazel
  • vgo

CGO

  • Soooooooooooo complex

arm64的go工具链

  • go tool
  • go assembler,/………………
  • go build -x test.go

Go interface internal

运行期的多态，是很多高级语言的很重要的特性。我们可以在运行期根据实际创建的对象，决定实际所要运行的函数。
C++可以通过virtual member function实现运行期的多态，同样，在Go我们可以通过interface实现类似的机制。虽然C++的virtual和Go的interface本质上还是有很多区别，但是不妨碍我们深入探讨一下关于如何实现运行期多态。

Note:

  1. 不去理解实现机制，并不影响我们使用C++或者Go（只要遵循语言的标准并不会有什么麻烦）。当然，如果能更深入的理解实现，本身有利于加深我们对代码的理解。
  2. 我们讨论的的实现很可能只代表主流编译器的实现，并不一定代表语言的标准。编译器需要遵循语言规范去实现，但是如何实现往往是编译器自己的决定。

C++多态

我们都知道C++的多态，通过基类里面把成员函数定义为virtual，继承类可以重新实现这个函数。使用一个基类的指针指向对象，并且通过该指针执行那个函数，具体执行的是基类还是继承类的函数，取决于运行期该对象的类型。C++的多态/继承当然没有那么简单，还有非常多的细节特性，想要完全说明白几乎不可能（建议去翻C++标准或者经典类的书）。我们这里只需要用最简单的例子，去说明实现的原理。

例如下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Base {
public:
    virtual void func() { std::cout << "Hello Base" << std::endl; }
}

class D : public Base {
public:
    virtual void func() { std::cout << "Hello D" << std::endl; }
}

/// main.cpp
Base *p = new D();
p->func(); ```

由于指针p指向的对象，实际上是类型D。而且`func()`定义为`virtual`，所以实际执行的是D的`func()`，程序输出：

Hello D

1
2
3
4
5
6
7

## C++ vtable

C++通过vtable实现多态，C++在***编译期***给每个类生成一个vtable。vtable就是一个函数地址数组，记录了这个类所有的virtual function指向的函数地址。只要该类声明了function为virtual，或者它的父类/祖先类声明了virtual，则该function就是virtual。

例如，`class D`的vtable只包涵一个元素，就是`func`的地址。

class D : vtable –> ———–
| D::func |
———–
| null |(null for array end)
———–

1
2
3

这里需要注意，`class D`的`func`没有指向`Base::func`，而是指向了`D::func`，是由于`class D`重新实现了`virtual func`。如果`class D`没有实现`virtual func`，那么`class D`的`func`会指向`Base::func`。

class D : vtable –> ————–
| Base::func |
————–
| null |(null for array end)
————–

1
2
3

那么，vtable是怎么使用的呢。在我们创建对象的时候，编译器会在创建对象的内存的开始插入vtable的地址指针vptr(很tricky)。例如，我们`new D()`

                                       vtable

p = new D() —–> ———— ———–
| vptr | ——–>| D::func |
———— ———–
| | | null |
| D object | ———–
| |
————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

> 所以即使是一个空的class，如果有virtual function，那么该class的sizeof也不会是0，而是一个指针的大小(sizeof(void *))。

当我们通过该对象调用`func`的时候，因为该function为virtual，会通过`vptr`找到`vtable`，并且在`vtable`里面找到`func`的地址，并且执行。

C++通过vtable实现了运行期的多态，但是vtable是在编译器静态绑定，运行期需要进行vtable的查找。


## Go interface
Go的interface是Go语言一个很重要的设计，借鉴了Java和C++的部分语言特性，最大的改变是去掉了C++和Java里面的显示继承。interface只是单纯的定义分行为（方法），如果我们要定义一种类型属于该interface，并不需要显示的继承该interface，只需要对该类型实现所有interface所声明的方法，那么这个类型就是属于该interface。

这里涉及的设计哲学是`What I do makes who I am`，不同于C++/Java的`I declare who I am`。这是一种充分`解耦`的设计哲学，打破 了类型之间的强耦合。其实跟现实世界很像，你是什么样的人，不取决于你自己怎么说或者你身上的既定的标签，而取决于你自己的行为。例如，你成天跟大家说你是君子不代表你就是一个君子，你的君子行径才能决定。嗯，有点跑题了，我们还是回到正轨。

例如下面的代码：

type Base interface {
func()
}

type D struct {}

func (d *D) func() {
fmt.Println(“Hello D”)
}

/// main.go
var p Base = new(D)
p.func()

1
2
3

由于p指向的对象，实际上是类型D，所以最后执行的是D的`func()`，程序输出：

Hello D

1
2
3
4
5
6


## Go itable

Go的interface结构包含2部分，第一部分是指向实际对象的value，第二部分是一个地址数组`itable`（有点像C++的vtable）。例如`interface Base`的结构如下

Base –> ————-
| value |
————- ———
| itable | —–> | func |
————- ———
| null |
———

1
2
3
4


当我们执行`var p Base = new(D)`时，会把左值拷贝给value，并且通过查找`D`的函数列表组装`itable`。

Base –> ————- ——————-
| value |————————————-> | address of D() |
————- ——— ——————-
| itable | —–> | func |—————
————- ——— | ————-
| null | |———-> | D::func() |
——— ————-


所以，当我们执行`p->func()`时，编译器已经知道具体执行的是`D::func()`


## 总结

C++和Go interface内部实现机制并不一样，但是都可以实现运行期的多态绑定。就是说，我们可以根据运行期实际创建的对象是什么，来决定运行的函数。

C++通过编译器静态产生vtable的方式实现，但是需要在运行期进行vtable查找，会带来运行期开销。

Go interface在运行期计算itable，好处是在执行的时候基本上是O(1)开销。

IPv4 private address

私有地址

Internet Assigned Number Authority(IANA)定义了一系列保留的私有地址，用来在路由器内部或者NAT内部进行组网。私有地址指允许在内网进行路由，如果这些地址跑到公网，所有的公网路由不会对这些地址进行路由。

地址段

  • A类地址

10.0.0.0/8: 10.0.0.0 - 10.255.255.255

  • B类地址

172.16.0.0/12: 172.16.0.0 - 172.31.255.255

  • C类

192.168.0.0/16: 192.168.0.0- 192.168.255.255

DHT

1. 背景

BT作为历史上最成功的P2P文件系统，已经在全球实现了彻底的去中心化。BT的P2P网络，不依赖任何机构或者中心依然能够很好的运行。
这里面，最关键的设计是引入了DHT。这里我们主要介绍一下为什么要引入DHT，以及DHT的基本原理。

BT作为一种P2P系统，面临资源索引问题，简单来说资源索引维护资源(resource)当前有哪些节点(peer)也在同时下载的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
res0 -> peerA,peerB,...
res1 -> peerC,peerD,...

                         ------------------------------
              Index ---> | res0 | res1 | ...          |
                         ------------------------------
                            |      |
                           \|/    \|/
                         ------- -------
                         |peerA| |peerC|
                         ------- -------
                         |peerB| |peerD|
                         ------- -------

2. 中心化

BT的数据传输本身是去中心化的，每一个peer会同时从网络上搜索到的其它peer进行数据传输。
但是资源索引一开始还是中心化的解决方案，就是Tracker。虽然网络上有很多提供Tracker的服务，每一个客户端也可以设置若干个Tracker，但是Tracker依然是一个中心化的服务。

Tracker原理很简单，提供了上报和查询服务。如下图：正在下载某一个资源(res)的BT客户端peer2把资源上报给Tracker。下载资源的BT客户端(peer1)可以到Tracker查询时下载这个资源的peer2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

           --------------    -----------------------------------
      |--->| Tracker    | -- |           Index                 |
      |    --------------    -----------------------------------
      |     |         /|\   
      |     |          |
      |     |          |
query |     |resp      |
      |     |(peer2)   |
      |     |          |    report res
      |     |          |----------------
      |    \|/                         |
   -----------                     ---------
   |  peer1  |                     | peer2 |
   -----------                     ---------

Tracker提供了一种简单高效的方案，解决了资源索引的问题。缺点是一旦Tracker不可用，BT的P2P网络也就随之瘫痪(可以参考海盗湾事件)。这是所有中心化服务必将面临的问题，为了让整个P2P网络更加健壮，需要探索一个去中心化的实现。

3. 去中心化

考虑没有中心化的Tracker，我们需要一个去中心化的方式，把资源的索引存储(sharding)到全网的节点，并且能高效的查询。

3.1 全量

最简单的办法，就是让每一个Node(节点)都维护一个全量的索引，相当于每个Node都是一个Tracker节点。

注意：我们需要区分一下Node和Peer的概念，以下是DHT的papper的描述
A “peer” is a client/server listening on a TCP port that implements the BitTorrent protocol. A “node” is a client/server listening on a UDP port implementing the distributed hash table protocol. 

1
2
3
4
5
6
7
8
9
10
11
12
13
--------------    -----------------------------------
| Node0      | -- |           Index                 |
--------------    -----------------------------------

--------------    -----------------------------------
| Node1      | -- |           Index                 |
--------------    -----------------------------------
    
    ...

--------------    -----------------------------------
| NodeN      | -- |           Index                 |
--------------    -----------------------------------

这种方案有几个明显的问题

  1. 每个索引的变更需要扩散到全网，效率太差
  2. 海量的索引，每个单点都需要全量存储，代价太大

3.2 Sharding

基本的思路是，我们需要把索引数据按照一定规则分布(sharding)到全网的节点。

1
2
3
4
5
6
7
8
9
10
    -----------       -----------     -----------                   -----------
    |  Node0  |       |  Node1  |     |  Node2  |       ...         |  NodeN  |
    -----------       -----------     -----------                   -----------
       /|\                 /|\            /|\                            /|\
        |--------           |              |                              |
                 |          |              |                              |
            -----------------------------------------------------------------------
Index ----> |  shard0    |  shard1    |   shard2     |  ...      |    shardN      |
            -----------------------------------------------------------------------

一致性Hash是一种常用的办法，首先把Node散列(hash)到一个整数的空间，这样每一个Node负责一个范围段的索引。
同样，我们可以把资源也计算一个整数的hash。
例如，NodeA负责范围[i, j)的范围，那么如果索引按照分布规则在范围内，那么该索引就由NodeA负责存储。

1
2
3
4
5
// NodeA covers [i, j).
// Use hash(resource) to caculate resource.
if i < hash(resource) < j {
    store(resource, NodeA) 
}

这里盗用一个网上的一致性Hash图片，具体的算法这里就不重复介绍了。

一致性Hash解决了sharding的问题，但是一致性Hash引入了Hash环状态。在系统中如何维护Hash状态数据，跟如何维护资源索引面临一样的问题。

我们需要彻底解决状态数据的问题，才能真正实现去中心化。

4. DHT

DHT(Distributed Hash Table)，就是分布式Hash table。实际上也是Sharding的一种实现方法，DHT可以看作是一致性Hash的基础上的改进。一致性Hash算法的问题是Hash环的状态数据，只要我们能设计出一种关于索引分布规则的去中心化的共识机制，我们并不需要去维护一个Hash环。关于DHT的比较完整的介绍，可以参考DHT Protocol。

DHT设计了这样一种去中心化的共识机制：索引信息应该存储到到距离目标更近的节点。

4.1 Hash

DHT网络中每个节点的NodeID就是一个hash值，每个资源也有一个hash。

4.2 距离

用来计算2个hash的距离，Node和Node之间可以有距离，Node和资源之间也可以有距离。要注意的是，这个距离并不是实际意义上的距离，只是一个算法上的需要。

4.3 Routing table

DHT网络中每个Node都维护一个Routing table（路由表），这是DHT的核心部分，它保存本节点和网络中一小部分节点信息。每一个节点，都能够提供查询接口，并且能够返回距离目标hash更近的节点。这样通过网络中递归查询Routihng table，可以不断的趋向更近。IPFS把这个过程总结为Peer Routing的过程。我们可以用Peer routing解决DHT的共识机制。

1
2
3
4
                   ---------------------------------------------
Routing table -->  | NodeInfo0 | NodeInfo1 | ...   | NodeInfoN |
                   ---------------------------------------------

我们以查询资源为例，一个典型的Query Resource过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1 ) client需要查找目标资源hash，先到Node0进行查询。
2 ) 如果Node0本地有这个hash的索引，则返回结果
3 ) 如果Node0本地没有这个hash的索引，Node0从自己的Routing table查找离目标hash更近的节点，例如Node1和Node2
4 ) client对Node1和Node2重复过程1的查询，直到有查询到有结果

           1) query hash       -----------
client  -------------------->  |         |
        <-------------------   |  Node0  |
           2 ) Resource        |         |
           3 ) Node1,Node2     -----------

           4 ) query hash      -----------
        -------------------->  |  Node1  |
                               -----------

           4 ) query hash      -----------
        -------------------->  |  Node2  |
                               -----------

5. Kademlia

DHT有很多不同的实现，这里主要介绍Kademlia，一般我们叫KAD。现在大部分的DHT都是基于KAD实现，或者KAD的一些改进。
KAD使用k-bucket(k桶)实现Routing table，能实现log2(N)的查找效率。假设1000000节点的规模的网络，可以最多20次查询能够完成全网节点的查询。

关于KAD的实现有很多细节，我们这里着重介绍为什么k-bucket能实现log2(N)的查找效率。

5.1 距离

KAD使用XOR(按位异或)对两个hash进行距离计算，为什么要使用异或？我们后面结合k桶可以看到，这是经过精心设计的算法。

1
distance(A, B) = A xor B

5.2 Routing table

KAD使用K桶(K-bucket)实现Routing table，K桶实际上是一个hash table。Hash table的大小取决于我们使用hash的位数，因为KAD使用sha1做hash算法，sha1的hash结果为160位，所以KAD的K桶大小为160。

那么K是什么意思呢，KAD限制了每个桶最多能存储K个节点信息，所以叫K桶。默认的KAD实现K一般为8。

实际的实现是K桶大小初始化为1，随着每个桶的节点数量超过K，K桶会进行对半分裂。由于不是关键点，我们这里就不详细介绍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
               -----------------------------------------------------------------------
K-bucket --->  |  0  |  1  |  2  |                  ...                 | 158  | 159 |
               -----------------------------------------------------------------------
                  |
                 \|/
               ------------
            -- | NodeInfo |
            |  ------------
            |  | NodeInfo |
         K <   ------------
            |  |   ...    |
            |  ------------
            -- | NodeInfo |
               ------------

5.3 K桶算法

那么，一个NodeInfo应该放到哪个桶呢。KAD的算法是，越小(具体实现也可能是越大，算法本质都一样)的桶存储的NodeInfo距离本节点的ID越远，并且每递增一个桶，距离折半。可以用按bit前缀匹配来实现，简单来说，第N个桶存储的节点NodeID与当前节点的NodeID前N-1位相同，第N位不同。

上面的描述还是有点晦涩，大家可以简单推算一下(XOR计算距离)，第0个桶上面的NodeInfo的ID所有的bit跟本节点ID都不一样（距离2^N，最远），最后一个桶的NodeInfo的ID只有最后一个bit跟本节点ID不一样（距离2^0=1）。

按照这个算法，有几个比较明显的结论是：

  1. 越大的桶存储的是离本节点越近的节点信息(XOR计算距离)
  2. 第N+1个桶存储的节点，比第N个桶存储的节点，距离本节点近了一半。也就是每递增一个桶，节点数量折半。
  3. 桶内所有的节点之间的距离，都一定比桶内节点跟本节点的距离，至少更近一半。(桶内节点跟本节点第N位不同，那么这些节点之间的第N位一定相同，也就是这些节点之间的前N位都相同)

我门用一个K桶大小为4的例子说明:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 假如节点0000保存了全部节点信息，实际上网络很大的时候一个节点的K桶只会保存一部分节点信息
// 下面为节点0000上的K桶

          -------------------------
          |  0  |  1  |  2  |  3  |
          -------------------------
           1000  0100  0010  0001
           1001  0101  0011
           1010  0110  
           1011  0111
           1100
           1101
           1110
           1111

可以看到：

  1. 第1个桶节点和本节点距离，比第0个桶节点和本节点的距离，更近。(例如 (0100 xor 0000 = 0100) < (1000 xor 0000 = 1000) )
  2. 第1个桶的节点数量，是第0个桶节点数量的一半。也就是越大的桶，节点数量是折半。
  3. 第0个桶，内部的节点距离，会比本节点距离至少更近一半。(例如 1000 xor 1001 = 0001, 1000 xor 0000 = 1000)

5.4 折半效率

所以，为什么KAD能够实现log2(N)的折半查找效率呢。

假如我们要查找/存储的目标为资源target，第一轮查询我们到节点Node0进行查询，Node0进行的操作为：

  1. 如果Node0拥有target资源，则返回
  2. 否则，计算target和Node0的距离所对应的K桶，例如为N
  3. 返回第N个桶的K个新节点信息

考虑第3)步，返回给客户端的这K个新节点，我们很容易得出一个结论：target和新节点的距离，至少比和Node0的距离近一半。

由于target和Node0计算距离定位到第N个桶，也就是target和Node0也是前缀关系，前N-1位相同，第N位不同。
再由于，”桶内所有的节点之间的距离，都一定比桶内节点跟本节点的距离，至少更近一半“。

客户端拿到离目标更近一半的新节点，继续进行下一轮查询，每递归一轮查找都能折半趋近。

6 结论

虽然我们这里忽略了很多DHT和KAD的实现细节，但是可以看到KAD通过K桶的Peer routing，能够实现折半效率的Peer routing。从而，我们可以通过Peer routing查找/存储到距离目标最近的节点，实现一个共识机制。

DHT作为去中心化的实现，相对中心化的Tracker，牺牲的是效率(慢扩散查找)和一致性(最终一致)，换来的是网络的健壮性。

Openssl tools

1. 生成rsa密钥文件

1
openssl genrsa -out private/cakey.pem

2. 查看密钥文件

1
2
openssl rsa -noout -text -in private/cakey.pem

3. 生成CSR

1
openssl req -new -key server_key.pem -out server_csr.pem
依赖：密钥文件server_key.pem

4. 查看CSR信息

1
2
openssl req -noout -text -in server_csr.pem

5. 生成证书

1
openssl req -new -x509 -key private/cakey.pem -out cacert.pem

依赖：密钥文件cakey.pem

6. 对CSR签名，生成证书

1
openssl ca -in server_csr.pem -out server_crt.pem

6. 查看证书

1
openssl x509 -noout -text -in server_crt.pem

ssl/tls

最近在折腾Microservice的gRPC鉴权问题，顺带梳理了下ssl/tls的原理。
以前没有特别深究过里面的问题，最近大概都算理清楚了，这里Mark也下。

1. ssl/tls

ssl/tls是一套基于非对称加密的安全协议，实际上ssl和tls是两个版本，大多数情况下这两个名词一起被提到，可以理解为tls是ssl的升级版本。

2. https

其实https是泛指http over secure，是在http协议之上增加的安全协议。当然，也有人会把它理解为http over ssl或者http over tls。
一般我们提到https都会默认提到ssl/tls，是因为ssl/tls在当前是最成熟的应用到https上。

3. ssl/tls握手

实际上https在安全机制上是做了两个事情，我们常常也会忽略。

  • 加密传输
  • 证书校验

握手的过程大概如下

  • Client端发送ClientHello给Server端。包含协议版本、一个随机数(Random1)、支持的加密算法、压缩算法等。

  • Server端发送ServerHello给Client端。包含协议版本的确认、一个随机数(Random2)、确认的加密算法、压缩算法等。

  • Server端发送Certificate(证书)给Client端。

  • Server端发送ServerHelloDone给Client端。

  • Client端发送ClientKeyExchange给Server端。包含一个随机数PreMasterSecret，并且PreMasterSecret要用证书里面的公钥进行加密。

  • Server端用自己的私钥把PreMasterSecret解开。Client和Server都用Random1、Random2、PreMasterSecret算出来MasterSecret，这个MasterSecret就是双方约定的加密传输的对称秘钥，并且使用之前协商的加密算法，进行后续的数据交互。

    注意：

    1. Server端所持有的私钥和公钥（在Certificate里面），并没有参与Certificate校验的过程，只是用来做最后一个随机数PreMasterSecret的加密保障。
    2. 这个过程并没有描述Certificate在Client端是怎么验证的，也就是Client根据什么确认Server的签名信息。

4. ssl/tls加密传输

加密传输是https的最重要特性，保证了所有网络上的数据不会被明文探测。整个握手过程实际上是明文的，生成MasterSecret的前面两个随机数也是明文。实际最终保证安全性的关键在于，PreMasterSecret这个随机数的安全性。而这个随机数的安全性是建立在非对称加密的安全性上面。

5. ssl/tls证书校验

5.1 基本原理

证书签名的基本原理很简单，一般是利用非对称加密算法。非对秘钥一般成对出现（最常用的RSA），一个公钥，一个私钥。
公钥加密的信息，只有私钥能解开。同理，私钥加密的信息，只有公钥能解开。
例如：我用私钥加密一段内容，同时告诉对方我的公钥，对方如果可以用我的公钥解开我的内容，就可以证明这段信息是我的。这里面，被加密的内容就可以作为签名信息。

5.2 关于CA/证书校验

ssl/tls的握手过程，往往容易忽略证书校验的过程，这个发生在握手的第3步，Server端发送证书给客户单之后，客户端是怎么验证证书的合法性呢？
握手的过程很简单，Server端的一组非对称秘钥，并没有参与到任何证书校验的环节，只是用来做了最后一个随机数PreMasterSecret的安全保障。

实际上我们Server的一对秘钥，并不是用来做证书校验，证书校验是通过另外一组非对称秘钥来保证。
这里就要提到***CA(Certificate Authority)***，CA是一个权威机构，主要负责证书的签名、发放、校验等职责。
主要逻辑参考这个图

certification_flow

  1. CA本身有自己的一套根密钥(cakey.pem)、根证书(cacert.pem一般包含了证书信息、对应的公钥信息等)
  2. Server生成自己的密钥(server_key.pem)和证书签名请求CSR(server_csr.pem)
  3. Server拿server_csr.pem到CA进行签名，得到server_crt.pem，即最终的证书。CA签名的过程，可以简单理解为用cakey.pem对server_csr.pem增加一段加密的签名信息。这段签名信息，只有CA的公钥（公钥信息在cacert.pem可以得到）可以解开。
    1
    F(cakey.pem, server_csr.pem) = server_crt.pem
  4. Client端（一般是浏览器）会内置了CA的根证书(cacert.pem)。在ssl/tls握手的第3步，Client拿到Server的Certificate（这个其实就是server_crt.pem），就可以根据CA的根证书对Certificate进行验证。

所以，最终证书的安全性建立在Client端的CA根证书的安全性。

Note: 怎么保证Client端CA证书的安全性？

5.3 为什么要给钱

正常的网站，为了做网站的证书签名，都需要找到权威的CA机构进行证书签名，而CA对这块都是要付费的。
那问题是，我们为什么非得找这些CA付费，自己随便搞一个假的CA进行对自己的证书进行签名不就行了吗。
其实也有人这样干，大家可以参考万恶的http://12306.cn。对，就是那个全世界最大的电商网站。
例如用Chrome访问都会提示证书不安全，因为他们并没有找权威CA进行证书签名。
https_error
CA的权威性，是建立在行业标准之上的存在，所以对浏览器厂商也会遵循这些行业标准。也就是，这些浏览器都会内置权威的CA的根证书。为了让浏览器能显示你是认证的网站 ，必须找权威的CA机构，给钱、签名。

6. Openssl自建CA、Server数字证书

恩，为什么要自建CA呢。
上面说了，ssl/tls实际上是做了两个事情，加密传输和证书验证。
这两个事情，其实不太相关。
证书验证，大部分场景是在网站浏览器端，所以网站必须给权威的CA机构付费。
但是，如非浏览器应用，我们只是想利用xls/tls加密传输。
我们就完全有理由自己搞私有的CA，自己给自己发证书了。

Openssl工具提供了一整套完整的命令行工具，大概流程如下
主要做几件事情

  1. 配置自己的CA
  2. 生成Server的密钥，CSR
  3. 用CSR到CA签名，生成CRT，也就是证书
CSR: Certificate Signing Request，证书签名请求
CRT: Certificate，证书

6.1 配置CA

如果安装了Openssl，默认的路径在/etc/pki/。
配置文件路径在tls/openssl.cnf，基本的配置可以不用改。
可以简单关注一下policy_match相关的配置，这里配置了对不同证书信息是否进行校验。

  • 进入CA目录

    1
    cd CA/

  • 创建两个文件

    1
    2
    touch index.txt serial
    echo 01 > serial

  • 创建根密钥

    1
    openssl genrsa -out private/cakey.pem 2048

  • 创建根证书
    需要用到密钥 

    1
    openssl req -new -x509 -key private/cakey.pem -out cacert.pem

6.2 配置Server

  • 生成Server密钥

    1
    openssl genrsa -out server_key.pem 2048

  • 生成Server CSR
    需要用到密钥

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    openssl req -new -key server_key.pem -out server_csr.pem
    ...
    Country Name (2 letter code) [AU]:CN
    State or Province Name (full name) [Some-State]:GD
    Locality Name (eg, city) []:SZ
    Organization Name (eg, company) [Internet Widgits Pty Ltd]:COMPANY
    Organizational Unit Name (eg, section) []:IT_SECTION
    Common Name (e.g. server FQDN or YOUR name) []:your.domain.com
    Email Address []:

    Please enter the following 'extra' attributes
    to be sent with your certificate request
    A challenge password []:
    An optional company name []:
    ...

6.3 证书签名

把上一步的server_csr.pem发给CA机器，在CA机器上执行

1
openssl ca -in server_csr.pem -out server_crt.pem

6.4 完成

Server端持有: 密钥server_key.pem、证书server_crt.pem
Client端持有: CA的根证书cacert.pem

双方即可进行ssl/tls握手通信

7. ssl/tls双向校验

因为在做gRPC鉴权的时候，我们需要的Server端对Client进行身份鉴权，于是发现ssl/tls是支持双向鉴权。
简单来说就是，除了Client端对Server端进行证书鉴权，Server端也会要求对Client进行证书鉴权。

握手过程如下，加粗的步骤是新增的。

  • Client端发送ClientHello给Server端。包含协议版本、一个随机数(Random1)、支持的加密算法、压缩算法等。
  • Server端发送ServerHello给Client端。包含协议版本的确认、一个随机数(Random2)、确认的加密算法、压缩算法等。
  • Server端发送Certificate(证书)给Client端。
  • Server端发送Certificate Request给Client端，要求Client端提供证书。
  • Server端发送ServerHelloDone给Client端。
  • Client端发送Certificate给Server端。
  • Client端发送ClientKeyExchange给Server端。包含随机数PreMasterSecret，并且PreMasterSecret要用证书的公钥进行加密。
  • Client和Server端用Random1、Random2、PreMasterSecret算出来MasterSecret，这个MasterSecret就是双方约定的加密传输的对称秘钥，并且使用之前协商的加密算法，进行后续的数据交互。

服务器拿到Client端的Certificate，进行类似Client端对Server端的Certificate校验过程，这样就实现了双向校验。

UDP package size

最近研究了一下udp相关的东西，做下笔记。
这里有相关的测试代码。

udp包一般多少适合

协议层的限制，理论上我们可以发送接收65535(0xFFFF)大小的udp包。为了避免IP层分片，udp包在ethernet上一般不超过1472(1500-20-8)，1500为ethernet的链路MTU。
实际上很多应用（例如DNS）的udp包都不超过512，为什么呢？

这是Stack Overflow上面的一句话
The maximum safe UDP payload is 508 bytes. This is a packet size of 576, minus the maximum 60-byte IP header and the 8-byte UDP header. Any UDP payload this size or smaller is guaranteed to be deliverable over IP (though not guaranteed to be delivered). Anything larger is allowed to be outright dropped by any router for any reason.
按照字面理解的意思是，大于576的udp包在路由链路保证不了一定传输，难道是路由器的实现潜规则？

  • 更新At 2016-11-14

RFC的IPV4标准里面有定义。

RFC 791 excerpt:
…
All hosts must be prepared to accept datagrams of up to 576 octets ( whether they arrive whole or in fragments ). It is recommended that hosts only send datagrams larger than 576 octets if they have assurance that the destination is prepared to accept the larger datagrams.
The number 576 is selected to allow a reasonable sized data block to be transmitted in addition to the required header information. For example, this size allows a data block of 512 octets plus 64 header octets to fit in a datagram. The maximal internet header is 60 octets, and a typical internet header is 20 octets, allowing a margin for headers of higher level protocols.
…

既然这样，另外一个问题来了，为什么TCP的MSS一般不受这个限制。
是因为TCP有做链路MTU探测，以及稳定的重传机制吗？

udp socket缓冲区

  1. 发送缓冲区

经常有一个误解是udp没有发送缓冲区，实际udp也有发送缓冲区。只不过udp并不是流协议，发送缓冲区只会缓存一个包，然后立刻就被拷贝到内核协议栈。
如果发送一个超过缓冲区大小的udp包，大多数的实现是直接丢弃。

  1. 接收缓冲区

接收缓冲区跟发送缓冲区有点不一样，所有的udp包会按照先后顺序缓存，应用层每次读会返回最早的包。实际上接收缓冲区就是FIFO队列。
如果接收缓冲区大小不够，大多数的实现是直接丢弃整个包。

FFmpeg

ffmpeg使用

发布rtmp流

1
ffmpeg -loglevel verbose -re -i test.flv -vcodec libx264  -vprofile baseline -acodec libmp3lame -ar 44100 -ac 1 -f flv 'rtmp://10.10.159.119:1935/app1/2'

ffmpeg安装

1
./configure --enable-libmp3lame --enable-libx264 --enable-libfdk-aac --enable-gpl --extra-cflags=-I/usr/local/include --extra-ldflags=-L/usr/local/lib --extra-libs=-ldl --enable-nonfree