WiredTiger MVCC (P2/4): Update chain và history store

Ở phần trước: một lệnh ghi đi qua bốn tầng trước khi chạm dữ liệu, và các timestamp quyết định version nào một transaction được thấy.

Cần đọc trước: Bốn tầng transaction và timestamp
Dẫn tới: Ba lab về snapshot bị giữ

Update chain: các version của một key trên page

[tài liệu] Trên một leaf page đang ở trong cache, khi một entry bị sửa lần đầu, WiredTiger gắn thêm một cấu trúc theo dõi thay đổi. Với mỗi key có một update chain: danh sách liên kết, version mới nhất ở đầu. Một update cũng có thể là tombstone (đánh dấu xoá). Tài liệu mô tả việc đọc một key: đi qua update chain trong bộ nhớ cho tới khi gặp version thấy được; nếu không có, xem bản trên đĩa (version đã được chọn ghi xuống ở lần reconciliation gần nhất); nếu vẫn chưa thấy được, tìm trong history store.

Page trong cache (leaf page), key = RecordId 184

   đầu chain                                                       cuối chain
   │                                                                      │
   ▼                                                                      ▼
 [ v5: balance 345 ]──▶[ v4: balance 336 ]──▶[ v3: balance 317 ]──▶[ v2: ... ]
   txn 91, ts 120        txn 88, ts 110        txn 70, ts 90         ...
   commit rồi            commit rồi            commit rồi
                                                  ▲
                         reader có read timestamp = 100  ──▶ đi từ đầu, bỏ v5, v4 (ts > 100),
                                                              dừng ở v3
        reader mới (read timestamp ≥ 120)  ──▶ dừng ngay ở v5

   không thấy trong chain?  ──▶ bản trên đĩa (file .wt)  ──▶ history store

Hai hệ quả ngay:

Người đọc mới thường chỉ đụng đầu chain, người đọc có snapshot cũ phải đi sâu hơn. Chain càng dài thì người đọc cũ càng tốn thêm bước đi qua chain (Lab 2 đo điều này, và cho thấy nó khó tách ra).
Người đọc và người ghi không chờ nhau. Người ghi thêm vào đầu chain, người đọc đi từ đầu xuống và bỏ qua những gì không thấy được. Ở bài Isolation & Snapshot lab đo: một transaction giữ snapshot mở, người khác ghi 20 lần, p50 1,00 ms và không lần nào phải chờ.

Vì sao đơn vị xung đột là document

Hứa ở bài Write Conflicts, Retry & Idempotency. Phần "cơ chế" nằm ở đây, và nó rất ngắn.

[tài liệu] Tài liệu timestamp của WiredTiger nói: một transaction đang thử ghi sẽ gặp xung đột khi trên update chain có update mà nó không thấy được; việc ghi đó trả WT_ROLLBACK. Mongod dịch lỗi đó thành WriteConflict. Chain thuộc về một key của B-tree; với collection, key là RecordId, mỗi RecordId là một document. WiredTiger không biết document có field a hay b: nó chỉ thấy "một giá trị", và update mới thêm vào chain của giá trị đó. Hai lệnh sửa hai field khác nhau của cùng một document vẫn cùng nhắm vào một chain.

[quan sát] Script e8-conflict.js, hai session A và B, mỗi bên một transaction snapshot đã đọc _id: 1 (e8-conflict.out):

Trường hợp	A	B	`update conflicts` của WiredTiger	`metrics.operation.writeConflicts`
1. cùng một document, A `$set` field `a`, B `$set` field `b`	ok	WriteConflict (112)	+1	+1
2. hai document khác nhau (`_id` 1 và 2)	ok	ok	0	0
3. một lệnh ghi thường commit sau snapshot của A, rồi A ghi cùng document	WriteConflict, kèm error label `TransientTransactionError`		+1	+1

Trường hợp 1 là câu trả lời: field khác nhau không cứu được, vì xung đột được xét theo key của B-tree, tức là theo cả document. Trường hợp 3 là first-writer-wins của bài Isolation & Snapshot nhìn ở tầng thấp: update đã commit sau snapshot của A nằm trên chain và A không thấy nó, nên A không được thêm update của mình lên trên. Ở các bài trước, bộ đếm writeConflicts tăng cả khi ứng dụng không thấy lỗi nào (lệnh ghi lẻ được server tự thử lại); xung đột trên chain chính là thứ nó đếm.

Những thứ thật sự chặn nhau (lock, latch, ticket) thuộc bài Concurrency; chain chỉ quyết định ai thấy gì và ai xung đột với ai.

Update chain lưu gì: nguyên giá trị hay delta

Bài Document Model và bài Schema Patterns & Evolution nói WiredTiger có thể giữ một thay đổi nhỏ dưới dạng delta, còn oplog ghi một diff. Đây là phần đo được, nhưng [chi tiết cài đặt]: manual không cam kết dạng lưu này và nó có thể đổi giữa các bản MongoDB.

[quan sát] e4-delta.js: một document 1 MB trong collection mới, một snapshot được giữ mở để không version nào bị xoá, 50 update, ba vòng xen kẽ giữa hai kiểu: $inc một field 4 byte và replaceOne bằng cả document 1 MB. Dữ liệu từ e4-delta.out, e4-delta.derived:

Sau 50 update	`$inc` (3 vòng)	`replaceOne` (3 vòng)
`bytes allocated for updates` tăng thêm trong cache	0,0 / 0,0 / 0,1 MB	15,3 / 3,1 / −3,1 MB (nhiễu: xem dưới)
dirty bytes tăng thêm	2,1 / 6,2 / 4,2 MB	27,9 / 20,7 / 20,6 MB
thời gian 50 lệnh	37 đến 44 ms	976 đến 1.296 ms (gồm gửi 1 MB mỗi lệnh)
oplog entry của lệnh cuối	318 byte: `{ $v: 2, diff: { u: { n: 50 } } }`	1.000.311 byte: cả document

Trong cache, $inc trên document 1 MB gần như không tốn thêm byte cho update (≤ 0,1 MB cho 50 version, dưới 2 KB mỗi version), còn replaceOne tạo ra hàng MB dirty. Số âm ở cột replaceOne là do bộ đếm này của toàn server và còn đổi theo các thread nền; chỉ nên tin thứ tự độ lớn. Ba lần chạy trước của script bị lỗi hoặc bị checkpoint làm nhiễu, nên không dùng ở đây.
[tài liệu + quan sát] Khớp với việc WiredTiger cho sửa một phần giá trị (update kiểu modify) thay vì ghi lại cả giá trị. [suy luận] Mongod có một ngưỡng kích thước nào đó quyết định khi nào dùng nó: ở Lab 1 của phần sau (Ba lab về snapshot bị giữ) (document khoảng 1,1 KB), bytes allocated for updates tăng khoảng 10 đến 11 MB cho 10.000 $inc đầu, tức khoảng 1,1 KB mỗi update, cỡ một bản đầy đủ. Tôi không tìm thấy ngưỡng trong tài liệu và không dò nó.
Oplog là một thứ khác. Diff $v: 2 (318 byte) là thứ replication gửi cho secondary; delta trong update chain nằm trong cache. Cùng ý tưởng "chỉ ghi phần đổi", nhưng hai nơi, hai định dạng. Oplog không phải nơi lưu các version cũ của document: nó chỉ để secondary phát lại, trong một collection bị giới hạn kích thước (bài Replica Set & Oplog).
[tài liệu] Dù chain lưu thế nào, lúc ghi xuống reconciliation vẫn viết cả page ra block mới; bài Schema Patterns & Evolution đã đo $inc trên document 10,9 MB (11,8 MB dirty, checkpoint ghi 10.920.698 byte). Bài này bổ sung nửa còn lại: trước khi ghi xuống, chain không lớn theo kích thước document. [quan sát] History store thì không thấy lợi thế đó: tới sau checkpoint, mỗi vòng 50 lệnh của cả hai kiểu thêm đúng 151 entry vào history store, file lớn thêm 4,8 MB ($inc) và 2,9 đến 5,7 MB (replaceOne). Tôi không giải thích được con số 151.

Từ page trong cache tới history store

Update chain sống trong cache. Nó được ghi xuống đĩa trong hai trường hợp: cache cần chỗ (eviction: bỏ một page khỏi cache để lấy chỗ), hoặc checkpoint cần ghi thay đổi xuống đĩa. Cả hai đều chạy reconciliation trên page đang bị sửa (bài WiredTiger & Compression); khi đó câu hỏi là "version nào đi đâu".

[tài liệu] Tài liệu history store của WiredTiger 12.0.0 trả lời:

Khi reconcile một page đang bị sửa, WiredTiger xem update chain và chọn update đã commit mới nhất làm giá trị trên đĩa. Mọi update cũ hơn được thêm vào history store, miễn là chưa obsolete.
Chỉ version mới nhất của key nằm trong file của bảng; các version cũ nằm trong một bảng history store duy nhất cho mọi bảng của người dùng (WiredTigerHS.wt).
Mỗi bản ghi trong history store có key gồm btree id của bảng, key của bản ghi, start timestamp, một bộ đếm và value gồm stop timestamp, durable timestamp, kiểu update, giá trị. Stop timestamp là lúc version đó không còn thấy được nữa (bị version mới hơn thay hoặc bị xoá). Khoảng từ start đến stop là nơi một reader có read timestamp rơi vào thì thấy version này.
Obsolete nghĩa là stop timestamp của version đã nhỏ hơn oldest timestamp và mọi transaction đang chạy đều thấy việc nó bị thay: không reader nào còn cần. Khi reconcile một page của history store, các bản ghi obsolete bị bỏ khỏi page mới; page chỉ còn bản ghi obsolete thì có thể xoá hẳn.
Lúc đọc: chain trước, rồi bản trên đĩa, rồi history store; trong history store WiredTiger bắt đầu từ version mới nhất của key và đi lùi cho tới version thấy được.

update chain trên page          reconciliation                    trên đĩa
────────────────────────        ───────────────                   ─────────────────────────────────
v5 (commit, ts 120) ────────▶   chọn v5 làm bản trên đĩa  ──────▶  file .wt:           v5
v4 (ts 110)                     v4, v3, v2 còn có thể cần?
v3 (ts 90)          ────────▶   có → thêm vào history store ────▶  WiredTigerHS.wt:    v4, v3, v2
v2 (ts 70)
v1 (ts 60)                      bị v2 thay ở ts 70, trước oldest timestamp:
                                obsolete → bỏ, không ghi đâu cả

[chi tiết cài đặt] Có hai dạng entry trong history store: bản đầy đủ và bản reverse modify. Lab đếm được cả hai (bảng dưới); tôi suy ra tên từ bộ đếm, không từ tài liệu.

Quan sát từ `serverStatus`

Các trường dưới đây không có trong trang manual của serverStatus (trang đó không có chuỗi "history store"); chúng là thống kê của WiredTiger đi qua mongod, nên tên có thể đổi giữa các phiên bản. Danh sách lấy từ e0-probe.out (8.3.11):

Trường (trong `serverStatus().wiredTiger`)	Đo gì
`historyStorageStats["block-manager"]["file size in bytes"]`	kích thước `WiredTigerHS.wt` theo WiredTiger
`historyStorageStats["block-manager"]["file bytes available for reuse"]`	phần của file đã trống, dùng lại được nhưng file chưa nhỏ đi
`cache["history store table insert calls"]`	số lần ghi một version vào history store (cộng dồn)
`cache["the number of times full update inserted to history store"]`, `cache["the number of times reverse modify inserted to history store"]`	phần của số trên là bản đầy đủ và bản reverse modify
`cache["page written requiring history store records"]`	số page được ghi mà có kèm bản ghi history store
`cache["bytes allocated for updates"]`, `cache["tracked dirty bytes in the cache"]`	bộ nhớ của các update và của dirty page trong cache
`transaction["transaction global oldest / stable / pinned / newest timestamp"]`	các timestamp ở phần trước (Bốn tầng transaction và timestamp), dạng số 64 bit
`transaction["transaction read timestamp of the oldest active reader"]`	read timestamp của reader cũ nhất (0 nếu không có)
`transaction["update conflicts"]`	số lần ghi gặp xung đột trên update chain

Cột mốc: Bạn đã có thể chỉ ra update chain nằm ở đâu, nói vì sao hai field khác nhau vẫn xung đột, và theo một version cũ xuống history store. Tiếp theo: Ba lab về snapshot bị giữ.

Hỏi & đáp

Hai transaction cùng đọc document { _id: 1, a: 0, b: 0 }. A chạy $set: { a: 1 } trước, rồi B chạy $set: { b: 1 }, chưa bên nào commit. Điều gì xảy ra ở lab?

Cả hai thành công, vì hai field khác nhau không đụng nhau và MVCC chỉ xung đột khi cùng field
WiredTiger không biết field. Nó chỉ thấy một key (RecordId) với một update chain. Lab: B nhận WriteConflict (112), update conflicts +1. Xem mục "Vì sao đơn vị xung đột là document".
Cả hai bị WriteConflict, vì cả hai cùng thấy bản cũ
Chỉ bên ghi sau bị từ chối: A đã thêm update chưa commit vào chain, B không thấy nó, nên B không được thêm update lên trên. A thành công. Xem bảng ở mục "Vì sao đơn vị xung đột là document".
B bị WriteConflict, vì cùng document nghĩa là cùng update chain
Trường hợp 1 của lab: A ok, B WriteConflict (112), update conflicts +1 và writeConflicts +1. Hai document khác nhau (trường hợp 2) thì cả hai đều ok. Xem mục "Vì sao đơn vị xung đột là document".
B chờ A commit rồi chạy tiếp, giống UPDATE ở PostgreSQL Read Committed
MongoDB huỷ ngay thay vì chờ; đó là khác biệt đã đo ở bài Isolation & Snapshot. Xem mục "Vì sao đơn vị xung đột là document".

Một document 1 MB nhận $inc: { n: 1 }, 50 lần. Lab so với replaceOne cả document. Điều nào đúng?

$inc luôn lưu bản đầy đủ của document 1 MB trong chain, nhưng nén nên nhỏ
Lab: 50 $inc làm bytes allocated for updates tăng ≤ 0,1 MB, trong khi replaceOne tạo ra hàng MB dirty. Chain không lưu 1 MB mỗi version. Xem bảng ở mục "Update chain lưu gì".
Chain giữ $inc dưới dạng phần thay đổi nên gần như không tốn byte, còn oplog ghi một diff riêng
Lab: $inc ≤ 0,1 MB, oplog 318 byte; replaceOne hàng MB, oplog 1.000.311 byte; ở document 1,1 KB mỗi update tốn khoảng 1,1 KB, tức chain giữ bản đầy đủ. Đây là chi tiết cài đặt, manual không cam kết. Xem mục "Update chain lưu gì".
Oplog entry của $inc là 318 byte, nên mỗi version trong update chain cũng đúng 318 byte
Oplog và update chain là hai thứ khác nhau, định dạng khác nhau, dù cùng ý tưởng lưu phần khác biệt. Lab chỉ đo thứ tự độ lớn của chain (≤ 0,1 MB cho 50 version). Xem mục "Update chain lưu gì".
Oplog lưu các version cũ của document, nên có thể dùng nó để đọc document ở thời điểm cũ
Oplog chỉ để secondary phát lại và có giới hạn kích thước; version đọc được nằm trong update chain và history store, không có API công khai. Xem mục "Update chain lưu gì", ý 3.

Document w0007 có balance 316. Transaction A mở snapshot và đọc nó. Rồi B commit ba lệnh $inc liên tiếp lên chính document đó. Trên page trong cache, A và người đọc mới nhìn vào đâu?

Cả hai đọc cùng một giá trị trên page, và B phải chờ A đóng transaction mới ghi được
Đó là mô hình locking, không phải MVCC. B không chờ: nó thêm version vào đầu update chain, A không bị chặn và cũng không thấy chúng (lab ở bài Isolation: 20 lệnh ghi, p50 1,00 ms, không lần nào phải chờ). Xem mục "Update chain: các version của một key trên page".
Một update chain: người đọc mới dừng ở đầu chain, A đi xuống tới version nó được phép thấy
Mỗi lệnh ghi thêm một version vào đầu chain; A có read timestamp và snapshot cũ nên bỏ qua ba version mới, còn người đọc mới dừng ngay ở đầu. Lab 1 cho thấy cả hai: sau 300.000 update, snapshot cũ vẫn đọc tổng n = 0, người đọc mới đọc 300.000. Xem mục "Update chain: các version của một key trên page".
Hai bản sao của cả document, một cho A, một cho người khác, tạo lúc A mở snapshot
Snapshot không chép dữ liệu. Nó chỉ là danh sách transaction đang chạy cộng read timestamp; các version đã nằm sẵn trong chain. Xem Bốn tầng transaction.
Bản trong file .wt trên đĩa cho A, bản trong cache cho người đọc mới
Bản trên đĩa chỉ là nơi dừng chân thứ hai (sau chain) và history store là thứ ba; thứ tự tìm là chain, bản trên đĩa, history store, cho mọi reader. Xem mục "Update chain: các version của một key trên page".