Upgrade to Pro — share decks privately, control downloads, hide ads and more …

A Tour of PostgreSQL Concurrency Control

Luka Huang
August 18, 2019
150

A Tour of PostgreSQL Concurrency Control

Luka Huang

August 18, 2019
Tweet

Transcript

  1. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    ACID and Isolation levels • How MVCC works in PostgresQL • How tuples changed during CRUD • How snapshot isolation works • How MVCC works in MySQL • MySQL vs PosgreSQL 0VUMJOF
  2. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Atomicity • Consistency • Isolation • Durability "$*%
  3. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Atomicity • A transaction is inseperable – ”all or nothing” • Consistency • Isolation • Durability "$*%
  4. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Atomicity • Consistency • A transaction shall bring the database from one consistent state to another consistent state, even if its not necessarily consistent during the transaction. • Isolation • Durability "$*%
  5. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Atomicity • Consistency • Isolation • Transactions are not affected by changes done by concurrent transactions • Durability "$*%
  6. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Atomicity • Consistency • Isolation • Durability • When a transaction is COMMITED, the changes are permanent, even after a crash "$*%
  7. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 $PODVSSFODZ$POUSPM5FDIOJRVFT

    • Locking e.g. 2PL (Two-Phase Locking) • Optimistic Concurrency Control • MVCC (Multi-version Concurrency Control)
  8. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 $PODVSSFODZ$POUSPM5FDIOJRVFT

    • Locking e.g. 2PL (Two-Phase Locking) • Optimistic Concurrency Control • MVCC (Multi-version Concurrency Control)
  9. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 $PODVSSFODZ$POUSPM5FDIOJRVFT

    • Locking e.g. 2PL (Two-Phase Locking) • Optimistic Concurrency Control • MVCC (Multi-version Concurrency Control)
  10. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Locking e.g. 2PL (Two-Phase Locking) • Optimistic Concurrency Control • MVCC (Multi-version Concurrency Control) $PODVSSFODZ$POUSPM5FDIOJRVFT
  11. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    A type of MVCC • PostgreSQL • every writing operation create a new version of data • retain old version of data. • use visibility check rules to decide which data to show • MySQL、Oracle • Implement by rollback segments 4* 4OBQTIPU*TPMBUJPO
  12. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 -PSFNJQTVN

    ref: https://www.microsoft.com/en-us/research/wp-content/uploads/
  13. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 ref:

    https://www.microsoft.com/en-us/research/wp-content/uploads/
  14. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    P1 (Dirty Read) • P2 (Non-repeatable or Fuzzy Read) • P3 (Phantom Read) QIFOPNFOBPG*TPMBUJPO
  15. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 1

    %JSUZ3FBE ref: https://medium.com/getamis/database-transaction-isolation-
  16. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 1

    /POSFQFBUBCMF3FBE ref: https://medium.com/getamis/database-transaction-isolation-
  17. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 1

    1IBOUPN3FBE ref: https://medium.com/getamis/database-transaction-isolation-
  18. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Read Uncommitted • Read Committed • Repeatable Read • Serializable *TPMBUJPO-FWFMT
  19. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 5BCMF%BUB

    QBHF QBHF QBHF QBHF QBHF QBHF QBHF 5BCMFEBUBBOE1BHF 8kb
  20. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Sequential Scan • B-Tree Index scan "DDFTTNFUIPET
  21. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 #5SFF*OEFY4DBO

    ref: https://www.pgcon.org/2016/schedule/attachments/423_Btree
  22. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    t_xmin - 保存插入此 tuple 的 txid。 • t_xmax - 更新或刪除 tuple 的 txid。如果 沒更新、刪除的話就設為 0 • t_cid (command_id) - ⽬前執⾏了多少命 令。 • t_ctid - ⾃⼰所在的 tuple (tid)。 'JFMETJO)FBQ5VQMF
  23. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 CREATE

    TABLE p_table (data text) ; INSERT INTO p_table ( data ) VALUES ( 'Jack' ) ; INSERT INTO p_table ( data ) VALUES ( 'Peter' ) ; INSERT INTO p_table ( data ) VALUES ( 'Luka' ) ; SELECT * FROM p_table; )FBQ5VQMF
  24. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 (FUUVQMFJOGPSNBUJPO

    SELECT lp as tuple, t_xmin, t_xmax, t_ fi eld3 as t_cid, t_cti d FROM heap_page_items(get_raw_page(p_table', 0));
  25. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 INSERT

    INTO p_table ( data ) VALUES ( 'Apple' ) ; *OTFSU
  26. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 BEGIN

    ; INSERT INTO p_table ( data ) VALUES ( 'Apple' ) ; SELECT txid_current() ; END ; *OTFSU
  27. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 BEGIN

    ; INSERT INTO p_table ( data ) VALUES ( 'Apple' ) ; SELECT txid_current(); => txid: 62 7 END ; *OTFSU
  28. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Active Transaction ID • In progress or not started • It’s invisible • Inactive Transaction ID • committed or aborted • It’s visible if committed "DUJWF*OBDUJWF5SBOTBDUJPO*%
  29. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 4OBQTIPU

    • xmin • if txid < xmin, transaction is inactive • xmax • if txid >= xmax transaction is active. • xip_list • transactions that transaction id in xip_list are active.
  30. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    ABORTED • IN PROGRESS • COMMITTED U@YNJO
  31. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 /*

    t_xmin status = ABORTED */ Rule 1: IF t_xmin status is 'ABORTED' THE N RETURN 'Invisible' END IF "#035&% ref: http://www.interdb.jp/pg/
  32. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 /*

    t_xmin status = IN_PROGRESS */ IF t_xmin status is 'IN_PROGRESS' THE N IF t_xmin = current_txid THE N Rule 2: IF t_xmax = INVALID THE N RETURN 'Visible' Rule 3: ELSE /* this tuple has been deleted or updated by the current transaction itself. */ RETURN 'Invisible' END I F Rule 4: ELSE /* t_xmin ≠ current_txid */ RETURN 'Invisible' END I F END IF */@130(3&44 ref: http://www.interdb.jp/pg/
  33. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 /*

    t_xmin status = COMMITTED */ IF t_xmin status is 'COMMITTED' THE N Rule 5: IF t_xmin is active in the obtained transaction snapshot THE N RETURN 'Invisible' Rule 6: ELSE IF t_xmax = INVALID OR status of t_xmax is 'ABORTED' THE N RETURN 'Visible' ELSE IF t_xmax status is 'IN_PROGRESS' THE N Rule 7: IF t_xmax = current_txid THE N RETURN 'Invisible' Rule 8: ELSE /* t_xmax ≠ current_txid */ RETURN 'Visible' END I F ELSE IF t_xmax status is 'COMMITTED' THE N Rule 9: IF t_xmax is active in the obtained transaction snapshot THE N RETURN 'Visible' Rule 10: ELS E RETURN 'Invisible' END I F $0..*55&% ref: http://www.interdb.jp/pg/
  34. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Rule6(Tuple_1) 㱺 Status(t_xmin:199) = COMMITTED ∧ t_xmax = INVALID 㱺 Visible 5 ref: http://www.interdb.jp/pg/ ref: http://www.interdb.jp/pg/
  35. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Rule7(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = IN_PROGRESS ∧ t_xmax:200 = current_txid:200 㱺 Invisible 5  ref: http://www.interdb.jp/pg/ ref: http://www.interdb.jp/pg/
  36. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Rule2(Tuple_2): Status(t_xmin:200) = IN_PROGRESS ∧ t_xmin:200 = current_txid:200 ∧ t_xmax = INVAILD 㱺 Visible 5  ref: http://www.interdb.jp/pg/
  37. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Storage Engine - InnoDB only • Isolation level • READ COMMITTED • REPEATABLE READ .7$$JO.Z42-
  38. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    DB_TRX_ID • DB_ROLL_PTR .7$$JO.Z42-*OOP%# ref: https://zhuanlan.zhihu.com/p/40208895
  39. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    DB_TRX_ID • The last transaction that update this record • DB_ROLL_PTR .7$$JO.Z42-*OOP%# ref: https://zhuanlan.zhihu.com/p/40208895
  40. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    DB_TRX_ID • The last transaction that update this record • DB_ROLL_PTR • rollback segment (undo log) .7$$JO.Z42-*OOP%# ref: https://zhuanlan.zhihu.com/p/40208895
  41. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 6OEP-PH

    • Automaticity • Copy data to another place before updating data . • The place is called undo log. ref: https://liuzhengyang.github.io/2017/04/18/innodb-mvcc/
  42. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 3PMMCBDL4FHNFOU

    ref: http://leviathan.vip/2019/02/14/InnoDB%E7%9A%84%E4%BA%8B%E5%8A%A1%E5%88%86%E6%9E%90- undo slot rollback segment undo log tablespace
  43. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 1.

    rseg_id - get rollback tablespace id 2. get data from undo log 4UFQTPG3PMM1PJOUFS /** Decodes a roll pointer. */ inline void trx_undo_decode_roll_ptr ( roll_ptr_t roll_ptr, /*!< in: roll pointer */ ibool *is_insert, /*!< out: TRUE if insert undo log */ ulint *rseg_id, /*!< out: rollback segment id */ page_no_t *page_no, /*!< out: page number */ ulint *offset) /*!< out: offset of the und o entry within page */ { ut_ad(roll_ptr < (1ULL << 56)) ; *offset = (ulint)roll_ptr & 0xFFFF ; roll_ptr >>= 16 ; *page_no = (ulint)roll_ptr & 0xFFFFFFFF ; roll_ptr >>= 32 ; *rseg_id = (ulint)roll_ptr & 0x7F ; roll_ptr >>= 7 ; *is_insert = (ibool)roll_ptr; /* TRUE==1 */ }
  44. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    Uncommited transacftions • If transactions is commited, system will remove transaction id from trx_sys list. USY@TZTUSBOTBDUJPOTMJTU ref: https://liuzhengyang.github.io/2017/04/18/innodb-mvcc/
  45. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 •

    low_trx_id • up_trx_id • trx_ids 3FBEWJFX ref: https://liuzhengyang.github.io/2017/04/18/innodb-mvcc/
  46. A Tour of PostgreSQL Concurrency Control, Luka Huang@COSCUP 2019 ref:

    https://liuzhengyang.github.io/2017/04/18/innodb-mvcc/ .7$$JO.Z42-