标簽
PostgreSQL , 大爆炸 , 沖突 , 打車集中 , 區域集中 , 鎖沖突 , adlock
https://github.com/digoal/blog/blob/master/201804/20180416_02.md#%E8%83%8C%E6%99%AF 背景
在打車高峰時期，通常會出現某個區域打車的人特别多的情況，比如在下班時，寫字樓。比如在演唱會結束時，演唱會現場。
這個場景有一個特點，同一個點送出請求，按距離搜尋最近的車，然後鎖定車輛。
在資料庫中，如果大家都這麼操作，會帶來鎖沖突的問題。我在上一篇文檔中，介紹了adlock，可以大幅提高吞吐，但是還有一個隐藏的可以提升的點（而且可以提升非常多），如果所有人都是從同一個位置發起的鎖定附近車輛請求，那麼會出現備援掃描+FILTER的情況。（因為A鎖定了第一輛車後，B必須跳過第一輛車去鎖定第二輛附近的車，然後是C必須跳過最近的前面2輛車，以此類推）并發越高，跳過的車輛越多。
《滴滴打車派單系統思考 資料庫設計與實作 - 每月投入6140元, 1天最多可盈利117億 -_-!》怎麼解決這個問題呢？
未來優化3：對于同一個時刻，同一個地點，有多人打車時，如果都按同樣的就近選擇CAR的規則，會導緻同一輛CAR被多次挑選中，本文使用了ADVISORY LOCK來避免行鎖沖突。但是依舊有更好的優化，因為這種方法雖然沒有了鎖沖突，但是掃描依舊是從近到遠的，是以
可能并發時，一些會話存在多行掃描才找到沒有被鎖定的行。 有一種方法，比如，類似組送出，對同一個地點同時打車的多人，一次取多輛CAR，在程式中配置設定給不同的人。 還有一種方法，需要資料庫内來實作，給一個離散因子，每次擷取到的可能不是最近的CAR
，滿足多少米内的周邊的CARs，随機挑選，但是這個随機挑選必須在INDEX中完成，必須保證在庫中的index scan, heap scan都隻掃一條。（類似索引的位點随機掃）
https://github.com/digoal/blog/blob/master/201804/20180416_02.md#%E4%BB%8E%E5%AE%87%E5%AE%99%E5%A4%A7%E7%88%86%E7%82%B8%E5%BC%80%E5%A7%8B 從宇宙大爆炸開始
https://github.com/digoal/blog/blob/master/201804/20180416_02_pic_001.jpg宇宙大爆炸理論是說最開始宇宙是一個點，大爆炸開始後，一個點逐漸擴散，形成了現在的宇宙。
滴滴打車的場景與之類似，打車高峰時，一個寫字樓的人很多，集中在一個點，車輛在外圍或附近，前面講了如果大家都從這個點去計算與車輛的距離，對所有人來說，最近的車輛都是同一輛車，是以存在沖突的問題。
https://github.com/digoal/blog/blob/master/201804/20180416_02_pic_002.jpg思路是什麼？
把集中在寫字樓一個位置的點打散，在計算離人最近的車輛時，就能夠盡可能的避免沖突，進而減少filter，提高性能，提高吞吐。
https://github.com/digoal/blog/blob/master/201804/20180416_02.md#%E4%BE%8B%E5%AD%90 例子
本文先舉一個例子，空間資料的例子與此類似(無非就是X和Y軸都給定一個離散範圍，進行離散)，下一篇文檔再介紹。
例如我們有1000萬條記錄，ID為PK，如果需求是找出與某個輸入值最近的ID，并鎖定它，如果它已被鎖定，則鎖定下一個與輸入值最近的ID。
例如輸入值為50，
優先鎖定50，如果50已經被其他會話鎖定了，則鎖定49和51，以此類推。
1、建立測試表
postgres=# create table a(id int primary key, info text, crt_time timestamp);
CREATE TABLE
2、寫入1000萬測試資料
postgres=# insert into a select generate_series(1,10000000), 'test', now();
3、建立GIST索引，支援距離搜尋操作符
postgres=# create extension btree_gist;
CREATE EXTENSION
postgres=# create index idx_a_1 on a using gist(id);
建立一個測試腳本，模拟高峰期打車的情況，（輸入同一個點，去鎖定離他最近的點，如果離它最近的點已經被鎖定，則跳過）。我們這裡同樣使用pg_try_advisory_xact_lock()來實作跳過已經被鎖定的記錄。
vi test.sql
select * from a where pg_try_advisory_xact_lock(id) order by id <-> 5000000 for update limit 1;
開啟壓測，可以達到約4.9萬TPS
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 56 -j 56 -T 120
progress: 3.0 s, 45775.8 tps, lat 1.224 ms stddev 0.828
progress: 4.0 s, 45571.5 tps, lat 1.229 ms stddev 0.826
progress: 5.0 s, 49345.6 tps, lat 1.135 ms stddev 0.747
progress: 6.0 s, 48948.0 tps, lat 1.144 ms stddev 0.856
progress: 7.0 s, 49578.2 tps, lat 1.129 ms stddev 0.758
https://github.com/digoal/blog/blob/master/201804/20180416_02.md#%E5%88%86%E6%9E%90%E5%8F%AF%E4%BC%98%E5%8C%96%E7%9A%84%E7%A9%BA%E9%97%B4filter 分析可優化的空間，filter
前面介紹了，并發的從同一點去搜尋附近的點，并鎖定它，存在一個問題，（因為A鎖定了第一輛車後，B必須跳過第一輛車去鎖定第二輛附近的車，然後是C必須跳過最近的前面2輛車，以此類推）并發越高，跳過的車輛越多。
通過下面的SQL可以觀察到這個現象。
1、會話A
postgres=# begin;
BEGIN
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from a where pg_try_advisory_xact_lock(id) order by id <-> (5000000-500000+100) for update limit 1;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.42..0.54 rows=1 width=27) (actual time=0.096..0.097 rows=1 loops=1)
Output: id, info, crt_time, ((id <-> 4500100)), ctid
Buffers: shared hit=5
-> LockRows (cost=0.42..397168.88 rows=3333333 width=27) (actual time=0.095..0.095 rows=1 loops=1)
Output: id, info, crt_time, ((id <-> 4500100)), ctid
Buffers: shared hit=5
-> Index Scan using idx_a_1 on public.a (cost=0.42..363835.55 rows=3333333 width=27) (actual time=0.092..0.092 rows=1 loops=1)
Output: id, info, crt_time, (id <-> 4500100), ctid
Order By: (a.id <-> 4500100)
Filter: pg_try_advisory_xact_lock((a.id)::bigint)
Buffers: shared hit=4
Planning time: 0.111 ms
Execution time: 0.135 ms
(13 rows)
2、會話B，在會話A沒有釋放鎖之前，從同一個點發起請求，鎖定附近的點。
Rows Removed by Filter: 1
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from a where pg_try_advisory_xact_lock(id) order by id <-> (5000000-500000+100) for update limit 1;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.42..0.54 rows=1 width=27) (actual time=0.128..0.128 rows=1 loops=1)
Output: id, info, crt_time, ((id <-> 4500100)), ctid
Buffers: shared hit=5
-> LockRows (cost=0.42..397168.88 rows=3333333 width=27) (actual time=0.127..0.127 rows=1 loops=1)
Output: id, info, crt_time, ((id <-> 4500100)), ctid
Buffers: shared hit=5
-> Index Scan using idx_a_1 on public.a (cost=0.42..363835.55 rows=3333333 width=27) (actual time=0.114..0.114 rows=1 loops=1)
Output: id, info, crt_time, (id <-> 4500100), ctid
Order By: (a.id <-> 4500100)
Filter: pg_try_advisory_xact_lock((a.id)::bigint)
Rows Removed by Filter: 1
Buffers: shared hit=4
Planning time: 0.112 ms
Execution time: 0.168 ms
(14 rows)
可以看到，發生了FILTER，因為按距離來說，4500100才是需要被傳回的，然而它已經被鎖了，是以會跳過它，找到下一個可以鎖的點。發生了一條FILTER。
并發越多，rows removed by filter會越多，因為都是被鎖定過的。造成性能影響。
https://github.com/digoal/blog/blob/master/201804/20180416_02.md#%E4%BC%98%E5%8C%96 優化
把一個點分散，例如我們把集中的點，打散到方圓1公裡的平面上。（也就是說在搜尋最近的車輛時，并不是拿你目前的定位來計算與車輛的距離。而是拿一個以你目前位置為中心，方圓一公裡内的“随機點”來尋找這個點最近的車輛。）
對于本例，我們設定一個範圍值，比如把點打散到上下5千以内的一個随機點，再求離他最近的點，并鎖定。
vi test.sql
\set seed random(1,5000)
select * from a where pg_try_advisory_xact_lock(id) order by id <-> (5000000+2500-:seed) for update limit 1;
壓測結果
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 56 -j 56 -T 120
progress: 5.0 s, 150380.9 tps, lat 0.372 ms stddev 0.165
progress: 6.0 s, 151711.9 tps, lat 0.369 ms stddev 0.168
progress: 7.0 s, 152098.8 tps, lat 0.368 ms stddev 0.154
progress: 8.0 s, 152003.3 tps, lat 0.368 ms stddev 0.156
progress: 9.0 s, 152421.4 tps, lat 0.367 ms stddev 0.154
progress: 10.0 s, 153108.7 tps, lat 0.366 ms stddev 0.148
progress: 11.0 s, 151427.8 tps, lat 0.370 ms stddev 0.156
https://github.com/digoal/blog/blob/master/201804/20180416_02.md#%E5%B0%8F%E7%BB%93 小結
使用把集中點，按一個範圍，随機打散的方法，鎖定附近點的處理吞吐提升了3倍多，從4.9萬提升到了15.1萬。
找到優化的方向，朝這個方向去優化，就會有性能的提升。這個思路對所有熱點消除的應用場景都有幫助。
![【MySQL資料庫】資料庫索引事務1.索引2.事務[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)