FPGA-Based High-Throughput Key-Value Store Using Hashing and B-Tree for Securities Trading System
Open Access
- 30 December 2022
- journal article
- research article
- Published by MDPI AG in Electronics
- Vol. 12 (1) , 183
Abstract
Field-Programmable Array (FPGA) technology is extensively used in Finance. This paper describes a high-throughput key-value store (KVS) for securities trading system applications using an FPGA. The design uses a combination of hashing and B-Tree techniques and supports a large number of keys (40 million) as required by the Trading System. We have used a novel technique of using buckets of different capacities to reduce the amount of Block-RAM (BRAM) and perform a high-speed lookup. The design uses high-bandwidth-memory (HBM), an On-chip memory available in Virtex Ultrascale+ FPGAs to support a large number of keys. Another feature of this design is the replication of the database and lookup logic to increase the overall throughput. By implementing multiple lookup engines in parallel and replicating the database, we could achieve high throughput (up to 6.32 million search operations/second) as specified by our client, which is a major stock exchange. The design has been implemented with a combination of Verilog and high-level-synthesis (HLS) flow to reduce the implementation time.Keywords
This publication has 12 references indexed in Scilit:
- A Low-Latency Multi-Version Key-Value Store Using B-Tree on an FPGA-CPU Platform2019
- Ultra-Low Latency and High Throughput Key-Value Store Systems Over Ethernet2018
- Build fast, trade fast: FPGA-based high-frequency trading using high-level synthesis2017
- Memory efficient and high performance key-value store on FPGA using Cuckoo hashing2016
- An FPGA implementation of high-throughput key-value store using Bloom filter2014
- A flexible hash table design for 10GBPS key-value stores on FPGAS2013
- More Robust Hashing: Cuckoo Hashing with a StashSIAM Journal on Computing, 2010
- FlashLook: 100-Gbps hash-tuned route lookup architecture2009
- Cuckoo hashingJournal of Algorithms, 2004
- FPGA implementation of MD5 hash algorithm2002