About technologies behind Double 11 shopping carnival - naked flash sales, a different flash sales t

Background
The flash sales have been a permanent topic in the commodity transaction circle. From Double 11 shopping carnival to the hard-to-get ticket - is it that only a quick hand matters?
In fact, for the transaction platform, they not only face numerous real customers, but also many scripts, automated plug-in snap-up systems - the stress is imaginable.
There are a lot of flash sales means. For example, some databases adopt the queuing mechanism, some adopt the asynchronous messages and some others adopt transaction merging to handle the flash sales scenarios.
Today I want to introduce to you a more extreme means: naked flash sales.
(In fact, I have written similar articles a long time ago and I would like to talk about it again since it is around the Double 11 shopping carnival.)
At present, PostgreSQL database may be the only one that supports naked flash sales. It seems to be saying: come at me, all of you. It may sound a little aggressive, but it is truly that violent.
PostgreSQL provides an ad lock for you to unleash your passion to the full. Taking a 32-core 64-thread server for example, you can get and probe the ad lock 1.3 million times per second.
Just imagine, if a single server can support 1 million requests/second for flash sales operations, the flash sales is just nothing. 100 servers will be enough to handle 100 million requests/second of flash sales requests. So thrilling. Let me continue.

Introduction to flash sales scenarios
Although the flash sales have been quite common, I would like to briefly introduce the business background of flash sales to make this article more inclusive.
For example, the flash sales of an iPhone at one yuan. If I only have one iPhone available for the sales, and we regard it as a record, after the flash sale starts, the one who first gets it (updates the lock of the record) wins.
For the database, the bottleneck of the flash sales lies in the multiple concurrent updating requests for the same record. Only one or a few requests will succeed, and other requests will fail or fail to update the record.
For example, if there are 100 iPhones available for the flash sales, and there are 1 million users concurrently joining the flash sales for the iPhone, the minimal granularity will be the row-level lock for the database. When one user is updating this record, the other 999,999 users will spend the time waiting, and so on.
Except the 100 lucky ones, all other users wait for result in vain. They should not have even been in the database to waste the resources.
In a traditional approach, a mark bit is used to indicate whether this record has been updated or to record the number of updates (the number of iPhones).
update tbl set xxx=xxx,upd_cnt=upd_cnt+1 where id=pk and upd_cnt+1<=5;   -- We assume there are five iPhones available.

Shortcoming of this approach:
The user who gets this lock may succeed or fail to process this record, or it may need a long time (such as the database response is slow). Before the processing completes the transaction, other sessions can do nothing but wait.
The wait is not scientific, because for users who haven't won the lock, the wait is just a waste of time.

Common optimization methods for flash sales
1. The general optimization is to first use for update nowait or other ways to avoid wait, that is, the user does not need to wait if he or she fails to get the lock.
begin;
select 1 from tbl where id=pk for update nowait;  --  If the user cannot get the lock instantly, return an error. The transaction is rolled back.
update tbl set xxx=xxx,upd_cnt=upd_cnt+1 where id=pk and upd_cnt+1<=5;
end;

This can shorten the wait time of the user, because the request returns directly if it fails to get the lock instantly.
2. Merge requests, that is, to merge multiple update requests to one update request. This approach requires changes to the kernel and will damage the ACID. Because if the merged request fails to get the lock, all the users of the merged requests fail. (Request merging is not the same with group commit which will not damage the ACID.)
Next, let's take a look at the ad lock.
What is ad lock?
Based on the descriptions in the manual, ad lock is a kind of user-oriented lightweight lock. The locked object is an integer. Ad locks can be divided into transaction locks and session locks or into shared locks and exclusive locks.
In a single database, locks of different integer values can be obtained. If the value is the same, the TRY can be used to apply a lock. If the lock is not obtained, FALSE is returned immediately.
https://www.postgresql.org/docs/current/static/functions-admin.html#FUNCTIONS-ADVISORY-LOCKS

Table 9-87. Advisory Lock Functions

Name	Return Type	Description
pg_advisory_lock(key bigint)	void	Obtain exclusive session level   advisory lock
pg_advisory_lock(key1 int, key2 int)	void	Obtain exclusive session level   advisory lock
pg_advisory_lock_shared(key bigint)	void	Obtain shared session level advisory   lock
pg_advisory_lock_shared  (key1 int, key2 int)	void	Obtain shared session level advisory   lock
pg_advisory_unlock(key bigint)	boolean	Release an exclusive session level   advisory lock
pg_advisory_unlock(key1 int, key2   int)	boolean	Release an exclusive session level   advisory lock
pg_advisory_unlock_all()	void   Release	all session level advisory locks   held by the current session
pg_advisory_unlock_shared  (key bigint)	boolean	Release a shared session level   advisory lock
pg_advisory_unlock_shared  (key1 int, key2 int)	boolean	Release a shared session level   advisory lock
pg_advisory_xact_lock(key bigint)	void	Obtain exclusive transaction level   advisory lock
pg_advisory_xact_lock  (key1 int, key2 int)	void	Obtain exclusive transaction level   advisory lock
pg_advisory_xact_lock_shared(key   bigint)	void	Obtain shared transaction level   advisory lock
pg_advisory_xact_lock_shared  (key1 int, key2 int)	void	Obtain shared transaction level   advisory lock
pg_try_advisory_lock(key bigint)	boolean	Obtain exclusive session level   advisory lock if available
pg_try_advisory_lock  (key1 int, key2 int)	boolean	Obtain exclusive session level   advisory lock if available
pg_try_advisory_lock_shared  (key bigint)	boolean	Obtain shared session level advisory   lock if available
pg_try_advisory_lock_shared  (key1 int, key2 int)	boolean	Obtain shared session level advisory   lock if available
pg_try_advisory_xact_lock(key   bigint)	boolean	Obtain exclusive transaction level   advisory lock if available
pg_try_advisory_xact_lock  (key1 int, key2 int)	boolean	Obtain exclusive transaction level   advisory lock if available
pg_try_advisory_xact_lock_shared  (key bigint)	boolean	Obtain shared transaction level   advisory lock if available
pg_try_advisory_xact_lock_shared  (key1 int, key2 int)	boolean	Obtain shared transaction level   advisory lock if available

Usually the smallest-granularity locks that a database supports (open to users) are row locks. Row locks aren't nearly as lightweight as LWLOCK and SPINLOCK, so traditional row locks will become a very severe bottleneck in the flash sales scenario, including the lock wait.
Use of ad lock
The ad lock boasts many uses besides the flash sales which I am about to illustrate next, such as:
concurrent security checks,
UPSERT scenarios in recursive calls,
and for ensuring atomic operations in business logic design.
Performance indicators of ad locks
Because the ad lock is very lightweight, does not need to access the data and requires no execution of lengthy code, it is quite efficient.
Tests on 32-core 64-thread servers show that it supports up to 1.31 million lock requests/second.
vi test.sql
\set id random(1,100000000)
select pg_try_advisory_xact_lock(:id);

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 96 -j 96 -T 100

transaction type: ./test.sql
scaling factor: 1
query mode: prepared
number of clients: 96
number of threads: 96
duration: 100 s
number of transactions actually processed: 131516823
latency average = 0.072 ms
latency stddev = 0.070 ms
tps = 1314529.211060 (including connections establishing)
tps = 1315395.309707 (excluding connections establishing)
script statistics:
 - statement latencies in milliseconds:
         0.001  \set id random(1,100000000)
         0.074  select pg_try_advisory_xact_lock(:id);

Application of ad lock to flash sales
In databases, the commodity usually has a unique ID on which we can apply the lock. (Of course, if this ID can be overlapped between different tables, we can avoid the conflict by adding the offset or other means.)
The row lock will only be applied and updates be executed after the ID is locked successfully, so that the rewardless row lock wait can be avoided and lengthy query code can be dropped.
The concurrent updating QPS to a single record using the ad lock can reach 391,000 requests/second. The commodities in the flash sales will be quickly sold out, without further wasting the database resources.
create table test(id int primary key, crt_time timestamp);
insert into test values (1);

vi test.sql
update test set crt_time=now() where id=1 and pg_try_advisory_xact_lock(1);

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 64 -j 64 -T 100

transaction type: ./test.sql
scaling factor: 1
query mode: prepared
number of clients: 64
number of threads: 64
duration: 100 s
number of transactions actually processed: 39104368
latency average = 0.163 ms
latency stddev = 0.216 ms
tps = 391012.743072 (including connections establishing)
tps = 391175.983419 (excluding connections establishing)
script statistics:
 - statement latencies in milliseconds:
         0.163  update test set crt_time=now() where id=1 and pg_try_advisory_xact_lock(1);
At this time, the database host still has 66.2% idle CPU resources available.

top - 13:12:43 up 51 days, 18:41,  2 users,  load average: 1.12, 0.97, 0.78
Tasks: 1463 total,  28 running, 1435 sleeping,   0 stopped,   0 zombie
Cpu(s): 24.5%us,  9.3%sy,  0.0%ni, 66.2%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Mem:  529321832k total, 235226420k used, 294095412k free,   903076k buffers
Swap:        0k total,        0k used,        0k free, 62067636k cached

Comparison with traditional examples
The traditional solution to eliminate wait is through select for update nowait statement.
begin;
select 1 from tbl where id=pk for update nowait;  --  If the user cannot get the lock instantly, an error is returned. The transaction is rolled back.
update tbl set xxx=xxx,upd_cnt=upd_cnt+1 where id=pk and upd_cnt+1<=5;
end;

In PG, you can use the do statements to combine the above into a block for operation.
The traditional solution can enable the processing of 86,000 requests per second.
vi test.sql
do language plpgsql $$ declare begin with t as (select * from test where id=1 for update nowait) update test set crt_time=now() from t where t.id=test.id; exception when others then return; end; $$;

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 64 -j 64 -T 100

transaction type: ./test.sql
scaling factor: 1
query mode: prepared
number of clients: 64
number of threads: 64
duration: 100 s
number of transactions actually processed: 8591222
latency average = 0.744 ms
latency stddev = 0.713 ms
tps = 85888.823884 (including connections establishing)
tps = 85924.666940 (excluding connections establishing)
script statistics:
 - statement latencies in milliseconds:
         0.744  do language plpgsql $$ declare begin with t as (select * from test where id=1 for update nowait) update test set crt_time=now() from t where t.id=test.id; exception when others then return; end; $$;
And the CPU has 54.5% resources remained.

top - 13:13:48 up 51 days, 18:42,  2 users,  load average: 8.14, 2.69, 1.37
Tasks: 1464 total,  21 running, 1442 sleeping,   0 stopped,   1 zombie
Cpu(s): 41.7%us,  3.8%sy,  0.0%ni, 54.5%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Mem:  529321832k total, 235256052k used, 294065780k free,   903176k buffers
Swap:        0k total,        0k used,        0k free, 62068308k cached

Real deduction throughput of a single commodity
We see the query QPS is very impressive, but the real deduction throughput may not be that high of course, because some requests return before they get the lock. So we need to test the real deduction throughput of a single commodity.
postgres=# create table upd(id int primary key, cnt int8);
postgres=# insert into upd values(1,0);

vi t0.sql
update upd set cnt=cnt-1 where id=1 and pg_try_advisory_xact_lock(1);
\sleep 10 us
....
vi t7.sql
update upd set cnt=cnt-1 where id=1 and pg_try_advisory_xact_lock(1);
\sleep 80 us

pgbench -M prepared -n -r -P 1 -f t0.sql -f t1.sql -f t2.sql -f t3.sql -f t4.sql -f t5.sql -f t6.sql -f t7.sql -c 64 -j 64 -T 100

postgres=# select * from upd;
 id |   cnt  
----+---------
  1 | -611249
(1 row)

A single commodity is deducted for 6,112.49 times a second. Usually the products offered in flash sales won't have a high stock, mostly within 1,000 in quantity. Otherwise it won't be called a flash sale, and users just don't need to bother to join the flash sales.
So this value can fully meet the need in real world situations.
Real deduction throughput of all the commodities on the entire platform
We suppose there are a total of 10 million commodities on the entire platform. Test the overall deduction throughput using this method.
postgres=# create table upd(id int primary key, cnt int8);
postgres=# insert into upd select generate_series(1,10000000), 0;

vi test.sql
\set id random(1,10000000)
update upd set cnt=cnt-1 where id=:id and pg_try_advisory_xact_lock(:id);

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 64 -j 64 -T 100

postgres=# select sum(cnt) from upd;
    sum    
-----------
 -27233112
(1 row)

Check the count to get the real deduction situation. For the entire platform, around 272,331.12 commodities are deducted every second, that is, 270,000 products are sold every second.
Advantage of ad lock over other flash sales optimizations

Using the ad lock can minimize the CPU usage, and wait time. Seen from the test case of this article, the updates to a single record can reach 391,000 requests/second.
While this figure is only 86,000 requests/second in the traditional means.

Using the ad lock won't damage the ACID. A single request is a single transaction without affecting other transactions.
The merge optimization method actually damages the ACID. If the merge fails, it will leads to the failure of all the related requests.