I know that this was a very hot topic when SundaeSwap came out.
How did the team solve this?
A good thing to remember when developing on Cardano is that there exists no global state! The state and its history of the blockchain is captured in a graph, where the current state of the chain are the outer leafs of this graph.
This above structure allows the blockchain to process transactions that append to this graph to be highly concurrent. The only problem is, once a leaf has left the current state and has become history, then other transaction cannot use it anymore. This latter is the misnamed “concurrency problem”. I call this misnamed, since the whole ledge is as concurrent as it can be. With only local state, you thus have to design your protocols accordingly, an EVM style approach (which relies on a global state) is not possible.
In the most common dexes liquidity is provided via a liquidity pool. This is a centralized piece of data that stores the information about the state. When a transaction utilized this pool, it needs to know the entire state of that pool. On Cardano, this thus has to be represented in a single unspent transaction output, no way around that. But since every transaction consumes this output and pushes it to the history of the graph creating a new location for the state of the pool, other transaction that try to utilize it as well lose track of its location. This means that only one transaction per block can trade with the pool.
To overcome this, we introduce a waiting line of outputs that want to interact with this pool. Then each block, these waiting transactions are combined to create multiple trades with the same pool in one transaction. This solves the problem.
For more information see (1)
This picture helps visualize the graph, here the E, F, G, H, I are leafs (these are nodes without any children) representing the current state of the blockchain. The rest of the nodes are already consumed outputs in the past.