A Simple Transaction Implementation

Original link: https://luyuhuang.tech/2023/06/18/simple-transaction.html

In server programming, transactions are often very important, and one of its very important functions is to ensure the integrity of a series of operations. For example, the server needs to execute two modification operations a and b successively to process a request, and both of them may fail; if a succeeds but b fails, the transaction will be responsible for rolling back the modification of a. Just imagine if the a operation is to deduct the balance, and the b operation is to deliver the goods. If the delivery fails, the money has to be returned. If the server uses a database system that supports transactions, such as MySQL, things are easy to handle. Otherwise, implementing similar logic would be tricky and error-prone.

I hope to have a simple transaction system to achieve this effect: For example, in the following code, handler function handles business logic. As long as an exception is thrown anywhere in handler function, all modifications in handler , whether it is _G.DB.last_update_time , data.order or data.money , will be rolled back.

 1
 2
 3
 4
 5
 6
 7

 function handler (data)
 _G .DB.last_update_time = os . time ()
 data.order_id = get_order_id()
 check_order(data)
 data.money = data.money - 10
 deliver(data)
 end

Because our program is single-threaded, there is no need to consider issues such as transaction isolation. So this so-called “transactional system” is just an automatic rollback mechanism.

In fact, I have seen similar transaction implementations before. Its approach is to store the data that needs to be modified (such as data above) in two copies, one is the official data and the other is the temporary data. The business code modifies the temporary data. If no exception is thrown, the temporary data overwrites the formal data (commit); otherwise, the formal data overwrites the temporary data (rollback). Temporary data is only a shallow copy of official data, and even then, the memory overhead is still very large. And because it is a shallow copy, this mechanism is invalid for fields of reference types (such as table). I don’t think this approach is good enough.

Recently, I was inspired by Nondeterministic Computing in section 4.3 of SICP , and thought that rolling back data is actually very simple-just change it back. When we modify the data, we record the value of the data before the modification. If an exception is caught, the corresponding data is changed back to the value before the modification. Let’s start with pcall :

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11

 local original_pcall = pcall
 function pcall (f, ...)
 begin()
 local ok, res = original_pcall(f, ...)
 if ok then
 commit()
 else
 rollback()
 end
 return ok, res
 end

Since pcall can be nested, ie pcall(function() pcall(function() end) end) , we use the stack to save the transaction context, push the stack in begin , and pop the stack when commit and rollback . So the top of the stack is the context of the current transaction. Call set to perform the modification operation, which will save the original value of the data in the context.

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13

 local stack = {}

 local function begin ()
 table . insert (stack, {})
 end

 function set (tab, key, val)
 local top = stack[#stack]
 if top then
 table . insert (top, {tab, key, tab[key]})
 end
 tab[key] = val
 end

When Committing, all assignment operations of the current transaction take effect, and the side effects caused by the current transaction are also side effects of the upper-level transaction. The original value of the data recorded in the current transaction needs to be moved to the context of the upper-level transaction (if any). When rolling back, the original value of each set operation is taken out sequentially from the back to the front, and the data is set to the value before modification to complete the rollback operation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17

 local function commit ()
 local top = table . remove (stack)
 local pi = stack[#stack]
 if pi then
 for _, assign in ipairs (top) do
 table . insert ( pi , assign)
 end
 end
 end

 local function rollback ()
 local top = table . remove (stack)
 for i = #top, 1 , -1 do
 local tab, key, val = table . unpack (top[i], 1 , 3 )
 tab[key] = val
 end
 end

When using it, it cannot be assigned directly, and it needs to call set . Of course, it can also be made into a meta table, but I don’t like it very much.

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10

 val = {}
 function test ()
 local old = val
 set( _G , 'val' , 42 )
 set(old, 1 , 1 )
 error ()
 end

 pcall (test) -- false nil
 next (val) -- nil

The entire implementation can be said to be very simple and effective, and the overhead is not large. The code was written by me, and there is still room for optimization: the old data storage in stack can use a more compact data structure; the code can be implemented in C to improve performance, etc.

This article is transferred from: https://luyuhuang.tech/2023/06/18/simple-transaction.html
This site is only for collection, and the copyright belongs to the original author.