Yesterday, there were three open-source spot CLOB implementations: Serum, Openbook v2, and Phoenix v1. Today, I release a fourth, appropriately named Yet Another Limit Order Book (acronymized to YALOB). Here's the story of how this one came to be:
As a small cadre of individuals knows, I'm working on the Meta-DAO, a DAO that will use futarchy to make decisions. Early on in the implementation of the Meta-DAO's program, I encountered a problem. In order to implement futarchy programatically, I needed to be able to fetch the prices of assets on-chain. Specifically, I needed to pull 10-day time-weighted average prices on conditional member tokens. But there was a problem: no existing CLOB implementation provided time-weighted average prices. Or at least, no CLOB that I could use. Drift v2 provides TWAPs, but Drift is for perpetual swaps, not just any ol' tokens.
My first instinct was to see if I could modify an existing CLOB to provide TWAPs. Searching through Serum's repo, I found a planned feature called permissioned markets. The idea with permissioned markets is that order book would have some 'open orders authority' who would need to sign off on all orders. This would allow a developer to write a wrapper contract that had its own custom logic about which orders could be accepted. For example, a wrapper contract could maintain a whitelist of KYCed accounts and only allow trades between whitelisted accounts. I realized that I could use this feature to create a TWAP. I would just have my wrapper contract record all trades' prices. From that, constructing a TWAP would be easy peasy lemon squeezy.
There was just one hitch in this plan. Permissioned markets were going to be released in Serum v4. But before v4 was released, that bad thing happened where everyone lost their money. And since it seemed unlikely that John J. Ray III was going to halt FTX's bankruptcy proceedings just so that I could build my beloved TWAP, I figured that TWAPs on Serum weren't going to work.
But Lady Fortuna wasn't all against me: OpenBook, the spiritual successor to Serum, had an open issue for permissioned markets. If I could implement permissioned markets for OpenBook, I could build a TWAP on OpenBook. So this is what I did, with a little help (okay, a lot of help) from a Very Cool Dude™ named Binye. On May 23rd, the PR was merged.
Now, it was on to the second half of the task: building the wrapper program. Or was it? You see, there is a siren song that afflicts all engineers and prevents us from getting useful things done. It goes something like ♫roll your own, baby♫, and man is it a hard song to tune out. What if I wrote my own CLOB, one with an integrated TWAP? Could I build something that was both simpler and more performant than what was already out there?
Although I can sometimes resist being seduced by the siren, this was not one of those times. The upshot of this is that I now, after 1.5 months of effort, have an answer to this question: yes, I can *pats self on back*. YALOB is both more simple and more performant than existing CLOBs. As far as simplicity goes, YALOB is ~1k lines of code, compared to Serum's 11.5k, Openbook's 12k, and Phoenix's 10.5k. It also uses a linked list to manage orders, rather than the more complex red-black tree or radix tree. And performance doesn't suffer either! The most important operations in any order book are limit order creates and deletes. Creating limit orders consumes 7k CUs in Serum (according to Toly), 20k CUs in Phoenix, ~30k CUs in Openbook on the latest master (although this is subject to change, since it's not in prod yet), and *drumroll* an average of 4k CUs in YALOB. Since we use a linked list, it's not constant-time, so the 4k estimate comes from conservatively estimating that the average new order needs to go 40 orders deep (when in fact most orders are placed very close to the top of the book). The worst-case is 5.7k CUs. And cancellations are where YALOB really shines. I didn't look at how many CUs the others consume to cancel an order, but since they use trees I would guess that deletion consumes roughly the same amount as insertion. But for YALOB, cancels are super cheap: 2.9k CUs! This is even cheaper than token transfers, which clock in at around 4.2k CUs.
I'm not going to argue that all of this is a free lunch. YALOB makes some trade-offs. For example, each side of the book can store only ~100 orders, instead of the typical ~1000. YALOB also doesn't include fancy features like automatically-expiring and oracle-pegged orders. But it's not bare-bones either: it has configurable fees, getters, and last but not least, a TWAP!
My main take-away from this experience is that it is possible to create Solana programs that are both very simple and very performant. I wrote YALOB in Anchor, which supposedly adds bloat. I only once used Godbolt to inspect the generated machine code. I didn't do any of the disgusting optimizations that EVM programs are forced to do. All I did was focus on three things: getting the data structures right, keeping structs small, and writing simple code. The result was a performant program.
In summary: