<center> # Storing Database ORM Operations as Data **A Strategy for Linearizing Database Operations** *Originally published 2018-09-05 on [labs.oddslingers.com](https://labs.oddslingers.com/posts/Linearizing-database-operations-django.html).* <img src="https://i.imgur.com/YiU19Lv.jpg" style="width: 80%; border-radius: 14px; box-shadow: 4px 4px 4px rgba(0,0,0,0.04);"> <br/><br/> </center> **This post outlines a technique that can be used to queue database ORM operations in a data structure instead of in imperative code form.** Declarative design is great for dealing with complex logic that produces a series of state changes that need to be executed later in a specific order. This is the core idea behind the Redux state management library. Another good example is a game engine that needs to perform a bunch of database writes when each player moves, but wants all the writes to happen atomically at the end of each game step rather than scattered throughout the game loop code. *How do you know when you might need something like this?* Here are some code smells that often indicate hidden complexity and potentially unsafe database transactions lurking in a codebase: - are database logic and view logic intertwined in the codebase? - can two processes update the same rows without enforced locks or atomic operations? - are there a lack of tests that confirm data integrity when multiple processes modify the same rows? <br/> <center> <img src="https://i.imgur.com/kBITVs1.png" style="width: 80%; border-radius: 14px; box-shadow: 4px 4px 4px rgba(0,0,0,0.04);"> </center> ## Why would data be better than code? As a system becomes more advanced, there is a natural tendency for procedures to transition from being inscribed as code, to expressed as data. For example, typical CI/CD pipelines have gradually moved from bash scripts in the past, to YAML, json, or other data-centric config files now. Declarative Infrastructure as Code has been a great advancement in managing systems, from BSD jail config files, to docker-compose, to ansible-playbooks, all find ways to express complex system requirements as simple raw values in a text file. This principle extends beyond config management to code actual implementation. We can build systems in the form of pure functional layers that pass around some data, then perform side effects at the very end safely. Having as much complexity expressed as data aids in keeping layers of systems cleanly separated, and does wonders for testability. As you're probably heard a compsci teacher say before "find the right data structure and the problem solves itself". You can pass around a data structure that represents a complex sequence of events as simple values and test it like data by making assertions about its content. LISP discovered the power of code as data long ago. That being said, we're not going whole-hog into the meta-programming heavens like LISP, here we're illustrating a compact structure that solves one problem well: describing database changes. ## How can we represent a database operation as data? Here's a database operation you might see in imperative form, as it is typically written in Django codebases: ```python user = User.objects.get(id=123) user.balance = user.balance + 100 ``` Now we're going to transform that example from imperative code that *outlines steps*, into declarative data that *describes a desired outcome*. We can represent each operation on a database as a tuple, and each set of operations as a list of those tuples, forming a transaction. ```python Operation = Tuple[QuerySet, str, Dict[str, Any]] # NamedTuple works well too Transaction = List[Operation] ``` An individual operation can now look like this in data form: ```python operation: Operation = ( User.objects.filter(id=123), # QuerySet to update 'update', # func to call on the queryset {'balance': F('balance') + 100}, # kwargs for the func ) ``` Django documents this as: [Avoiding Race Conditions With `F()`](https://docs.djangoproject.com/en/2.1/ref/models/expressions/#avoiding-race-conditions-using-f). This structure works not only for updates, but also equally well for object creation and deletion: ```python operation1 = (User.objects, 'get_or_create', {'username': 'bob'}) operation2 = (User.objects.filter(username='bob'), 'delete', {}) ``` If `F()` expressions aren't enough, you can reuse this design to aquire a list of locks before your logic executes, and execute a different list of operations afterwards. ```jsx pre_logic_locks = [ (User.objects.filter(id=123), 'select_for_update, {}), ] ... post_logic_writes = [ (User.objects.filter(id=123), 'update', {'some_field': new_val}) ] ``` Of course, the ultimate declarative language is SQL, we can only get close with the Django ORM. <center> <img src="https://i.imgur.com/WVMRrDq.png" style="width: 80%; border-radius: 14px; box-shadow: 4px 4px 4px rgba(0,0,0,0.08);"> </center> ## How do we process a list of operations? Once we have any set of operations queued up in a list, we can execute them atomically together: ```python def execute_operations(operations: Transaction): with transaction.atomic(): for qs, func_name, kwargs in operations: func = getattr(qs, func_name) yield func(**kwargs) ``` In this way we can perform 20 or 30 field and row updates scattered across various tables while mitigating TOCTTOU bugs and excessively expensive locking. ## Why would we need this? Imagine you have a game loop with complex logic that takes 100ms to calculate the next gamestate after each player action. The logic needs to access and update several datase rows representing the game state, but the reads and writes happen scattered throughout the game loop. Because each game loop step needs to write all changes in a single transaction, and writes are scattered in a 100ms window, we know that to operate it safely we will need to hold some locks for the entire 100ms window. Lets take the example of a person joining a game and paying for some chips out of their wallet to start playing. To make sure we have enough chips balance to pay the join-game fee for the whole duration of the join transaction, we have to prevent concurrent games from modifying balance until we're done. Additionally, if they don't have enough chips, or if the game fails for some reason during the transaction, we don't want to leave partially commited database changes, we want to roll everything back together. Locking other games for 100ms is not great, because it effectively rate-limits all table changes to 10/s, in a way that's difficult to fix later because it requires a fundamental structural change in the code. If we can come up with an atomic solution that performs all writes in one go at the end, maybe we can bring the locking down to under 5 or 10ms. Grouping writes into single short atomic transactions should allow more games to run simultaneously, no more long locks on all objects shared between games. ```python join_game: Transaction = [ (GameAction.objects, 'create', {'user': bob, 'action': 'JOIN'}), (Game.objects.filter()) (UserBalance.objects.filter(user=bob), 'select_for_update', {}), (UserBalance.objects.filter(user=bob, amt__gte=5000), 'update') ] ``` ## Details ### Testability With transactions outlined as data, we can test assumptions about their behavior by simply asserting statements about the values in the operation tuples. ```python3 def balance_transfer(src: User, dst: User, amt: int) -> Transaction: return [ (UserBalance.objects.filter(user=src), 'select_for_update', {}), (BalanceTransfer.objects, 'create', {'src': src, 'dst': dst, 'amt': amt}), ... ] class TestBalanceTransfer: def test_lock_aquired(self): operations = balance_transfer(test_user_a, test_user_b, 100) assert operations[0].func = 'select_for_update' ... assert all(execute_operations(operations)), 'Some operations did not run' ``` These operation lists and objects can also be passed around, extended, and modified as needed much more easily than imperative code deep inside a view somewhere. ### Lazy QuerySet evaluation is mandatory It's critical that QuerySets don't get accidentally evaluated before they run in the transaction, as that may lead to stale data read into memory early on being written back to the db after other logic executes. We can prevent this easily by adding an assertion in our `execute_operations` function: ```python assert isinstance(queryset, QuerySet), 'QuerySets should not be evaluated before they are executed to maintain concurrency safety' ``` Evaluated QuerySets will be instances of `List` instead of `QuerySet`. ## Full example with locking & updates across multiple tables Here I show an example of a bank that needs to store both an `Account.balance` and a table of `BalanceTransfers` to keep track of credits and debits for each of their users. When transferring money between two users, it needs to update multiple inter-dependent rows and ensure that the assumptions about a user's balance hold true throughout the entire transaction. Specifically, we need to make sure that the source user doesn't have money withdrawn concurrently by other threads until we finish this transfer. ```jsx src = User.objects.get(id=123) dst = User.objects.get(id=987) amt = 1000 balance_transfer = [ # lock source's balance to prevent other withdrawals until transaction is over (Account.objects.filter(user=src), 'select_for_update', {}), # throws a NotFoundError if src user doesn't have enough money (Account.objects.filter(user=src, balance__gte=amt), 'get', {}), (BalanceTransfer.objects, 'create', {'src': src, 'dst': dst, 'amt': amt}), (Account.objects.filter(user=src, 'update', {'balance': F('balance') - amt}), (Account.objects.filter(user=dst, 'update', {'balance': F('balance') + amt}), ] execute_operations(balance_transfer) ``` ## Further Reading You may not use the Django ORM or you may have a different preferred way of representing transactions. If you think you've found a better way, give us a shoutout at @MonadicalSAS, we'd love to learn! If you're interested in database integrity and want to learn more, check out our other resources on designing safe systems with SQL databases and Python: - [Banking Blunders and Concurrency Challenges](https://labs.oddslingers.com/posts/Designing-A-Banking-System.html) - [PyGotham2018 Talk](https://github.com/pirate/django-concurrency-talk) - [Modeling Message Queues in TLA+](https://www.hillelwayne.com/post/tla-messages/) by Hillel Wayne (not our team)