# Distributed Storage, Key-Value Stores, Security (23)

## Distributed Storage

### Remote Procedure Call (RPC)

在分布式系统中，节点之间需要通过网络发送、接受消息来交流。信息在网络中传输有许多细节需要考虑，如：

* 数据包丢失
* 数据错误
* 网络超时
* 如何将消息打包、拆分、组装、解包
* ...

如果每个分布式系统都需要实现一套这样的通信逻辑，那对开发人员来说将非常痛苦且容易犯错。此时，更好的选择是使用 RPC，顾名思义，就是远程过程调用：客户端调用服务就像在服务端本地调用一个函数一样，如：

* client calls: remoteFileSystem -> Read("rutabaga")
* server calls: fileSys -> Read("rutabaga")

信息流动过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrRNxN17badbdekmFa0%2F-LrRQf0Shep4Avc01Akc%2FScreen%20Shot%202019-10-18%20at%209.14.53%20AM.jpg?alt=media\&token=9e1cb7b8-1c1f-48fc-bda8-c7667ddee140)

对比 RPC 与普通的函数调用，其中概念对应关系如下：

| Function Call     | Remote Procedure Call         |
| ----------------- | ----------------------------- |
| Parameters        | Request Message               |
| Result            | Reply Message                 |
| Name of Procedure | Passed in request message     |
| Return Address    | mbox2(client return mail box) |

通常，Client/Server stubs 会由 RPC 框架自动生成，用户只需要将服务的输入输出定义在 IDL (Interface Definition Language) 中即可。

#### RPC Details

1\. Client 如何知道 Server 的位置，并将消息发送过去？

需要将服务名称翻译成 host、port

2\. Dynamic Binding

服务的注册与发现，Client 无需关心服务的具体位置

#### Problems with RPC

1\. 可能出现 Partial Failures/Non-Atomic Failures

* 分布式环境下的故障形式比单机形式下的故障形式多得多
  * user-level bug causes address space to crash
  * machine failure, kernel bug causes all processes on same machine to fail
  * some machine is compromised by malicious party
  * before RPC: whole system would crash/die
  * after RPC: One machine crashes/compromised while others keep working
  * can easily result in inconsistent view of the world
    * Did my cached data get written back or not?
    * Did server do what I requested or not?
  * The Byzantine Generals' Problem

2\. Performance

网络开销 + 错误处理开销

### Microkernel Operating Systems

操作系统的架构的两个极端就是 Monolithic Structure 和 Microkernel Structure，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrRNxN17badbdekmFa0%2F-LrRXjVyqH2r2qCPiWT6%2FScreen%20Shot%202019-10-18%20at%209.45.50%20AM.jpg?alt=media\&token=1279bdbd-9604-4b5d-b9a7-6b3cdbb8745c)

其中 Monolithic Structure 将更多的内容囊括进入 kernel 中，如 file system, Windowing 等等，它们之间的对比罗列如下 ([来源](https://unix.stackexchange.com/questions/6409/how-does-linux-kernel-compare-to-microkernel-architectures))：

1. Monolithic kernel is much **older than microkernel**. It’s used in Unix while the idea of microkernel appeared at the end of the **1980's**.
2. Examples of OSes having the monolithic kernels are **UNIX, LINUX** while the OSes having microkernel are **QNX, L4, HURD** and initially **Mach** (not MacOS X) which was later converted into hybrid kernel. Even **MINIX** is not a pure microkernel because its device drivers are compiled as part of the kernel.
3. Monolithic kernels are **faster than microkernels**. The first Mach microkernel is 50% slower than monolithic kernels. Later versions like L4 are only **2% or 4% slower than the monolithic kernel**.
4. Monolithic kernels are generally **bulky** while pure microkernel has to be **small in size**, even fit into the processor's first level cache (first generation microkernel).
5. In monolithic kernels, device drivers reside in the **kernel space** while in the microkernel device drivers reside in the **user space**.
6. Since device drivers reside in the kernel space, it makes monolithic kernel **less secure** than microkernel (Failure in the driver may lead to crash). Microkernels are **more secure** than monolithic kernels, hence they're used in many military devices.
7. Monolithic kernels use **signals and sockets** to ensure IPC while microkernel approach uses **message queues**. The 1st gen of microkernel poorly implemented IPC so they were slow on context switches.
8. Adding new features to a monolithic system means **recompiling the whole kernel** while you can add new feature or patches **without recompiling**

本节在这里提到 Monolithic/Microkernel 的对比是想说，后者的设计更适合云原生的场景。比如需要构建一个分布式文件系统，如果在 Microkernel Structure 之上，File System 将变得可插拔，进程通过 RPC 调用 File System 接口，而 RPC 客户端调用本地 RPC 服务与远程 RPC 服务的方式是一样的，因此整个切换过渡的过程将变得如丝般顺滑。

### Network-Attached Storage and the CAP Theorem

假设我们想要提供一个最简单的分布式文件系统，共享网络中不同节点上的存储空间，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrRNxN17badbdekmFa0%2F-LrRZcfWoM7dCTIMNdrE%2FScreen%20Shot%202019-10-18%20at%209.54.07%20AM.jpg?alt=media\&token=81b62630-e99a-4ef2-aa98-29659a111254)

我们势必需要面对 Consistensy，Availability 以及 Partition Tolerance，CAP 原理说的就是三者无法兼得。其中 Partition Tolerance 是既定存在的环境因素，我们无法改变，因此任何分布式系统都需要在 Consistency 与 Availability 中做权衡。

## Distributed File Systems

如果用一个词总结操作系统，可以用虚拟化 (virtualization)，将所有硬件资源虚拟化后提供给不同的软件使用；但如果要总结分布式系统，还需要另一个词，即透明 (transparency)，让远程和本地的硬件用起来差不多，用户只需要将所有通过网络相连的硬件资源看作一个大型单体计算机即可。

类似地，分布式文件系统的主要功能可以概括为：

> Transparent access to files stored on a remote disk

在分布式文件系统内部，我们需要能够定位存储资源。本地文件系统可以让我们通过指定文件路径访问文件，分布式文件系统同样需要类似的支持，它的实现可以分为以下三种：

1. Hostname: localname，利用 hostname 指定目标机器，再用 localname 指定具体文件路径
2. Mounting：将远程硬盘挂在在本地文件系统的某路径下
3. Global Namespace：统一资源定位符，世界上的任意文件都有唯一的资源定位符

### Simple Distributed File System

想象下面这个场景：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrS6tGZ8UxyAZX1ekrS%2F-LrS9_ChZ7rR2qFHOuNj%2FScreen%20Shot%202019-10-18%20at%2012.39.51%20PM.jpg?alt=media\&token=80363790-b4f6-4b90-b20c-7f76b9739632)

有一块远程硬盘挂载在 Server 上，Client 的文件读写操作都通过 RPC 请求发送给 Server，Client 本地没有缓存。这种方案的优势在于，Server 为多个 Clients 提供一致的视图 (consistent view)。但问题也不少：

* 网络开销导致文件操作速度变慢
* 很多场景无法使用 pipeline 优化
* Server 将成为性能瓶颈

一种优化方案是通过缓存来减少网络开销，如使用本地 buffer cache，提高一些重复读的效率。但缓存带来的一致性问题它都有。除此之外，Client 和 Server 也可能出现崩溃，缓存中的内容如果未来得及写出，则崩溃可能导致数据丢失，因此这里还需要解决故障恢复的问题。

### Network File System (NFS)

NFS 主要由三层抽象构成：

* UNIX file-system interface：open, read, write, close
* VFS layer：将本地文件系统和远程文件系统抽象出统一接口
* NSF service layer：最底层，实现 NFS Protocol

如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrb-aymaZqqmmFFsZiT%2FScreen%20Shot%202019-10-20%20at%2010.32.26%20AM.jpg?alt=media\&token=8ca7e91f-0670-4082-b33f-0c7798d59135)

#### Protocol

其中 NFS Protocol 定义了一些远程操纵文件的 RPC 接口，包括：

* reading/searching a directory
* manipulating links and directories
* accessing file attributes/reading and writing files

在 NFS 中：

* 所有的写操作都必须持久化以后才能返回，即 write-through caching
* 所有的服务器都是无状态的，每个请求都必须提供请求所需的所有参数
* 所有的操作应该是幂等的，举例如下：
  * 当服务器在 disk I/O 结束前崩溃时，客户端通过超时重发后，服务器再重新执行一次
  * 读写文件块时崩溃，重新读写
  * 删除文件/文件夹时，一次成功操作后，剩余操作都执行失败，返回错误

#### Failure Model

NFS 的 Failure Model 可以简单概述为：

> Transparent to client system

在遇到 NFS 服务器崩溃的情况下，有两种处理方式：

1. 无限等待 (Hang) 直到服务器返回消息
2. 直接报错

#### Cache Consistency

NFS 提供的一致性保证很弱：clients 通过周期地轮询服务器来查看是否有变化。因此，当一个 client 修改某个文件时，其它 clients 通常还在使用旧版的文件，直到下一次轮询发生。

如果多个 clients 同时向一个文件写数据，怎么办？NFS 对这种操作没有任何保证，该文件的最终版本可能是其中任何一版，也可能是中间结果，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrafw-jx6Fe13BltZXo%2FScreen%20Shot%202019-10-20%20at%209.02.10%20AM.jpg?alt=media\&token=8a1cc9bf-b9e3-4044-8ebe-363f0a924290)

在单机系统上，我们预期的行为是：

* 如果读请求在写请求结束之前开始，则拿到旧版本的数据
* 如果读请求在写请求结束之后开始，则拿到新版本的数据

在 NFS 上，我们得到的行为是：

* 如果读请求在写请求结束之后 30 秒 (参数可调整) 后开始，则拿到旧版本数据
* 如果读请求在写请求结束之后 30 秒 (参数可调整) 内开始，则可能拿到旧版本或部分更新的数据

### Andrew File System (AFS)

AFS 的设计受到 NFS 的许多影响，但它与 NFS 的主要不同在于：

* 用 callbacks 取代轮询 (polling)：clients 不再轮询 server，而是引入的 callbacks 机制，server 记录所有打开某文件的 clients，当文件内容变化时，server 立即将其告诉所有打开该文件的 clients，节省了轮询的带宽
* 在文件关闭时才写出数据：在关闭文件之前文件的修改都在本地缓存，直到文件关闭才一起写出。因此在 AFS 中，不会出现部分写出的情况，要么全部写出，要么都没写出。此外，即使 server 通知每个 client 某文件已经被修改，若该文件没有重新被打开，则 clients 还是只会看到旧版的文件。
* 数据不止在内存中缓存一份，且在磁盘上也缓存了一份。利用文件在本地磁盘的语义，在文件未重新打开时看到的都是旧版文件。

与 NFS 相比，AFS 的优势在于：

* 利用本地磁盘作为缓存，可以缓存更多文件
* 利用 callbacks 减少带宽

AFS 与 NFS 共同的缺点，受限于中心服务器：

* 性能：所有写操作，读缓存未命中都将传递到 server
* 可用性：server 是单点故障
* 成本：server 的机器性能要求更高

### Virtual Filesystem (VFS)

VFS 是在本地文件系统和网络文件协议之上的一层抽象，它提供了虚拟 superblocks、inodes、files 等等概念，只要能够提供这些抽象概念，就能构建一个底层文件系统与之兼容。以文件复制为例：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrb0Fbinn2itEE5rKNg%2FScreen%20Shot%202019-10-20%20at%2010.35.13%20AM.jpg?alt=media\&token=326996c7-94f5-4a7f-b22f-4b42a87a2fb6)

## Key-Value Storage

键值数据库为开发者提供了最简单的数据持久化，它的接口通常非常简单：

```
put(key, value)
get(key)
```

它可以被直接使用，也可以作为其它复杂存储模型的基础，如关系型存储模型。当数据的体量很小时，我们用内存中的 map/dict/hash table 来存储即可；而当数据体量越来越大，到达 PB 级别时，就需要面临更多的问题和挑战。

典型的键值数据库使用场景举例如：

* Amazon:
  * Key: customerID
  * Value: customer profile
* Facebook, Twitter:
  * Key: userID
  * Value: user profile
* iCloud/iTunes:
  * Key: Movie/song name
  * Value: movie, song

已经商用的键值数据库包括但不局限于：

* AWS
  * DynamoDB
  * Simple Storage System (S3)
* BigTable/HBase/Hypertable
* Cassandra
* Memcached/Redis
* ...

究其本质，其实键值数据库就是分布式哈希表 (Distributed Hash Tables, DHT)。它的核心思想就是将键值数据合理地分片，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrb37b_PBMNxSGRsGd7%2FScreen%20Shot%202019-10-20%20at%2010.47.56%20AM.jpg?alt=media\&token=7050aa10-bdeb-4212-ad4c-cc292a93dc6a)

既然是分布式系统必然又要面对 fault tolerance, scalability, consistency, heterogeneity 等各种问题。

### Directory-Based Architecture

利用一个主节点来存储某个键所在的节点名称，如下图所示：

写数据：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrb5R5WA5giV_fHQkaI%2FScreen%20Shot%202019-10-20%20at%2010.58.00%20AM.jpg?alt=media\&token=83d9bd89-c570-4fef-9d32-8cb256142b90)

读数据的方式有两种，recursive 和 iterative，前者如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrb5ZFkeCZMU_eB-WnN%2FScreen%20Shot%202019-10-20%20at%2010.58.32%20AM.jpg?alt=media\&token=c9152a19-b014-4fa7-99fe-188414ff6af1)

后者如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrabDgEkP-D1bI6SxnG%2F-Lrb749VCT2IIjCUOY3p%2FScreen%20Shot%202019-10-20%20at%2011.05.10%20AM.jpg?alt=media\&token=c53566f4-0fe6-47c9-84b5-e7820c38f698)

对比 recursive 和 iterative：

Recursive Query：

* 优势：
  * 速度更快：通常主节点与其它节点之间的距离更紧，网络更通畅
  * 更容易保持数据一致性：主节点可以对读写操作进行排序
* 劣势：
  * 扩展性差，所有请求都需要经过主节点，主节点就成了瓶颈

Iterative Query：

* 优势：扩展性好
* 劣势：速度慢，更难保持数据一致性

#### Fault Tolerance

将数据复制到多个节点上：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LrbC4AV-OWmdk9UTTRa%2F-LrbCEvgIuGlA682b3MJ%2FScreen%20Shot%202019-10-20%20at%2011.27.46%20AM.jpg?alt=media\&token=06583645-3840-4a1b-aaf0-5aa8e452483d)

#### Scalability

可以从以下三个方面来考虑扩展性：

* 存储空间的扩展可以通过增加节点来实现
* 出现热点时，可以适当增加热点数据的复制数量
* 主节点的扩展性可以通过复制或者分片来解决

在增加节点扩展存储的过程中，键值数据库还需要考虑负载均衡问题，将新的键值更多地导向新节点，但又不能只向新节点中增加数据，而是尽量地将负载均衡分配；当存储节点出现崩溃时，则需要将崩溃节点的数据复制到其它节点上。(consistent hash)

#### Consistency

略讲：与关系型数据库中的一致性遇到的问题和解决方案类似：

* Linearizable Consistency
* Eventual Consistency
* Causal/Sequantial/Strong Consistency

总体上，为了提供更强的一致性保证，分布式键值数据库的 put 速度慢，get 速度快。

#### Quorum Consensus

略，见 [DDIA](https://zhenghe.gitbook.io/open-courses/ddia-bi-ji/consistency-and-consensus) 中的讨论。

## 参考

lecture node [23](https://inst.eecs.berkeley.edu/~cs162/sp15/static/lectures/23.pdf)