3. 快照数据结构：价格-数量映射、红黑树、跳表在硬件中的实现考量

好，咱们接着聊订单簿快照的数据结构。说实话，这个题目我特别喜欢，因为它直接关系到硬件加速的成败。你想想看，软件里用个红黑树或者跳表，几毫秒的延迟根本无所谓。但在FPGA里，一个时钟周期就是几纳秒，选错数据结构，整个系统就废了。

我个人习惯把订单簿快照的数据结构分成三类来考量：价格-数量映射、红黑树、跳表。这三者在硬件里的实现思路完全不同，坑也各有各的深。

3.1 价格-数量映射：最直接的方案

价格-数量映射，说白了就是一个哈希表或者直接寻址表。把价格作为key，把对应的挂单总量作为value。这个结构在软件里太简单了，但在硬件里，嗯，要注意几个点。

我在项目中遇到过一个问题：价格精度怎么定？如果价格是浮点数，那映射就麻烦了。我建议直接用定点数，比如把价格乘以10000取整，作为RAM的地址。这样既保证了精度，又实现了O(1)的查找。

举个例子：

// 价格-数量映射的硬件实现示意
// 价格 = 100.25，映射为地址 1002500
// 如果价格范围是 0 ~ 1000000，需要 20 位地址线
// BRAM 深度 = 2^20 = 1,048,576 个条目
// 每个条目 32 位，存储挂单总量

module price_quantity_map (
    input clk,
    input [19:0] addr,      // 价格映射后的地址
    input [31:0] wdata,     // 写入的数量
    input we,               // 写使能
    output reg [31:0] rdata // 读出的数量
);

    // 使用 BRAM 实现
    reg [31:0] mem [0:1048575];
    
    always @(posedge clk) begin
        if (we)
            mem[addr] <= wdata;
        rdata <= mem[addr];
    end

endmodule

这个方案的好处是快，真的快。一个时钟周期搞定。但缺点也很明显：内存浪费。如果价格范围很大，但实际交易的价格点很少，那大部分BRAM都是空的。我曾经在一个项目中，价格范围需要24位地址，但实际活跃的价格点只有几百个。用BRAM直接映射，浪费了99.9%的存储空间。

3.2 红黑树：平衡的代价

红黑树在软件里是王者，但在硬件里，说实话，我不太推荐。为什么？因为红黑树的平衡操作太复杂了。

红黑树的五个性质，在硬件里实现起来，每个都是坑：

• 节点颜色：需要额外的1位来存储颜色信息
• 左旋/右旋：需要修改3-4个指针，每个指针都是多比特信号
• 插入后的修复：最多需要O(log n)次旋转和颜色调整
• 删除后的修复：更复杂，需要处理多种情况

你想想看，在FPGA里，每个时钟周期只能做有限的操作。红黑树的插入操作，在软件里可能只需要几十条指令，但在硬件里，可能需要几十个时钟周期。这对于低延迟的订单簿来说，是不可接受的。

我记得有一次，团队里有个新人坚持要用红黑树，说软件里都是这么做的。结果实现出来，插入一个价格点需要35个时钟周期。而我们的目标是整个订单簿更新在10个时钟周期内完成。嗯，后来还是换方案了。

3.3 跳表：硬件友好的概率结构

跳表是我个人比较喜欢的方案。为什么？因为跳表在硬件里实现起来，比红黑树友好太多了。

跳表的核心思想是用概率来替代平衡。每个节点随机决定它的层数。这样就不需要复杂的旋转操作了。

在硬件里实现跳表，有几个关键点：

1. 层级存储：每个节点需要存储多个层的指针。可以用BRAM数组来实现。
2. 随机数生成：用LFSR（线性反馈移位寄存器）生成随机数，决定节点层数。
3. 查找操作：从最高层开始，逐层向下。每层只需要比较一次。
4. 插入操作：先查找，再在每层插入指针。不需要旋转。

下面是一个跳表节点在硬件中的结构示意：

// 跳表节点的硬件结构
// 最大层数设为 8 层
// 每层包含一个指向下一个节点的指针

typedef struct {
    logic [31:0] price;      // 价格
    logic [31:0] quantity;   // 数量
    logic [2:0]  level;      // 节点层数 (0-7)
    logic [15:0] next_ptr[8]; // 每层的下一个节点指针
} skip_list_node;

// 查找操作：从最高层开始
// 每个时钟周期处理一层
// 8层最多需要8个时钟周期

always @(posedge clk) begin
    case (current_level)
        7: begin
            if (node[ptr].price < target_price)
                ptr <= node[ptr].next_ptr[7];
            else
                current_level <= 6;
        end
        6: begin
            if (node[ptr].price < target_price)
                ptr <= node[ptr].next_ptr[6];
            else
                current_level <= 5;
        end
        // ... 依次类推
        0: begin
            // 找到目标或确认不存在
            found <= (node[ptr].price == target_price);
        end
    endcase
end

这个实现的好处是：延迟可预测。最多8个时钟周期就能完成查找。而且插入操作也只需要在每层修改指针，没有复杂的平衡逻辑。

3.4 三种方案的对比与选择

好了，咱们来做个总结。三种方案各有优劣，选择哪个取决于你的具体需求。

特性	价格-数量映射	红黑树	跳表
查找延迟	1 时钟周期	O(log n) 时钟周期	O(log n) 时钟周期
插入延迟	1 时钟周期	O(log n) 时钟周期（含旋转）	O(log n) 时钟周期
存储效率	低（地址空间稀疏时）	高	中
实现复杂度	低	高	中
硬件资源消耗	BRAM为主	LUT+BRAM	BRAM为主
适用场景	价格范围小且密集	通用场景（不推荐硬件实现）	价格范围大且稀疏

我个人建议：

• 如果价格范围有限（比如只有几千个价格点），直接用价格-数量映射，简单粗暴。
• 如果价格范围很大，但活跃价格点不多，用跳表，平衡了速度和资源。
• 红黑树嘛，除非你有特殊需求，否则别在硬件里折腾它。

好了，关于快照数据结构的硬件实现，就聊到这里。记住，没有银弹，只有最适合你场景的方案。

---

公众号:蓝海资料掘金营，微信deep3321