Hai người mua chiếc vé concert cuối cùng

01Còn đúng một vé

Trang web ghi còn 1 vé. Linh và Minh, hai người lạ ở hai thành phố, cùng bấm Mua trong vài mili giây. Cả hai request đều hỏi database còn bao nhiêu vé, cả hai nghe “một”, cả hai nghĩ “của mình”, và cả hai đều ghi lại một giao dịch bán. Nhà hát chứa cả đám đông, quầy vé chỉ có một chiếc vé, và giờ có hai người cầm email xác nhận cho nó.

Mình gặp đúng con bug này lần đầu như một câu chuyện, ở chương 7 của Designing Data-Intensive Applications (Martin Kleppmann, bản 1), rồi gặp lại ở dạng gần production trong bài đặt lịch khám, nơi một câu UPDATE có điều kiện đã kết thúc nó. Bài đó trả lời câu “gõ lệnh gì?”. Bài này trả lời câu mình đã bỏ qua: con bug này thật ra tên là gì, và database bảo đảm điều gì thì nó biến mất? Điều thú vị là cái tên không phải thuộc tính của con bug. Nó là thuộc tính của cách mình lưu vé.

người mua trên một vé

2 : 1

cách lưu dữ liệu, 2 tên lỗi khác nhau

2

cách chữa một bộ đếm

4

SQLSTATE bạn phải học cách retry

40001

02ACID, đọc phần chữ nhỏ

Ai cũng đọc thuộc ACID. Ít ai đọc kỹ từng chữ cái thật sự hứa điều gì, và Kleppmann nói thẳng rằng từ này mang nghĩa khác nhau ở các database khác nhau. Bốn ghi chú quan trọng với chuyện bán vé:

• Atomicity hoàn toàn không liên quan tới concurrency. Nó có nghĩa là khả năng hủy giữa chừng (abortability): transaction hỏng nửa đường thì mọi thứ nó đã ghi bị vứt đi. Chuyện hai thread đua nhau là việc của chữ cái kế tiếp.
• Consistency là trách nhiệm của ứng dụng, không phải của database. “Số vé đã bán không vượt sức chứa” là một invariant của ứng dụng. Database chỉ thi hành được những phần bạn khai báo (CHECK, UNIQUE, khóa ngoại); phần còn lại tùy bạn dùng transaction đúng hay không. Kleppmann nhắc lại câu đùa cũ rằng chữ C được thêm vào cho vừa acronym.
• Isolation là chữ cái cắn người. Trên lý thuyết nó nghĩa là các transaction chạy như thể lần lượt từng cái một (serializability). Trong thực tế, hầu hết database lặng lẽ mặc định ở mức yếu hơn, và các mức yếu đó có tên riêng và bug riêng.
• Durability nghĩa là dữ liệu đã commit sống sót sau sự cố, thường nhờ write-ahead log, đôi khi nhờ replication. Đó là một lời hứa có kèm xác suất, không phải tuyệt đối.

Còn một phân biệt nữa: ghi một object (tăng một bộ đếm) so với transaction nhiều object (chèn dòng vé và trừ kho và ghi đơn hàng). Database cho bạn bảo đảm atomic rẻ trên một dòng, và điều đó sẽ hóa ra là lối thoát cho bộ đếm.

03Transaction của bạn thực sự thấy gì

Hình dung cuốn sổ cái ở quầy vé, và anh nhân viên đọc to nó qua điện thoại. Ở read committed, mỗi câu anh đọc đều mới nhất: mỗi statement chỉ thấy dữ liệu đã commit trước lúc statement đó bắt đầu, và không bao giờ thấy phần việc dang dở của người khác (không có dirty read). Nhưng hai câu trong cùng một transaction có thể mâu thuẫn nhau, vì thế giới đã đổi giữa hai câu. Đó là mặc định của Postgres, và là lý do vì sao “đọc, nghĩ, rồi ghi” có một cái lỗ.

Ở snapshot isolation, anh nhân viên đưa bạn một bản photo cuốn sổ tại khoảnh khắc bạn bước vào, và bạn chỉ đọc bản photo cho tới khi rời đi. Database dựng điều này bằng MVCC (multi-version concurrency control): mỗi lần ghi tạo ra một phiên bản mới của dòng thay vì ghi đè bản cũ, và mỗi transaction chỉ thấy những phiên bản đã commit trước snapshot của nó. Khẩu hiệu trong sách là reader không chặn writer, writer không chặn reader. Postgres gọi mức này là REPEATABLE READ; MySQL cũng gọi thế, nhưng hai bên hành xử khác nhau theo những cách quan trọng ở dưới.

04Cách lưu A: một bộ đếm, và lost update

Cách lưu đầu tiên là cách một sinh viên sẽ viết: mỗi sự kiện một dòng với cột tickets_left. Mua vé nghĩa là “đọc, nếu lớn hơn 0 thì trừ một, ghi lại”. Đây là schema bạn dán thẳng vào psql được:

CREATE TABLE events (
  id           int PRIMARY KEY,
  name         text NOT NULL,
  tickets_left int  NOT NULL CHECK (tickets_left >= 0),
  version      int  NOT NULL DEFAULT 0
);
CREATE TABLE orders (
  id       bigserial PRIMARY KEY,
  event_id int NOT NULL REFERENCES events(id),
  buyer    text NOT NULL
);
INSERT INTO events VALUES (1, 'Opera Night', 1, 0);   -- exactly one ticket left

Handler ngây thơ làm ba bước trong ứng dụng: SELECT tickets_left, tính left - 1 bằng code, rồi UPDATE … SET tickets_left = 0. Đó là một chu trình read-modify-write, và timeline dưới đây cho thấy vì sao nó vỡ: người ghi thứ hai tính ra đáp án từ một giá trị đã hết đúng ngay trong lúc nó đang nghĩ.

Đây là lost update: hai chu trình read-modify-write trên cùng một giá trị, trong đó lần ghi sau lặng lẽ xóa lần ghi trước. Để ý nó không phải là gì: không phải dirty read (mọi thứ đọc được đều đã commit) và CHECK cũng không cứu được ta, vì 0 là con số hoàn toàn hợp lệ. Invariant vỡ trong đầu ứng dụng, không phải trong bảng.

Cách chữa 1: khóa dòng (phản xạ đầu tiên của mình)

Lần đầu mình giải bài này, đáp án của mình là đáp án gần như ai cũng đưa ra: khóa dòng đó lại để người mua thứ hai không chạm vào được cho tới khi người đầu xong. Đúng, và nó có tên là pessimistic lock. Trong SQL đó là SELECT … FOR UPDATE:

BEGIN;
SELECT tickets_left FROM events WHERE id = 1 FOR UPDATE;   -- second buyer waits here
-- app: if tickets_left > 0 ...
UPDATE events SET tickets_left = tickets_left - 1 WHERE id = 1;
INSERT INTO orders (event_id, buyer) VALUES (1, 'linh');
COMMIT;

Transaction của Minh bị chặn ở FOR UPDATE cho tới khi Linh commit, rồi đọc lại và thấy 0. Cái giá giống bài đặt lịch khám: lock được giữ suốt vòng gọi từ ứng dụng, nên trên một dòng nóng người mua xếp hàng và giữ connection của database. Dùng khi quyết định thật sự cần nhiều statement, đừng dùng cho một phép tăng đơn lẻ.

Cách chữa 2: gộp thành một statement atomic

Chu trình read-modify-write chỉ tồn tại vì phép tính nằm ở ứng dụng. Chuyển nó vào database là chu trình biến mất; update một dòng là atomic ở mọi engine:

UPDATE events
SET    tickets_left = tickets_left - 1
WHERE  id = 1 AND tickets_left > 0
RETURNING tickets_left;
-- 1 row  -> you got the ticket
-- 0 rows -> sold out, tell the user

Dưới READ COMMITTED của Postgres, người mua thứ hai chờ người đầu, rồi ==!đánh giá lại mệnh đề WHERE trên phiên bản mới của dòng==, thấy tickets_left = 0 và không update gì. Đây chính là mẹo conditional update mà bài đặt lịch khám dựa vào; mình không lặp lại lý lẽ ở đây. Thậm chí bỏ WHERE đi, ràng buộc CHECK cũng sẽ từ chối lần trừ thứ hai bằng một lỗi. Cách chữa tốt nhất cho bộ đếm, và không cần nâng isolation.

Cách chữa 3 và 4: compare-and-set, và cột version

Đôi khi giá trị mới không viết được thành phép tính: bạn tính nó từ cả một document hoặc từ nhiều trường. Khi đó dùng compare-and-set: chỉ ghi nếu dòng vẫn mang giá trị bạn đã đọc. Dạng chắc chắn hơn là optimistic locking, trong đó cột version đại diện cho câu “từ lúc mình xem tới giờ chưa có gì đổi”.

-- compare-and-set on the value itself
UPDATE events SET tickets_left = 0
WHERE  id = 1 AND tickets_left = 1;          -- 0 rows: someone changed it, re-read and retry

-- optimistic locking with a version column
SELECT tickets_left, version FROM events WHERE id = 1;      -- say (1, 7)
UPDATE events
SET    tickets_left = 0, version = version + 1
WHERE  id = 1 AND version = 7;               -- 0 rows: lost the race, retry or give up

Cột version tốt hơn việc so sánh giá trị khi giá trị có thể quay lại đúng cái bạn đã đọc (1, rồi 0, rồi hoàn vé thành 1: vấn đề “ABA”), và dùng được cho dòng có nhiều cột. Cái giá là bên thua phải retry trong code ứng dụng, rẻ khi xung đột hiếm và khổ sở khi bốn mươi người tranh một vé. Một lưu ý từ sách: compare-and-set chỉ an toàn nếu WHERE đọc dòng hiện tại chứ không phải một snapshot cũ. Postgres và InnoDB đều đọc dòng hiện tại cho UPDATE; engine khác thì nên kiểm tra trước khi tin.

Thêm một cách, miễn phí: để database tự phát hiện

Một số engine tự phát hiện lost update khi isolation dựa trên snapshot. Chạy đoạn này trong hai cửa sổ psql (S1 và S2) trên schema ở trên:

-- S1
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT tickets_left FROM events WHERE id = 1;            -- 1
-- S2
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT tickets_left FROM events WHERE id = 1;            -- 1
-- S1
UPDATE events SET tickets_left = 0 WHERE id = 1;
COMMIT;
-- S2
UPDATE events SET tickets_left = 0 WHERE id = 1;
-- ERROR:  could not serialize access due to concurrent update   (SQLSTATE 40001)
ROLLBACK;                                                 -- then retry the whole transaction

Postgres nhận ra dòng mà S2 muốn đổi đã bị một transaction commit sau snapshot của S2 sửa, và hủy S2. ==!MySQL InnoDB ở REPEATABLE READ thì không.== SELECT thường của nó đọc snapshot, nhưng UPDATE đọc dòng đã commit mới nhất, nên lệnh SET tickets_left = 0 thứ hai chạy qua và đơn bán của Linh bị ghi đè trong im lặng. Serializable của Oracle và snapshot isolation của SQL Server cũng tự phát hiện, theo sách. Bài học thực tế: cùng một đoạn code đúng ở engine này và sai ở engine kia, nên muốn đúng khi đổi engine hãy dùng cách chữa 2.

05Cách lưu B: mỗi vé một dòng, và write skew

Giờ đổi cách lưu, và xem con bug đổi tên. Hệ thống bán vé thật thường lưu mỗi vé đã bán thành một dòng riêng và coi sức chứa là một con số của sự kiện. Để bán, handler đếm số dòng đang có và chèn dòng mới nếu còn chỗ.

CREATE TABLE events_b (id int PRIMARY KEY, capacity int NOT NULL);
CREATE TABLE tickets (
  id       bigserial PRIMARY KEY,
  event_id int  NOT NULL REFERENCES events_b(id),
  buyer    text NOT NULL
);
INSERT INTO events_b VALUES (1, 1);                       -- capacity 1

-- the naive handler, run by Linh and by Minh at the same time:
BEGIN;
SELECT count(*) FROM tickets WHERE event_id = 1;          -- 0, so the app decides there is room
INSERT INTO tickets (event_id, buyer) VALUES (1, 'linh'); -- Minh inserts 'minh'
COMMIT;

Đây là write skew: hai transaction đọc cùng một tiền đề, rồi mỗi bên ghi một object khác nhau, và hai lần ghi cộng lại làm tiền đề sai. Ví dụ trong sách là hai bác sĩ trực cùng xin nghỉ vì mỗi người thấy “người kia vẫn đang trực”. Ở đây tiền đề là “count còn dưới capacity”. Nguyên nhân gốc cũng có tên riêng, là phantom: thứ mà tiền đề phụ thuộc vào (một dòng làm count thành 1) chưa tồn tại, nên chẳng có gì để lock hay gắn version.

So với cách lưu A. Ở đó hai người mua tranh nhau một dòng, nên row lock, kiểm tra version hay REPEATABLE READ của Postgres đều chặn được. Ở đây họ không bao giờ chạm vào cùng một dòng. Cách chữa đầu tiên của mình (“khóa dòng lại”) không có dòng nào để khóa, và Postgres thậm chí không cho thử: SELECT count(*) … FOR UPDATE bị từ chối vì không được lock cùng aggregate. (InnoDB chấp nhận câu này và gap lock của nó có thể chặn cuộc đua, nhưng thường dưới dạng lỗi deadlock chứ không phải một lần chờ gọn gàng.) Postgres ở REPEATABLE READ cũng để cả hai lệnh insert đi qua, vì nó chỉ kiểm tra xung đột ghi-ghi trên cùng một dòng.

Ba lối thoát khỏi write skew

1. Materialize xung đột. Cho phantom một thân xác. Lock một dòng mà mọi người mua vé của sự kiện này đều phải chạm vào, chẳng hạn chính dòng sự kiện:

BEGIN;                                                    -- READ COMMITTED (the default)
SELECT capacity FROM events_b WHERE id = 1 FOR UPDATE;    -- all buyers of event 1 line up here
SELECT count(*) FROM tickets WHERE event_id = 1;          -- fresh statement, sees the committed insert
INSERT INTO tickets (event_id, buyer)
SELECT 1, 'minh'
WHERE  (SELECT count(*) FROM tickets WHERE event_id = 1)
     < (SELECT capacity FROM events_b WHERE id = 1);
COMMIT;

Cách này chạy ở READ COMMITTED vì mỗi statement lấy snapshot mới sau khi có lock. Ở REPEATABLE READ nó không đủ: snapshot đã chốt ở statement đầu tiên, trước lúc chờ, và vì không ai sửa dòng cha nên Postgres không thấy xung đột nào để báo, count vẫn đọc ra 0. (Nếu mọi người mua còn UPDATE dòng cha, Postgres sẽ hủy bên thua bằng 40001: an toàn nhưng phải retry.) Nó cũng biến mọi người mua của một sự kiện thành một hàng đợi, tức lại là một dòng nóng. Nếu đằng nào cũng chịu serialize trên một dòng, bộ đếm của cách lưu A đơn giản hơn.

2. Để database thi hành. Nếu ghế có số (hoặc bạn tạo sẵn một dòng cho mỗi vé, như các slot ở bài đặt lịch), ràng buộc UNIQUE (event_id, seat_no) biến phantom thành xung đột thật. Hai người cùng chọn một ghế đụng nhau ở unique index và một người nhận 23505. Với vé đứng, tạo sẵn các dòng rồi chiếm một dòng bằng SKIP LOCKED:

CREATE TABLE seats (
  event_id int  NOT NULL,
  seat_no  int  NOT NULL,
  buyer    text,                                   -- NULL = free
  PRIMARY KEY (event_id, seat_no)
);
INSERT INTO seats VALUES (1, 1, NULL);

UPDATE seats SET buyer = 'minh'
WHERE  (event_id, seat_no) = (
         SELECT event_id, seat_no FROM seats
         WHERE  event_id = 1 AND buyer IS NULL
         LIMIT  1 FOR UPDATE SKIP LOCKED)
RETURNING seat_no;                                -- 0 rows: nothing free right now (rows held by in-flight buyers are skipped)

3. Nâng isolation level. Chạy nguyên handler cũ ở SERIALIZABLE và để database tự phát hiện mẫu nguy hiểm. Đây là cách chữa duy nhất dùng được cho code ngây thơ mà không phải sửa, và nó đi kèm một hợp đồng: ==!bạn phải bắt 40001 và retry cả transaction==.

BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT count(*) FROM tickets WHERE event_id = 1;          -- 0
INSERT INTO tickets (event_id, buyer) VALUES (1, 'linh');
COMMIT;
-- the app only inserts if count < capacity; when both run concurrently, one statement (often the COMMIT) fails with:
-- ERROR:  could not serialize access due to read/write dependencies among transactions
-- SQLSTATE 40001  ->  retry the whole transaction; it now sees count = 1 and sells nothing

async function withRetry<T>(fn: (tx: Tx) => Promise<T>, max = 5): Promise<T> {
  for (let attempt = 1; ; attempt++) {
    try {
      return await db.transaction(fn, { isolationLevel: "serializable" });
    } catch (e: any) {
      if (e.code !== "40001" || attempt === max) throw e;   // only retry serialization failures
      await sleep(10 * 2 ** attempt + Math.random() * 10);   // backoff with jitter
    }
  }
}

06Bản đồ các mức isolation và anomaly

07Ba cách để serializable thật sự

Serializable là mức duy nhất hứa: kết quả giống như thể các transaction chạy từng cái một, theo một thứ tự nào đó. Nếu bạn muốn invariant đúng mà không phải nghĩ một cách chữa riêng cho từng query, sách mô tả ba họ cách làm, và mỗi họ trả giá bằng một loại tiền khác nhau.

Chạy tuần tự là công cụ thô: nó làm cả họ bug biến mất, nhưng chỉ hợp với transaction ngắn, chạy trong bộ nhớ, và checkout vé mà gọi cổng thanh toán giữa transaction sẽ làm kẹt thread duy nhất. 2PL là cách bi quan: nó lock mọi thứ nó đọc, kể cả khoảng “các vé của sự kiện 1”, đúng là thứ chặn được phantom của ta. Cũng chính vì thế nhiều kỹ sư né nó: transaction chờ lock làm kẹt hàng người sau, và hai transaction chờ nhau thì deadlock (bài 06 đào sâu đúng chuyện này).

SSI là cách lạc quan, và là cách Postgres đưa ra. Không ai bị chặn; database canh mẫu nguy hiểm (một transaction đã đọc thứ mà transaction đồng thời sau đó sửa) và hủy một trong hai, thường lúc commit. Nó thận trọng nên đôi khi hủy cả transaction vốn vô hại. Đó chính là 40001 trong ví dụ ở trên. Khác biệt giữa hai thế giới là lúc bạn trả giá: 2PL bắt bạn chờ từ đầu, SSI cho bạn chạy và đôi khi bảo bạn đi lại. Khi contention thấp, SSI là món hời. Với một vé và mười nghìn người mua, mọi người thua cùng retry một lúc lại là một cơn bão riêng, nên các đợt mở bán nhu cầu cao vẫn thích một update atomic trên bộ đếm, và bộ đếm đó lại thành một dòng nóng riêng (bài 07).

08Kết: cái tên phụ thuộc vào cách mô hình hóa

Cùng một chiếc vé, cùng hai ngón tay. Lưu một con số thì lỗi là lost update; lưu thành dòng thì là write skew. Gọi tên hình dạng trước, rồi mới chọn công cụ.

Duy Anh, ghi chú khi đọc DDIA chương 7

Đó chính là lý do người phỏng vấn mê câu hỏi này. Ứng viên nói “khóa dòng lại” có phản xạ đúng và được một nửa đáp án. Câu hỏi tiếp theo (“giờ mỗi vé là một dòng và bạn kiểm tra count < capacity, điều gì thay đổi?”) tách người học thuộc một cách chữa khỏi người hiểu một mức isolation hứa gì và không hứa gì. Một anh DBA mình từng làm cùng có ghi trong sổ một dòng tóm tắt: tìm tiền đề chung, rồi quyết định ai sở hữu nó. Dòng đó đã cứu mình hơn một lần. Bài kế tiếp (bài 03): những người mua xếp hàng sau một lock chính là thứ biểu đồ p99 phơi ra còn con số trung bình che đi.

• Bộ đếm? ==UPDATE … WHERE n > 0 atomic==. Lùi về CAS hoặc cột version khi giá trị mới không phải phép tính, và FOR UPDATE khi quyết định trải qua nhiều statement.
• Dòng kèm count? Tiền đề là một phantom. ==Materialize nó, ràng buộc nó, hoặc lên SERIALIZABLE và retry 40001.==
• Đừng tin tên mức isolation giữa các engine. REPEATABLE READ của Postgres bắt được lost update; của InnoDB thì không.

Câu hỏi phỏng vấn để luyện

1. Còn một vé, hai người mua đồng thời. Gọi tên anomaly và nêu ba cách chữa.
2. Trên Postgres, vì sao SELECT … FOR UPDATE không giúp được khi mỗi vé là một dòng riêng và bạn đếm chúng?
3. REPEATABLE READ có ngăn lost update không? Trả lời cho Postgres và cho MySQL.
4. So sánh 2PL và SSI: mỗi cách bắt bạn trả giá lúc nào?

Bài viết của Vũ Duy Anh, kỹ sư backend ở Hà Nội. Câu hỏi hay góp ý sửa sai xin gửi qua email.