第四章：订单簿数据结构设计

各位同学，今天我们来聊聊订单簿数据结构设计。这章内容，说白了就是硬件订单簿的「骨架」。骨架搭不好，后面再牛的算法也跑不起来。

我个人习惯把订单簿拆成三个核心模块：价格队列、深度存储、查找映射。咱们一个一个啃。

4.1 价格队列的硬件实现

先说说价格队列。软件里用链表实现价格队列，很简单。但硬件里呢？你想想看，FPGA里没有动态内存分配，链表那套玩不转。

我建议用静态数组+指针的方式。每个价格档位对应一个队列，队列深度固定。比如我做过一个项目，订单量峰值每秒500万笔，队列深度设成256就够用了。

代码示例（Verilog）：

module price_queue #(
    parameter DEPTH = 256,
    parameter WIDTH = 64
)(
    input clk,
    input rst,
    input wr_en,
    input [WIDTH-1:0] wr_data,
    input rd_en,
    output reg [WIDTH-1:0] rd_data,
    output full,
    output empty
);
    reg [WIDTH-1:0] mem [0:DEPTH-1];
    reg [7:0] wr_ptr, rd_ptr;
    reg [8:0] count; // 多1位用于判断满/空
    
    always @(posedge clk) begin
        if (rst) begin
            wr_ptr <= 0;
            rd_ptr <= 0;
            count <= 0;
        end else begin
            if (wr_en && !full) begin
                mem[wr_ptr] <= wr_data;
                wr_ptr <= wr_ptr + 1;
                count <= count + 1;
            end
            if (rd_en && !empty) begin
                rd_data <= mem[rd_ptr];
                rd_ptr <= rd_ptr + 1;
                count <= count - 1;
            end
        end
    end
    
    assign full = (count == DEPTH);
    assign empty = (count == 0);
endmodule

4.2 基于BRAM的深度存储

价格队列本身用BRAM实现，那订单簿的完整状态存哪？还是BRAM。FPGA里BRAM是宝贵的资源，一块36Kb的BRAM能存512个72bit的数据。

我常用的方案是分层存储：

• L1缓存：存当前最优买卖盘口（用寄存器实现，零延迟）
• L2缓存：存最近活跃的10-20个价格档位（用分布式RAM）
• L3存储：存完整订单簿（用BRAM）

为什么要分层？说白了，就是拿空间换时间。高频交易里，90%的查询都集中在最优盘口附近。把热点数据放寄存器里，查询延迟能压到1个时钟周期。

存储层级	实现方式	容量	访问延迟
L1	寄存器	4-8个价格档位	1 cycle
L2	分布式RAM	16-32个价格档位	2-3 cycles
L3	BRAM	全部价格档位	3-5 cycles

4.3 哈希表与CAM的硬件映射

订单簿里有个关键操作：根据订单ID快速找到它所在的队列位置。软件里用哈希表，O(1)查找。硬件里呢？

我推荐用CAM（内容可寻址存储器）。CAM的硬件本质是并行比较器阵列，输入一个key，所有条目同时比较，一个时钟周期出结果。

但CAM有个缺点：贵。一个条目大概要20-30个LUT+FF。所以不能全量用CAM，得混合着来：

• 活跃订单（最近100笔）：用CAM，查找延迟1 cycle
• 历史订单：用哈希表映射到BRAM地址，查找延迟3-5 cycles

哈希表在硬件里怎么实现？我习惯用线性探测法。冲突了就往下一个地址找。代码实现也不复杂：

module hash_table #(
    parameter SIZE = 1024
)(
    input clk,
    input [31:0] key,
    input [15:0] value_in,
    input wr_en,
    output reg [15:0] value_out,
    output reg found
);
    reg [31:0] keys [0:SIZE-1];
    reg [15:0] values [0:SIZE-1];
    reg valid [0:SIZE-1];
    
    integer i;
    reg [9:0] hash_addr;
    
    always @(posedge clk) begin
        hash_addr <= key[9:0]; // 简单哈希：取低10位
        
        if (wr_en) begin
            // 线性探测，找到空位或相同key
            for (i = 0; i < SIZE; i = i + 1) begin
                if (!valid[hash_addr] || keys[hash_addr] == key) begin
                    keys[hash_addr] <= key;
                    values[hash_addr] <= value_in;
                    valid[hash_addr] <= 1;
                    break;
                end
                hash_addr <= hash_addr + 1;
            end
        end else begin
            // 读操作
            found <= 0;
            for (i = 0; i < SIZE; i = i + 1) begin
                if (valid[hash_addr] && keys[hash_addr] == key) begin
                    value_out <= values[hash_addr];
                    found <= 1;
                    break;
                end
                hash_addr <= hash_addr + 1;
            end
        end
    end
endmodule

4.4 整体架构图

下面这张图展示了订单簿数据结构的整体框架。你可以看到数据是怎么从网口进来，经过解析、查找、更新，最终输出盘口快照的。

嗯，这张图基本把数据流讲清楚了。行情数据进来，先解析，然后查订单ID在哪个队列里，更新队列状态，同时更新分层存储，最后盘口计算引擎算出最新的买卖盘口。

好了，这一章的内容就到这。数据结构是地基，地基稳了，后面咱们才能盖高楼。下一章我会讲订单簿的更新逻辑，包括增删改查的硬件流水线设计。

---

公众号:蓝海数据掘金营，微信deep3321