Motor: Enabling Multi-Versioning for Distributed Transactions on Disaggregated Memory

设计一个分布式系统必定会遇到一个问题—— **因为分区容忍性（partition tolerance）的存在，就必定要求我们需要在系统可用性（availability）和数据一致性（consistency）中做出权衡** 。这就是著名的 **CAP** 定理。它告诉我们，分布式系统中有三项关键属性，但你不可能同时满足所有三个：



- **一致性**（Consistency）：所有节点上的数据都是一致的，比如每个人看到的文档都是最新的。
- **可用性**（Availability）：系统能响应所有请求，即使有些节点出问题也能继续运行。
- **分区容忍性**（Partition Tolerance）：即使节点之间的网络通信出现了问题，系统还能继续工作。

CAP 定理的意思是，你必须在这三者之间做取舍。例如，分区容忍性对于分布式系统非常重要，因为网络问题在分布式环境中经常发生。如果你想要保证系统的分区容忍性和可用性，那一致性就可能受到影响，反之亦然。

举个例子，如果你在不同城市的朋友们一起玩在线游戏，游戏可能因为网络分区导致有的人操作延迟。但游戏公司通常会优先保证可用性（即游戏继续运行），而不总是优先考虑一致性（比如大家瞬间同步）。这就是 CAP 定理的应用。

## **1. 数据一致性问题与Paxos的背景**

在分布式系统中，多个节点需要协作完成一致的操作（例如更新数据库、选举主节点）。但由于网络延迟、节点故障等问题，如何让所有节点对某个值（例如一条操作指令）达成一致，是一个复杂的挑战，称为**共识问题**。
**Paxos协议**由Leslie Lamport于1990年提出，是首个被严格证明正确性的分布式共识算法，成为解决此类问题的经典方案。

---

## **2. Paxos的核心目标**

- **安全性（Safety）** ：所有节点最终达成相同的值，且该值必须由某个节点提出。
- **活性（Liveness）** ：只要多数节点存活且通信正常，算法最终能达成一致。
- **容错性**：允许系统中最多半数节点故障（包括崩溃、网络分区等）。

---

## **3. 核心概念与角色**

Paxos协议中有三类角色：

1. **Proposer（提议者）** ：提出提案（Proposal），包含唯一编号和提议的值。
2. **Acceptor（接受者）** ：投票决定是否接受某个提案。
3. **Learner（学习者）** ：学习已达成一致的提案值。

**关键概念**：

- **提案编号（Proposal Number）** ：全局唯一且递增的编号，用于区分提案优先级。
- **多数派（Quorum）** ：超过半数的Acceptor集合，用于确保决策的唯一性。

---

## **4. Basic Paxos算法流程**

Paxos通过两阶段协议（Prepare & Accept）确保一致性：

### **阶段一：Prepare（准备阶段）**

1. **Proposer发送Prepare请求**：

    - 生成一个全局唯一的提案编号 `n`，向所有Acceptor发送 `Prepare(n)`。
2. **Acceptor响应Promise**：

    - 若收到的 `n` 大于已回复过的所有Prepare请求的编号，则回复 `Promise(n, accepted_n, accepted_v)`，其中 `accepted_n` 和 `accepted_v` 是该Acceptor已接受的最高编号提案的值。
    - 否则拒绝请求。

### **阶段二：Accept（接受阶段）**

1. **Proposer发送Accept请求**：

    - 若收到**多数派Acceptor**的Promise回复：

      - 选择所有回复中最高编号对应的值 `v`（若存在），否则使用自己的提案值。
      - 向所有Acceptor发送 `Accept(n, v)`。
2. **Acceptor接受提案**：

    - 若收到的 `n` 大于等于已承诺的Prepare编号，则接受该提案，回复 `Accepted(n, v)`。
    - 否则拒绝。
3. **Learner学习结果**：

    - 一旦某提案被**多数派Acceptor接受**，Learner将值 `v` 作为最终结果。

---

## **5. 正确性保证的直观解释**

- **唯一性**：每个提案编号唯一，且Acceptor只接受更高编号的提案。
- **值传递性**：若某个值已被多数派接受，后续Proposer必须选择该值（通过阶段一中回复的 `accepted_v`）。
- **容错性**：只要多数派存活，算法能持续推进。

---

## **6. 活锁问题与优化**

- **问题**：多个Proposer同时提交递增的编号，导致无限循环的Prepare阶段。
- **解决方案**：

  - 引入**Leader选举**机制，指定唯一Proposer（Multi-Paxos的核心思想）。
  - 随机退避策略（降低冲突概率）。

---

## **7. Multi-Paxos：从单次共识到连续操作**

- **目标**：优化Basic Paxos的单次提案开销，支持连续多次共识（如日志复制）。
- **核心思想**：

  - 选举一个稳定的Leader作为唯一Proposer。
  - 对每个日志位置运行一次Basic Paxos（通过Prepare阶段的复用减少通信开销）。

---

## **8. 实际应用与变种**

- **经典系统**：Google的Chubby锁服务、Apache ZooKeeper（ZAB协议受Paxos启发）。
- **变种算法**：Raft（简化Paxos的逻辑）、Fast Paxos（优化延迟）。

---

## **9. Paxos的优缺点**

- **优点**：

  - 理论完备性：首个严格证明正确性的共识算法。
  - 高容错性：容忍半数节点故障。
- **缺点**：

  - 实现复杂：需处理大量细节（如日志持久化、Leader选举）。
  - 活锁风险：需额外机制优化。

---

## **10. 总结**

Paxos通过两阶段协议和多数派机制，在不可靠的分布式环境中实现一致性。尽管其理论抽象性导致实现难度较高，但其思想深刻影响了后续共识算法（如Raft），成为分布式系统领域的基石。

**学习建议**：结合具体实现（如ZooKeeper）理解Multi-Paxos的应用，并通过Raft算法对比掌握共识问题的核心逻辑。

分布式系统中的Paxos协议

## 一、二叉树遍历基础概念

二叉树的遍历是指按照某种顺序访问二叉树中的每个节点，且每个节点仅访问一次。常见的遍历方式包括**前序遍历**、**中序遍历**和**后序遍历**，其核心区别在于根节点、左子树和右子树的访问顺序。



| 遍历类型 | 访问顺序          | 适用场景                     |
|----------|-------------------|------------------------------|
| 前序遍历 | 根节点 → 左子树 → 右子树 | 树的创建、表达式求值前缀表示 |
| 中序遍历 | 左子树 → 根节点 → 右子树 | 表达式求值中缀表示、排序二叉树遍历 |
| 后序遍历 | 左子树 → 右子树 → 根节点 | 释放树资源、表达式求值后缀表示 |


## 二、递归实现
递归实现基于二叉树的递归定义，代码简洁直观，利用函数调用栈自动管理遍历顺序。以下以Python语言为例：
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前序遍历递归实现
def preorderTraversal_recursive(root):
    if not root:
        return []
    return [root.val] + preorderTraversal_recursive(root.left) + preorderTraversal_recursive(root.right)

# 中序遍历递归实现
def inorderTraversal_recursive(root):
    if not root:
        return []
    return inorderTraversal_recursive(root.left) + [root.val] + inorderTraversal_recursive(root.right)

# 后序遍历递归实现
def postorderTraversal_recursive(root):
    if not root:
        return []
    return postorderTraversal_recursive(root.left) + postorderTraversal_recursive(root.right) + [root.val]
```

## 三、非递归实现
非递归实现需手动维护一个栈（Stack）来模拟递归调用栈，更适合理解遍历的底层逻辑，同时可避免递归深度过大导致的栈溢出问题。

### 1. 前序遍历非递归
前序遍历非递归需先将根节点入栈，每次弹出节点并访问，再将其右子节点和左子节点依次入栈（确保左子树优先访问）。
```python
def preorderTraversal_iterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result
```

### 2. 中序遍历非递归
中序遍历需优先遍历到最左侧叶子节点，再依次回溯访问根节点和右子树。
```python
def inorderTraversal_iterative(root):
    if not root:
        return []
    stack, result = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result
```

### 3. 后序遍历非递归
后序遍历非递归实现较为复杂，可采用两个栈：第一个栈存储节点，第二个栈存储后序遍历结果，最终反转第二个栈得到顺序结果。
```python
def postorderTraversal_iterative(root):
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node.val)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    return stack2[::-1]
```


## 四、性能分析
| 遍历方式 | 时间复杂度 | 空间复杂度（递归） | 空间复杂度（非递归） |
|----------|------------|--------------------|----------------------|
| 前序遍历 | O(n)       | O(h)（h为树高）   | O(n)                 |
| 中序遍历 | O(n)       | O(h)               | O(n)                 |
| 后序遍历 | O(n)       | O(h)               | O(n)                 |

- **时间复杂度**：所有遍历方式均需访问每个节点一次，时间复杂度为O(n)，n为节点数。
- **空间复杂度**：递归实现受树高影响（最坏情况为O(n)，平衡树为O(log n)），非递归实现依赖栈，最坏情况下栈中需存储所有节点，为O(n)。


## 五、总结
1. **递归实现**：代码简洁，适合简单场景，但可能存在栈溢出风险。
2. **非递归实现**：手动管理栈，灵活性强，适用于复杂场景或对内存控制要求高的场景。
3. **应用场景**：根据具体需求选择遍历方式，如中序遍历常用于二叉搜索树的有序输出，后序遍历常用于释放树资源。

通过对比递归与非递归实现，能更深入理解二叉树遍历的本质，同时提升算法设计与代码优化能力。

二叉树的前中后序遍历

留痕使用说明

> 使用SPDK NVMe of RDMA 实现多NVMe设备共享



## 一、编译、安装spdk

### 1.1、下载
1.1.1 下载spdk源码
首先，我们需要从GitHub上克隆SPDK的源码仓库。打开终端，输入以下命令：

```bash
git clone -b v22.01 https://github.com/spdk/spdk.git
cd spdk
```

**1.1.2 下载子模块**

接下来，我们需要初始化并更新SPDK的子模块。
```bash
git submodule update --init
```

1.1.3 安装依赖

为了确保编译过程顺利进行，我们需要安装SPDK所需的依赖项。运行以下命令来自动安装这些依赖：

```bash
sudo ./scripts/pkgdep.sh
```

1.1.4 编译

现在，我们开始编译SPDK。

```bash
./configure --with-rdma --with-shared
sudo make
```

1.1.5 执行单元测试

编译完成后，我们需要运行单元测试来验证SPDK是否安装成功。

```bash
./test/unit/unittest.sh
```

最后如果输出 **all unit test passed**，代SPDK安装成功

![image.png](/static/img/4b8af98b61d073ef87369c183ffd5fdd.image.webp)

### 1.2、配置设备

1.2.1 绑定设备

在开始之前，我们需要将NVMe设备绑定到SPDK。运行以下命令来完成绑定：

```bash
sudo scripts/setup.sh

# 正确结果：
# 0000:0b:00.0 (15ad 07f0): nvme -> uio_pci_generic

# 查看状态
sudo ./scripts/setup.sh status

# 解绑设备
sudo ./scripts/setup.sh reset
```

![image.png](/static/img/804984a8a2ec3e352222bc9211285eda.image.webp)

**0000:b4:00.0** 和 **0000:b5:00.0**是设备编号，下面会用到

## 二、服务端配置

1. 启动 nvmf_tgt 

在服务端，我们需要启动nvmf_tgt来提供NVMe over Fabrics服务。打开一个新的终端，运行以下命令：

```bash
build/bin/nvmf_tgt
```

终端将输出类似以下的内容：

```plain
[zhousk@slave02 spdk]$ build/bin/nvmf_tgt -i 0
[2025-04-28 19:26:00.347292] Starting SPDK v22.01 git sha1 47737f1 / DPDK 21.11.0 initialization...
[2025-04-28 19:26:00.347451] [ DPDK EAL parameters: [2025-04-28 19:26:00.347487] nvmf [2025-04-28 19:26:00.347515] -c 0x1 [2025-04-28 19:26:00.347543] --log-level=lib.eal:6 [2025-04-28 19:26:00.347567] --log-level=lib.cryptodev:5 [2025-04-28 19:26:00.347623] --log-level=user1:6 [2025-04-28 19:26:00.347651] --base-virtaddr=0x200000000000 [2025-04-28 19:26:00.347709] --match-allocations [2025-04-28 19:26:00.347737] --file-prefix=spdk0 [2025-04-28 19:26:00.347789] --proc-type=auto [2025-04-28 19:26:00.347815] ]
EAL: No available 1048576 kB hugepages reported
EAL: No free 2048 kB hugepages reported on node 1
TELEMETRY: No legacy callbacks, legacy socket not created
[2025-04-28 19:26:00.532151] app.c: 601:spdk_app_start: *NOTICE*: Total cores available: 1
[2025-04-28 19:26:00.673833] reactor.c: 943:reactor_run: *NOTICE*: Reactor started on core 0
[2025-04-28 19:26:00.673911] accel_engine.c: 510:spdk_accel_engine_initialize: *NOTICE*: Accel engine initialized to use software engine.
```

2. 在另一个终端，使用rpc.py脚本来配置NVMe over Fabrics

```bash
# 1. 启动 RDMA
scripts/rpc.py nvmf_create_transport -t RDMA -u 8192 -i 131072 -c 8192

# 2. 将 NVMe 控制器附加到 SPDK 的块设备层
# 0000:b4:00.0 是上文的 BDF
./scripts/rpc.py bdev_nvme_attach_controller -b NVMe1 -t PCIe -a 0000:b4:00.0
# output: NVMe1n1

# 3. 创建 subsystem
# cnode1、SPDK00000000000001 可以自定义
./scripts/rpc.py nvmf_create_subsystem nqn.2016-06.io.spdk:cnode1 -a -s SPDK00000000000001 -d SPDK_Controller1

# 4. 添加 namespace
./scripts/rpc.py nvmf_subsystem_add_ns nqn.2016-06.io.spdk:cnode1 NVMe1n1
# NVMe1n1 是 2 中的输出

# 5. 添加监听
# -a 是本机 ip，-s 是端口，可修改
./scripts/rpc.py nvmf_subsystem_add_listener nqn.2016-06.io.spdk:cnode1 -t rdma -a 192.168.200.202 -s 4420 -f ipv4

# 获取 subsystem 信息
./scripts/rpc.py nvmf_get_subsystems


# 下面是删除操作（可选）

# 删除 subsystem
./scripts/rpc.py nvmf_delete_subsystem nqn.2016-06.io.spdk:cnode1
# 删除 ns
# ns_id 通过 nvmf_get_subsystems 获取
./scripts/rpc.py nvmf_remove_ns <nsid>
# 移除监听
./scripts/rpc.py nvmf_subsystem_remove_listener nqn.2016-06.io.spdk:cnode1 -t rdma -a 192.168.200.202 -s 4420
```

4. 获取 subsystem 信息

```json
./scripts/rpc.py nvmf_get_subsystems
```

输出下面这些信息

```json
[
  {
    "nqn": "nqn.2014-08.org.nvmexpress.discovery",
    "subtype": "Discovery",
    "listen_addresses": [],
    "allow_any_host": true,
    "hosts": []
  },
  {
    "nqn": "nqn.2016-06.io.spdk:cnode1",
    "subtype": "NVMe",
    "listen_addresses": [
      {
        "transport": "RDMA",
        "trtype": "RDMA",
        "adrfam": "IPv4",
        "traddr": "192.168.200.202",
        "trsvcid": "4420"
      }
    ],
    "allow_any_host": true,
    "hosts": [],
    "serial_number": "SPDK00000000000001",
    "model_number": "SPDK_Controller1",
    "max_namespaces": 32,
    "min_cntlid": 1,
    "max_cntlid": 65519,
    "namespaces": [
      {
        "nsid": 1,
        "bdev_name": "NVMe1n1",
        "name": "NVMe1n1",
        "nguid": "35354A30581000030025384700000003",
        "uuid": "35354a30-5810-0003-0025-384700000003"
      }
    ]
  }
]
```

此时 **nvmf_tgt** 显示 

[2025-04-28 19:26:24.621233] rdma.c:2668:nvmf_rdma_listen: *NOTICE*: *** NVMe/RDMA Target Listening on 192.168.200.202 port 4420 ***


**这样就完成了！！！**


## 三、客户端配置
在客户端，我们可以使用SPDK自带的测试工具来验证NVMe over Fabrics的配置是否成功。

```plain
./build/examples/perf -r 'trtype:RDMA adrfam:IPv4 traddr:192.168.200.202 trsvcid:4420' -q 128 -o 4096 -w read -t 10
```

![image.png](/static/img/000fd7102586a961833db68879d691b0.image.webp)

【学习笔记】SPDK NVMe of RDMA

👨🏻‍💻这是一个充满知识💬的链接，快点进来看看你的好友给你分享了什么干货吧❣️