US-12620028-B2 - Efficient data relocation in an asymmetric multi-level caching structure for efficient data storage and retrieval

US12620028B2US 12620028 B2US12620028 B2US 12620028B2US-12620028-B2

Abstract

Systems and methods are provided herein for efficient data relocation within a multi-level memory cache. In particular, the method can include (i) storing specific data structures, or tiles, in a first memory cache that contain open order data representing open orders for one of buying or selling a financial instrument at consecutive price levels that fall within a defined price range between a most aggressive price and a least aggressive price; (ii) storing multiple tiles in a second memory cache that contain open order data representing open orders for one of buying or selling the financial instrument at prices that fall outside the defined price range; and relocating tiles between the first memory cache and the second memory cache in response to changes in the open order data for one of buying or selling the financial instrument at the most aggressive price.

Inventors

Anthony D. Amicangioli
B. Joshua Rosen
Ryan P. WALSH
Nicola AGUILAR-THOMSON

Assignees

Hyannis Port Research, Inc.

Dates

Publication Date: 20260505
Application Date: 20231207

Claims (15)

1 . A method of relocating files within a multi-level memory cache, comprising: storing a first plurality of tiles in a first memory cache by a cache manager the first plurality of tiles containing open order data representing open orders for one of buying or selling a financial instrument at consecutive price levels that fall within a defined price range, the consecutive price levels including a most aggressive price and a least aggressive price, the first memory cache being configured as a circular buffer array, and wherein the first plurality of tiles are stored in the circular buffer array in order of the consecutive price levels; storing a second plurality of tiles in a second memory cache by the cache manager, the second plurality of tiles containing open order data representing open orders for one of buying or selling the financial instrument at prices that fall outside the defined price range, the second memory cache being configured as a sparse hash array, and wherein the second plurality of tiles are stored in the sparse hash array according to a hash key algorithm; relocating tiles between the first memory cache and the second memory cache by the cache manager in response to changes in the open order data for one of buying or selling the financial instrument, wherein relocating the files between the first memory cache and the second memory cache by the cache manager includes: selecting a first tile to overwrite in the first memory cache, the first tile being stored at a first location of the circular buffer array, the first tile being associated with one of the most a aggressive price and the least aggressive price of the defined price range; determining whether the first tile selected to overwrite is empty; copying the first tile from the first location of the circular buffer array to a second location in the sparse hash array of the second memory cache in response to determining that the first tile is not empty; and overwriting the first location in the circular buffer array of the first memory cache vacated by the first tile with a second tile associated with one of a new most aggressive price or a new least aggressive price of the defined price range, and wherein the cache manager includes fixed logic implemented in hardware.
2 . The method as recited in claim 1 , wherein the first tile is associated with the least aggressive price, and the second tile is associated with the new most aggressive price, the method comprising: creating the second tile containing open order data representing at least one open order for one of buying or selling the financial instrument at the new most aggressive price; determining whether the first file associated with the least aggressive price within the defined price range contains any open order data; copying the first tile associated with the least aggressive price from the first location in the first memory cache to fall the second location in the second memory cache in response to determining that the first tile associated with the least aggressive price contains open order data; and overwriting the first location in the first memory cache with the second tile associated with the new most aggressive price.
3 . The method as recited in claim 2 , further comprising: overwriting the first tile associated with the least aggressive price at the first location in the first memory cache with the second tile associated with the new most aggressive price in response to determining that the first tile associated with the least aggressive price contains no open order data.
4 . The method as recited in claim 1 , wherein the first tile is associated with the most aggressive price, and the second tile is associated with the new least aggressive price, the method further comprising: determining whether the second tile is included among the second plurality of files stored in the sparse hash array of the second memory cache, wherein the second tile contains open order data for one of buying or selling the financial instrument at the new least aggressive price of the defined price range; and in response to determining that the second tile is included among the second plurality of tiles stored in the sparse hash array of the second memory cache, the method further includes overwriting the first tile associated with the most aggressive price at the first location in the circular buffer array of the first memory cache with the second tile associated with the new least aggressive price from a third location in the sparse hash array of the second memory cache.
5 . The method as recited in claim 4 , further comprising: creating the second tile associated with the new least aggressive price for the defined price range in response to determining that the second plurality of tiles stored in the second memory cache does not include any tile associated with the new least aggressive price; and overwriting the first tile associated with the most aggressive price at the first location in the circular buffer array of the first memory cache with the second tile associated with the new least aggressive price.
6 . The method as recited in claim 1 , wherein the most aggressive price is equal to or greater than a best bid price or equal to or lower than a best ask price.
7 . The method as recited in claim 6 , wherein the least aggressive price is a price among the consecutive price levels within the defined price range furthest away from the most aggressive price.
8 . An electronic data access system for relocating tiles within a multi-level memory cache, comprising: a cache manager coupled to a multi-level memory cache, the multi-level memory cache including a first memory cache and a second memory cache, wherein the cache manager includes fixed logic implemented in hardware; wherein the first memory cache is configured as a circular buffer array, and wherein the cache manager stores in the circular buffer array a first plurality of tiles containing open order data representing open orders for one of buying or selling a financial instrument at consecutive price levels that fall within a defined price range, the first plurality of tiles being stored in the circular buffer array in order of the consecutive price levels, the consecutive price levels including a most aggressive price and a least aggressive price, wherein the second memory cache is configured as a sparse hash array, and wherein the cache manager stores in the sparse hash array a second plurality of tiles containing open order data representing open orders for one of buying or selling the financial instrument at prices that fall outside the defined price range, the second plurality of tiles being stored in the sparse hash array according to a hash key algorithm; wherein the cache manager is configured to relocate tiles between the first memory cache and the second memory cache in response to changes in the open order data for one of buying or selling the financial instrument, wherein relocating the tiles between the first memory cache and the second memory cache by the cache manager includes: selecting a first tile to overwrite in the first memory cache, the first tile being stored at a first location of the circular buffer array, the first tile being associated with one of the most aggressive price and the least aggressive price of the defined price range; determining whether the first tile selected to overwrite is empty; copying the first file from the first location of the circular buffer array to a second location in the sparse hash array of the second memory cache in response to determining that the first tile is not empty; and overwriting the first location in the circular buffer array of the first memory cache vacated by the first tile with a second tile associated with one of a new most aggressive price or a new least aggressive price of the defined price range.
9 . The electronic data system as recited in claim 8 , wherein the first tile is associated with the least aggressive price, and the second tile is associated with the new most aggressive price, wherein the cache manager is configured to create the second tile containing open order data representing at least one open order for one of buying or selling the financial instrument at the new most aggressive price; wherein the cache manager is configured to determine whether the first tile associated with the least aggressive price within the defined price range contains any open order data; wherein the cache manager is configured to copy the first tile associated with the least aggressive price from the first location in the first memory cache to the second location in the second memory cache in response to determining that the first tile associated with the least aggressive price contains open order data; and wherein the cache manager is configured to overwrite the first location in the first memory cache with the second tile associated with the new most aggressive price.
10 . The electronic data system as recited in claim 9 , wherein the cache manager is configured to overwrite the first tile associated with the least aggressive price at the first location in the first memory cache with the second tile associated with the new most aggressive price in response to determining that the first tile associated with the least aggressive price contains no open order data.
11 . The electronic data system as recited in claim 8 , wherein the first tile is associated with the most aggressive price, and the second tile is associated with the new least aggressive price, wherein the cache manager is configured to determine whether the second tile is included among the second plurality of tiles stored in the sparse hash array of the second memory cache, wherein the second tile contains open order data for one of buying or selling the financial instrument at the new least aggressive price of the defined price range; and wherein, in response to determining that the second tile is included among the second plurality of tiles stored in the sparse hash array of the second memory cache, the cache manager is configured to overwrite the first tile associated with the most aggressive price at the first location in the circular buffer array of the first memory cache with the second tile associated with the new least aggressive price from a third location in the sparse hash array of the second memory cache.
12 . The electronic data system as recited in claim 11 , further comprising: wherein the cache manager is configured to create the second tile associated with the new least aggressive price for the defined price range in response to determining that the second plurality of tiles stored in the second memory cache does not include any tile associated with the new least aggressive price; and wherein the cache manager is configured to overwrite the first tile associated with the most aggressive price at the first location in the circular buffer array of the first memory cache with the second tile associated with the new least aggressive price.
13 . The electronic data system as recited in claim 8 , wherein the most aggressive price is equal to or greater than a best bid price or equal to or lower than a best ask price.
14 . The electronic data system as recited in claim 13 , wherein the least aggressive price is a price among the consecutive price levels within the defined price range furthest away from the most aggressive price.
15 . The electronic data system as recited claim 8 , wherein the cache manager includes any of a field programmable gate array (FPGA) and application specific integrated circuit (ASIC).

Description

RELATED APPLICATIONS This application claims the benefit of U.S. Provisional Application Nos. 63/430,777 and 63/430,778, both filed on Dec. 7, 2022, the disclosures of which are hereby incorporated by reference in their entirety. TECHNICAL FIELD Systems and methods described herein relate to caches for data storage and retrieval, and more particularly to an asymmetric multi-level caching structure for use in electronic trading systems, electronic data feed systems, or other automated systems involving priority-based data storage and retrieval. Systems and methods described herein also relate to efficient data relocation and key selection in a multi-level hash indexed cache. BACKGROUND In electronic trading systems, an order book receives orders from market participants to buy and sell stock or other financial instruments and attempts to fill the orders by matching them with contra-orders (e.g., buy for a sell—sell for a buy). Unmatched orders are stored in an open order data store until they are matched or otherwise canceled. An electronic trading system may also include an electronic data feed service that provides subscribers with trading data related to open orders and matches. There is a need for improved systems and methods for efficient data storage and retrieval from a data feed service or from an order book for electronic trading. BRIEF DESCRIPTION OF THE DRAWINGS The foregoing will be apparent from the following more particular description of example embodiments of the invention, as illustrated in the accompanying drawings in which like reference charters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the present invention. FIG. 1 is a schematic diagram that illustrates an automated trading system according to an embodiment. FIG. 2 is a schematic diagram that illustrates detailed components of the matching engine book of FIG. 1 according to an embodiment. FIG. 3 is a schematic diagram that illustrates the data structure of a tile according to one embodiment. FIG. 4 is a schematic diagram that illustrates an embodiment of an asymmetric multi-level cache that is provisioned for storage and retrieval of tiles according to a price priority scheme. FIG. 5 is a schematic diagram that illustrates an example provisioning of a first memory cache within the multi-level memory cache for a single stock. FIG. 6 is a flow diagram that illustrates a method for fetching tiles from the external multi-level cache according to an embodiment. FIGS. 7A and 7B are schematic diagrams that illustrate examples for determining a tile location within an active order region of the first memory cache using a target price tick as an index. FIG. 8 is a flow diagram that illustrates a method of generating a hash key to index an inactive price region of the second memory cache in the form of a sparse hash array according to an embodiment. FIG. 9 is a flow diagram that illustrates a method of processing different types of tiles according to an embodiment. FIGS. 10A-10D are schematic diagrams that illustrate examples of retrieving different types of tiles according to the method of FIG. 9. FIG. 11 is a flow diagram that illustrates a method for gradually adjusting a price-consecutive tile sequence within an active order region of the first memory cache to include more aggressive price tiles according to an embodiment. FIGS. 12A and 12B are schematic diagrams illustrating an example of gradually adjusting a price-consecutive tile sequence within the active buy order region of the first memory cache to include more aggressive price tiles having higher bid prices. FIG. 13 is a flow diagram that illustrates a method for gradually adjusting a price-consecutive tile sequence within an active order region of the first memory cache to include less aggressive price tiles according to an embodiment. FIGS. 14A and 14B are schematic diagrams illustrating an example of gradually adjusting a price-consecutive tile sequence within the active buy order region of the first memory cache to include less aggressive price tiles having lower bid prices. FIGS. 15A-15B is a flow diagram that illustrates a method 1500 for converting a target price to a tick with a consecutive integer sequence regardless of changes in minimum price variation between consecutive prices according to an embodiment. FIG. 16 is a flow diagram that illustrates a method 1600 of pre-fetching a tile in advance according to an embodiment. FIG. 17 is a schematic diagram illustrating a processing unit for optimizing the use of cache space within the multi-level memory cache according to an embodiment. FIG. 18 is a schematic diagram that illustrates an embodiment of an automated trading system, including a ticker plant that maintains a separate order book in the form of an asymmetric multi-level memory cache. FIG. 19 is a schematic diagram that illustrates another embodiment