-
Notifications
You must be signed in to change notification settings - Fork 0
How, and why we use Redis
This page briefly describes the problems that lead to me picking Redis, as well as how I implemented solutions.
These features are listed in the order that they were implemented.
When we first started buffering writes to the database, we hit a snag where the system experienced significant periods of downtime due to blocking writes to disk. While the buffers were being flushed, we couldn't add any new data to them (as they were full), and we couldn't trust the database because it hadn't reached full consistency with the application yet. The only way to circumvent the issues here would be to cache relevant data in-memory, either in our app or in a fast remote key-value store.
Trade data is different from most data on the exchange; it remains static after it's created. We don't need it for future exchange, or even account operations, aside from rare occurrences like allowing a user to view their past trades, or keeping track of ownership of stock.
For these reasons, trade data really doesn't need to be in RAM, and it especially doesn't need to be taking up our application's address space. The ideal place to store trade data is on disk, but there are scenarios where storing it in RAM, at least temporarily, is essential.
Lets say we're flushing the Trade buffer to disk (reason? it's near capacity). This process takes some time, maybe seconds, maybe minutes, possibly even hours (factors include disk speed, number of inserts, etc). Then, for an unknown period of time, we cannot be sure that the database is fully consistent and will have the most recent trades of the user. As stated earlier, we really don't want to waste our limited RAM on storing trades, but we need to have a fast way to store and access this data during the period of uncertainty.
This is a great opportunity for a remote key-value store like Redis. We can just associate a list of trades to a user, and over time we can grow the list as more trades are executed, or shrink the list as trades make their way into our Postgresql server (TODO still).
During program execution, we cache users in our app when they submit/cancel orders, or have orders filled by someone else. While a user is in cache, we keep track of any new trades that occur, and once the user is evicted (either normal eviction or on controlled shutdown of the exchange) we write all new trades to Redis.
An order is converted into a trade in one of 2 ways, either the order is the filled, i.e it was pending and a new order came along and filled it, or the order is the filler--it is the new order that filled an old one.
We differentiate trades in this way on an account basis. In any trade, there is a filler order and a filled order, so one account will store the trade in their filled list, and the other in their filler list. We use the following keys: filled:user_id and filler:user_id.
This is a simple performance enhancement, but under high user request load it can be pretty important. Previously, we read users straight from Postgres; an approach that performed poorly when lots of different users made requests. In a realistic scenario, most of the high frequency users would remain in the in-app cache, but for the simulations I ran (in which users are randomly picked), decreasing access times made a significant runtime impact.
We store basic account information like username, user_id, and passwords in Redis. This entire program is currently a security nightmare, and so if I have time I'll consider hash + salting passwords, and plugging any sql injection vulnerabilities, but for now this is what we've got. We also have a user_id --> username mapping to help us determine which orders belong to which user quickly. This is something that comes up when we process trades on the exchange, since Orders store an associated user_id, rather than the username (data compaction reasons); see update_single_user().
User Accounts
user:username
User ID --> Username
id:user_id
This feature builds on the idea of caching users in our app rather than constantly reading their data from Redis or Postgres.
When a user wants to submit or cancel an order, or request to see their account activity, we need to get access to some, or all of their pending orders. In the case of submitting an order, we need to make sure that the new order doesn't fill an old order placed by the same user. As for cancelling, we have to be certain that the order that the user has requested to cancel actually belongs to them. Rather than going through the markets of the exchange each time the user requests to do one of these actions, we opt to cache this data in the users account once. This data remains in their cached account until they're evicted at some point in the future, meaning we have fast access to all their pending orders.
Gathering this data occurs in a method called fetch_account_pending_orders(). Previously, this method would scan every market on the exchange, then for each market, it would iterate over all the orders to see if the order.user_id matched the requesting users's user_id. This approach can obviously become expensive when the number of orders and markets gets large, ex. 3000 markets with 100,000 pending orders each. Suppose we have 10,000 unique users who place 1 order each, each order is handled sequentially. This means we will have to call fetch_account_pending_orders 10,000 times, each call requiring 3000 x 100,000 = 300,000,000 comparisons. This totals to 3,000,000,000,000 (3 TRILLION) comparisons, some 99.999% of which are completely unnecessary!
Clearly, we need to decrease our search space, and we do so by storing markets in which each user has pending trades in Redis. This is done in the following way:
- We have
active_markets:user_id, which is a sorted set. - Sorted sets are sets where the elements have an associated score, in our case, the elements are market symbols like
$TSLA, and the score is the number of pending orders the user has in that market. - When the score for a market reaches 0, we remove the market from the set.
With this simple data structure, we can limit our search in fetch_account_pending_orders to the markets found in active_markets:user_id. For the typical user, this will likely be less than ~10 markets, resulting in a massive decrease in our search space.
This isn't the optimal way to do this, since individual markets might have millions of pending orders, but it was a simple first step, and is very easy to maintain. The optimal thing would probably be to maintain a list of the pending orders of each user in Redis, but this would require a lot of work and wouldn't be necessary until scaling became an issue. At that point, this would be an obvious problem to tackle.
I liked this approach because it's very similar to Reference Counting in Rust, a method by which the compiler can keep variables from going out of scope until the last reference is dropped. I also implemented this approach in a way that minimized communication with Redis, since we only update the active_markets:user_id set when a user is evicted from cache (the data is summarized during program execution).