Common interface for query functions in sql.DB and sql.Tx
I want to implement a command pattern upon the database/sql in golang. The goal is that no matter whether the client uses sql.DB or sql.Tx, it can get the result by executing the same command. So that, the client can decide which instance to pass the command according to its needs. The problem is golang is a strongly typed language; therefore, you have to define the instance type in command’s struct first. They are two different types(sql.DB and sql.Tx), and it bothers me.
There is an interesting discussion on Github of the golang standard library. I am looking for the same solution like the issue author’s proposal; thus, I read the whole posts in the discussion.
I extract two important points:
Many people have the same requirement, so the issue is more like a common abstraction to the high-level design. Libraries are used to ease up things and to not make everyone repeat the very same work.
Does such an interface need to live in the standard library? It is more like a design concept than a driver.
Originally, my thoughts were biased towards the former and then I felt that the latter was more correct. From my point of view, the common platform cannot meet everyone’s design concept, that is not practical. If there is indeed a design need, which means it have to be accomplished by a new high-level library. In this case, sqlexp has already played this role. We can either buy in it or create another one.
When we are using MySQL in golang, we usually adopt database/sql to finish our jobs. In my opinion, the most common driver must be go-sql-driver. It is efficient and easy to use but hard to use well.
Especially, the fetch result sets coming from SELECT are not a slice like other dynamic programming languages. In other dynamic language, we expect the results would be a list to represent what columns you want. Moreover, In Python, we can directly fetch the database and get a dict as a result set.
In golang, we have to define the variables first, and then manually assign those variables to Scan. This implementation results in 2 problems:
If we issued a SELECT *, we will encounter an error if the schema changes in the future.
If we want to ask for a new column, we have to aware where uses the result sets. And modify them all carefully although they didn’t care the new column.
To sum up, we need a method to mitigate those common problems after all. My idea comes from Python, I want the result sets to be a map, so that the caller will not be impacted if any change on the database.
In the previous article, we had introduced how to ensure the integrity of transferring money. However, it’s not good enough to prevent going wrong. That approach will probably take time to retry many times to make things be done, so that it consumes client’s time as well as occupying the database resource.
User Scenario
Suppose there is a table for maintaining the lottery tickets, and each ticket has its own owner, serial number and a flag, remain, of whether it is used or not. In addition, there is another table to keep winning records.
For instance, A had 3 tickets but used one. And then, B got one ticket. Besides, the used ticket wins 100 dollars for A.
Simple Design
According the our previous introduction, we will design the remain flag in an unsigned integer with the default value: 1. When consuming this ticket, we uses the atomic update to increase the remain by -1. If a user has only one ticket but wants to draw twice, the second attempt will fail due to the negative value of remain.
Represent in the psudo code is like:
1 2 3 4 5 6 7
`START TRANSACTION` A_ticket = `select id from tickets where \ remain = 1 and user = 'A' order by id limit 1` `update tickets set remain = remain - 1 where id = A_ticket` reward = bingo() `insert into rewards (id, reward) values (${A_ticket}, ${reward})` `COMMIT`
First, A’s first ticket will be picked out, and the lottery will start after deduction. Finally, the result will be updated into the database.
But the problem occurs in the assumption that A has two tickets like the example at the beginning of this article, which means that A can draw twice at the same time. When A draws twice simultaneously, it should be successful without fail.
Run the process once with the implementation we mentioned. The first one who comes in will get a ticket number 3 and the second one who comes in will also get the same ticket. As a result, the first draw will succeed but the second attempt will be failed. If it fails, then it must try again, and then it will get the ticket number 4 and succeed.
Such a procedure would be correct after all, but it is not good enough. When you have n tickets, you obviously can draw n times at the same time within O(1). However, such an implementation leads to O(n). Among them, O(n-1) is a retry. And, the higher the n, the worse the user experience.
Random select
Here comes the second design, we don’t order by the id; instead, we pick the ticket randomly to mitigate the failure. Therefore, we modify the original select statement to become:
A_ticket = *select id from tickets where remain = 1 and user = ‘A’ order by RAND() limit 1*
In this example, we don’t care about the drawback of order by RAND(); nevertheless, the random means it will sometimes go wrong. Worst of all, it may choose the ticket with a long validity period instead of the ticket is about to expire.
Requirement
Looking back at our needs, we need to draw a lottery “simultaneously” several times when the user has a few tickets, and use the tickets in order.
Final Solution
To achieve our goal, we can leverage Redis’ help. The purpose of Redis is to have a congestion control. In order to make all clients can succeed once, we have to dispatch the tickets to them correctly while highly concurrency occurs.
Bad approach
Usually, Redis is used to be a distributed optimistic lock to make sure the permission of a critical section, e.g.,
1 2 3 4 5 6
ret = `setnx lock 1` if not ret: raise Locked("already locked by others") else: do_something() `del lock`
If an application can set a lock in Redis, which means he can dominate this time period until he finishes his job; on the other hand, everyone must wait for him. Solving the problem in this way is still not very helpful, at most it can only speed up the client’s retry, because the client doesn’t need to go through the database operation and the lottery procedures.
Good approach
To solve this problem, we want to support multi-entrance by using Redis. The process is to push all the current ticket numbers through LPUSH, and use RPOP to take out the first one.
Because Redis’ single command is atomic, you can ensure that the tickets are correctly allocated to each call that comes in at the same time.
Let’s take a simple psudο code as an example:
1 2 3 4 5 6
do: A_owned_tickets = `select id from tickets where \ remain = 1 and user = 'A' order by id` `LPUSH A_owned_tickets ${owned_tickets}` A_ticket = `RPOP A_owned_tickets` while A_ticket != nil
1 2 3 4 5 6
`START TRANSACTION` `update tickets set remain = remain - 1 where id = A_ticket` reward = bingo() `insert into rewards (id, reward) values (${A_ticket}, ${reward})` `COMMIT` `DEL A_owned_tickets`
In the above example, we use uppercase to indicate Redis’ instructions. Let’s use the sequential diagram to get a deeper look at what’s going on.
The above is an ideal situation. Although A1 and A2 occur simultaneously, A1 is slightly earlier than A2, so there will be two complete sequences in Redis, [4, 3, 4, 3]. If A1 and A2 occur almost at the same time, it will be the following situation:
From the above figure, even if A1 and A2 occur almost simultaneously, it will not affect the accuracy. So what happens if A1 finishes its job faster, COMMIT the result and deletes the list?
We can see A2 got a nil at the first time, so he therefore had to retrieve the tickets from MySQL and push again to proceed the process. Even so, it is more efficient than the original commit failure after all the processes are run.
The worst case will happen when there is high concurrency, some clients are very fast and some clients are very slow, which will cause several retries and still fail. The flow as shown below.
If this is the case, you can adopt an alternative approach. Do not actively DEL the list, but use EXPIRE to delete. Choosing a reasonable timeout will relieve symptoms. However, it comes another problem, the validity of expired data. This is a trade-off, you can take the approach that suits your user scenario.
At last, if the amount of coming requests is greater than the owned tickets, the original schema design still works to reject the invalid operations(remain cannot be negative).
How to avoid the race condition and the negative value
Scenario
Suppose there is a table, bank.
Both A and B have 100, and A will transfer 70 dollars to B twice.
Simple Design: Wire after Checking Balance
It would be like this in pseudo-code:
1 2 3 4 5
A_owned = `select money from bank where name = A` B_owned = `select money from bank where name = B` if A_owned >= 70: `update bank set money = A_owned - 70 where name = A` `update bank set money = B_owned + 70 where name = B`
This is the simplest design; however, there are two defects:
Remained money is incorrect after updating.
After remitting, the balance comes to a negative value.
Let’s watch these two issues separately.
The root cause of the first issue is that if A initiates two transfers at the same time, both of the two times A_owned would be 100. We introduce this situation in time-series diagram below:
Finally, the A’s balance will become 30. This is the classic race condition. How to solve it?
Solution of Race Condition
In order to solve the race condition, there are three ways:
Atomic Update
Transaction plus Lock
Version Scheme
Atomic Update
The problem of this situation is using the unreliable data. To prevent this from happening, we shouldn’t update records via using the previous results but the current value in the database.
Change the origin statement:
update bank set money = A_owned — 70 where name = A
to the new statement:
update bank set money = money — 70 where name = A
This is the atomic update.
Transaction plus Lock
Before the introduction, I have to say, most people have a misunderstanding of the transaction. The transaction is not invincible and cannot avoid all race conditions. Thinking the transaction as a panacea is so wrong.
The transaction is invincible IF the isolation level of MySQL is set to Serializable Isolation; nevertheless, Serializable Isolation affects the database performance dramatically. Therefore, the most accepted compromise is Repeatable Read Isolation. On the other hand, MySQL is not able to prevent the race condition in the such criteria. According to the reference, InnoDB cannot handle Lost Update and Phantom, i.e., the race condition will still be happened.
If you say that, what is the use of the transaction?
The transaction is to protect the integrity of a bunch of database operations. We can rollback all the changing data if there is any error occurred, so that the dirty data will not commit into the database.
Let’s get down to the business; how to leverage the transaction? The example is as follows:
1 2 3 4 5
start transaction A_owned = `select money from bank where name = A for update` if A_owned >= 70: `update bank set money = A_owned - 70 where name = A` commit
By using for update, it can acquire an exclusive lock on the desired row. If another transaction with the same row entered, it must wait for the lock released. The working flow is like below:
From the diagram above, we can know A2 gets the value after A1 has been finished. In addition, A2 gets 30 which is not enough to the transfer, thus, A2 finishes its job without doing anything.
Version Scheme
This approach is much more complicated than the two mentioned. We have to alter table to add a new column, version, to record the changes.
Before updating data, we have to retrieve the version first then update the row on the specific version. The code is like:
1 2 3
A_owned, old_ver = `select money, version from bank where name = A` if A_owned >= 70: `update bank set money = 30, version = version + 1 where name = A and version = old_ver`
Updating data and comparing the version must be executed simultaneously; otherwise, the operation will be failed. Let’s explain with a time-series diagram:
After A1 updates the row, the database returns 1 means there is one row affected, i.e., it updated successfully. But, A2 gets 0; in other words, no row is updated.
To Sum Up
We know there are three approaches to solve the race condition from the above introduction. However, the cost of the version scheme is too high, and the performance of the transaction plus lock is too poor. We really don’t need the heavy synchronization like the exclusive lock on an essential operation.
The atomic update is a better solution to apply to most use cases. Although we will no longer lose updates, negative values may still occur. Because the money is deducted 70 twice, the money is turned into -40 which is not allowed.
Total Solution
In addition to use the atomic update to modify the money, we still need some tricks to refrain from the negative values. My personal recommendation is to define the column, money, as an unsigned integer. Besides, use the transaction to protect the transfer. The final solution of this article is:
1 2 3 4 5 6
`start transaction` A_owned = `select money from bank where name = A` if A_owned >= 70: `update bank set money = money - 70 where name = A` `update bank set money = money + 70 where name = B` `commit`
Change two updates to the atomic update, and use transaction to guard the whole operation. Even if if A_owned >= 70 cannot stop A2, A2 will still get the failure due to the unsigned column. The transaction will be failed, and B won’t receive the money does not belong to him.
這在即時計算數量上有著高昂成本(注意，Innodb沒有維護一個內部計數，相反的，當下了SELECT COUNT(*) FROM LIKES WHERE...時幾乎總是重掃整張資料表)。我們也許可以透過別的組件，例如：快取或別張資料表來儲存計數，但即便我們這麼做，還是有一個重要的問題需要克服：如何確保實際的讚和額外儲存的讚數是一致的。
