第四章 FPGA实现订单簿：哈希表与CAM设计
订单簿，说白了就是交易所的「记账本」。高频交易里，谁记账快谁就赚钱。我刚开始做这个项目时，觉得用软件写个订单簿挺简单的，但放到FPGA上，事情就完全不一样了。
硬件实现订单簿，核心就三个问题：怎么存？怎么查？怎么改？
4.1 哈希表 vs CAM：两种查找哲学
订单簿里最频繁的操作是什么？是查找。给定一个价格，找到对应的订单队列。软件里我们用红黑树、跳表，但硬件里，我们有两个选择：哈希表和CAM。
哈希表：把价格通过哈希函数映射到一个地址。优点是省资源，缺点是可能有冲突。我在项目中遇到过哈希冲突导致订单丢失的情况，排查了整整两天。
CAM（内容可寻址存储器）：直接拿价格去匹配，并行比较所有条目。速度快，但费资源。你想想看，一个条目就要一堆比较器。
我的建议：价格档位少（比如几千个）用CAM，价格档位多（几万个）用哈希表。暗池交易通常价格档位不多，我个人习惯用CAM。
4.2 CAM的硬件实现
CAM的核心思想很简单：输入一个数据，输出匹配的地址。但实现起来有几个坑。
// 一个简单的CAM模块
module cam #(
parameter DEPTH = 1024,
parameter WIDTH = 32
)(
input clk,
input rst_n,
input [WIDTH-1:0] search_data,
input search_en,
output reg [DEPTH-1:0] match_addr, // 独热码
output match_found
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
wire [DEPTH-1:0] match_wire;
genvar i;
generate
for(i = 0; i < DEPTH; i = i + 1) begin
assign match_wire[i] = (mem[i] == search_data) ? 1'b1 : 1'b0;
end
endgenerate
always @(posedge clk or negedge rst_n) begin
if(!rst_n)
match_addr <= {DEPTH{1'b0}};
else if(search_en)
match_addr <= match_wire;
end
assign match_found = |match_addr;
endmodule嗯，这里要注意：CAM的匹配逻辑是组合逻辑，直接连到比较器上。如果DEPTH很大，组合路径会很长，时序容易出问题。我曾经在1024深度的CAM上跑200MHz，结果setup time违例，最后不得不拆成两级流水。
避坑指南：CAM深度超过512时，建议用流水线结构。我曾经因为没注意这个，导致整个订单簿在高峰期丢单，被交易员追着骂了一周。
4.3 价格队列的硬件实现
每个价格档位对应一个订单队列。队列里存的是订单ID，按价格时间优先级排序。硬件实现队列，我推荐用双端口BRAM + 头尾指针。
| 队列操作 | 硬件实现 | 时钟周期 |
|---|---|---|
| 插入（尾部） | 写BRAM，尾指针+1 | 1 |
| 删除（头部） | 头指针+1 | 1 |
| 删除（中间） | 需要移动数据，复杂 | N |
| 查询头部 | 读BRAM | 1 |
你可能会问：删除中间订单怎么办？比如一个订单要撤单，它可能在队列中间。软件里直接链表删除就行，硬件里就麻烦了。
我的做法是：标记删除法。不真的移动数据，而是给每个订单加一个valid位。删除时只把valid置0，查询时跳过无效条目。代价是队列会慢慢变「脏」，需要定期压缩。
4.4 订单插入与删除的流水线设计
高频交易里，一微秒可能就有几百个订单进来。单周期处理一个订单是基本要求。流水线设计就是把一个操作拆成多个阶段，每个阶段一个时钟周期。
我设计的订单处理流水线分5级：
- 解析阶段：解析网络包，提取订单信息
- 查找阶段：用CAM查找价格档位
- 队列操作阶段：读/写队列BRAM
- 状态更新阶段：更新订单簿状态
- 响应阶段：生成确认消息
流水线最怕什么？数据冲突。比如前一个订单刚插入，后一个订单就要查这个价格档位。解决办法是旁路转发：把上一级的结果直接传给下一级，不用等写回BRAM。
小技巧：流水线深度不是越深越好。5级流水线处理一个订单，延迟是5个时钟周期。如果时钟是200MHz，就是25ns。这个延迟对高频交易来说已经有点大了。我一般控制在3-4级。
4.5 并发访问控制
订单簿是共享资源，多个端口可能同时读写。比如一个端口在插入买单，另一个端口在查询卖单。怎么保证数据一致性？
硬件里没有锁的概念，我们用的是多端口存储器。Xilinx的BRAM支持真双端口，可以同时读写不同地址。但如果是同一地址，就有冲突了。
我的解决方案：
- 读写分离：插入操作走写端口，查询操作走读端口
- 乒乓操作：两个BRAM交替工作，一个写一个读
- 优先级仲裁：给不同操作分配优先级，高优先级的先执行
我记得有一次，一个同事没做并发控制，结果两个端口同时修改同一个价格档位的头指针，导致整个队列乱掉。交易数据对不上，最后回滚了整整一天的数据。
核心原则：硬件并发控制，宁可多花资源做冗余，也不要冒险共享。一个错误的订单簿，比慢10倍的订单簿更可怕。
4.6 本章知识体系
下面这张图展示了订单簿硬件实现的核心逻辑：
这张图把整个流程串起来了。从订单输入开始，经过流水线处理，用CAM或哈希表找到价格档位，操作对应的价格队列，最后通过并发控制输出结果。每个环节都可能成为瓶颈，需要仔细优化。
个人经验：刚开始做订单簿时，我总想一次把所有功能都做进去。结果调试了两个月还没跑通。后来学乖了，先做一个最简单的版本，只支持插入和查询，跑通了再加删除和修改。迭代开发在硬件里同样适用。
好了，这一章的内容就到这里。订单簿的硬件实现，说白了就是存储结构 + 流水线 + 并发控制。把这三个点吃透了，剩下的就是工程细节了。
公众号:蓝海资料掘金营，微信deep3321