50 năm sau, Two-Phase Locking có còn là lựa chọn tốt nhất?
(concurrencyfreaks.blogspot.com)- Two-Phase Locking(2PL), được công bố năm 1976, cung cấp Opacity mạnh hơn serializability, nhưng sau gần 50 năm vẫn còn các giới hạn về khả năng mở rộng khi đọc và bảo đảm tiến triển
- Với các quy tắc đơn giản về lấy và nhả khóa, 2PL xử lý các giao dịch trên nhiều bản ghi đồng thời cung cấp mức cô lập mạnh, nên vẫn được dùng rộng rãi trong các CSDL giao dịch thương mại và cấu trúc dữ liệu đồng thời
- 2PL truyền thống có thể gây xung đột ngay cả giữa các thao tác đọc do khóa loại trừ lẫn nhau; dù dùng reader-writer lock, tại các điểm tập trung nhiều lượt đọc như gốc của cây tìm kiếm nhị phân vẫn phát sinh tranh chấp read-indicator
- 2PLSF phân tán chỉ báo theo từng reader lên các cache line để giảm tranh chấp khi lấy khóa đọc, và chỉ áp dụng fetch_and_add() trên bộ đếm nguyên tử trung tâm cho các giao dịch đã xung đột
- Các biến thể 2PL như No-Wait, Deadlock-detection, Wait-Or-Die vẫn để lại vấn đề live-lock hoặc khả năng mở rộng; 2PLSF là một cải tiến nhắm đồng thời tới khả năng mở rộng khi đọc và giao dịch starvation-free
Vì sao 2PL vẫn quan trọng
- Two-Phase Locking(2PL) là một trong những cơ chế kiểm soát đồng thời đa dụng đầu tiên cung cấp serializability; trên thực tế, nó cung cấp mức cô lập còn mạnh hơn là Opacity
- 2PL được công bố năm 1976 trong bài báo của Jim Gray và các cộng sự, và bản thân ý tưởng có thể đã tồn tại từ trước đó, nên thường được xem là một kỹ thuật gần 50 năm tuổi
- Kiểm soát đồng thời đa dụng là các thuật toán cho phép giao dịch có ngữ nghĩa all-or-nothing trên các mục dữ liệu như nhiều đối tượng, bản ghi, tuple
- Ưu điểm của 2PL nằm ở sự đơn giản và mức cô lập mạnh
- Trước khi đọc hoặc ghi một bản ghi, trước hết phải lấy khóa bảo vệ bản ghi đó
- Giữ các khóa đã lấy cho đến khi giao dịch kết thúc để tạo ra một góc nhìn nhất quán
Sự cô lập được tạo ra từ những quy tắc đơn giản
- Trong 2PL, mỗi lần truy cập trong giao dịch đều lấy khóa, và tất cả khóa được nhả ở thời điểm kết thúc giao dịch, khi biết rằng sẽ không còn truy cập nào nữa
- Tại thời điểm kết thúc, mọi khóa của dữ liệu đã truy cập đều đang được giữ, nên xuất hiện điểm tuyến tính hóa(linearization point) cho giao dịch đó
- 50 năm trước, nhiều nhà nghiên cứu cơ sở dữ liệu cho rằng có thể nhả khóa ngay sau khi truy cập xong bản ghi, nhưng kiểu kiểm soát đồng thời như vậy không bảo đảm serializability
- Các CSDL giao dịch thương mại đã biết sử dụng 2PL hoặc T/O, kết hợp với MVCC
- Trong lĩnh vực cấu trúc dữ liệu đồng thời, linearizability gần như là tiêu chuẩn; để ghi nhất quán lên nhiều node, thông thường cần một cách tiếp cận giống 2PL cho các truy cập ghi
- Ngoại lệ là cấu trúc dữ liệu lock-free, nhưng cần nhấn mạnh rằng triển khai lock-free đúng là việc khó
Nút thắt của 2PL: khả năng mở rộng khi đọc và live-lock
- Điểm yếu lớn của 2PL là thiếu khả năng mở rộng khi đọc và bảo đảm tiến triển kiểu live-lock
- 2PL cổ điển được thiết kế dựa trên khóa loại trừ lẫn nhau, nên ngay cả khi hai thread chỉ đọc cùng một bản ghi, chúng vẫn có thể xung đột và một hoặc cả hai phải abort rồi khởi động lại
- Chuyển sang reader-writer lock sẽ giảm xung đột giữa các lượt đọc, nhưng làm tăng chi phí khóa và lượng bộ nhớ sử dụng
- Khóa loại trừ lẫn nhau có thể được triển khai bằng 1 bit biểu thị trạng thái khóa/nhả
- Reader-writer lock cần thêm một bộ đếm số reader hiện đang giữ khóa ở chế độ đọc ngoài bit này
- Ví dụ, bộ đếm 7 bit có thể biểu diễn tối đa 128 thread, và mỗi khóa có thể chiếm 1 byte
- Nếu cơ sở dữ liệu có hàng chục tỷ bản ghi, chỉ riêng khóa cũng cần hàng chục tỷ byte
- Vấn đề lớn hơn là tranh chấp trên bộ đếm
- Trong workload read-non-disjoint, nhiều lượt đọc tập trung vào cùng một dữ liệu
- Node gốc của cây tìm kiếm nhị phân là ví dụ điển hình: mọi thao tác đều phải đọc nó trước khi đi xuống các node con
- Trong 2PL, mỗi lần truy cập gốc đều cần lấy khóa, và ngay cả khi dùng reader-writer lock, khóa của node gốc vẫn bị tranh chấp nặng
Cách tiếp cận hiện có và read-indicator có thể mở rộng
- TLRW là cách tiếp cận do Dave Dice và Nir Shavit trình bày tại SPAA 2010, dùng reader-writer lock để tăng hiệu năng so với khóa loại trừ lẫn nhau, nhưng vẫn không nhanh bằng kiểm soát đồng thời lạc quan
- Nếu áp dụng một triển khai tương tự TLRW, trong đó mỗi truy cập đọc tranh chấp trên một biến duy nhất của reader-writer lock, cho cây tìm kiếm nhị phân Rank-based Relaxed AVL, khả năng mở rộng hầu như đi ngang dù là giao dịch ghi hay giao dịch đọc
- Tranh chấp read-indicator có thể được giảm nhẹ bằng read-indicator có thể mở rộng
- Cách được ưu tiên là reader-writer lock trong đó mỗi reader đánh dấu lúc đến và rời đi trên một cache line riêng
- Việc lấy khóa đọc sẽ không còn tranh chấp
- Thread muốn lấy khóa ghi phải quét tất cả cache line để kiểm tra có được phép hay không, nên chi phí lấy khóa ghi tăng lên
- NUMA Aware reader-writer locks bàn về các thuật toán reader-writer lock dùng kỹ thuật này
- Trong ba thuật toán reader-writer lock, hai thuật toán có khả năng mở rộng cao nhưng không starvation-free
Thiết kế reader-writer lock của 2PLSF
- Two-Phase Locking Starvation-Free(2PLSF) là cơ chế kiểm soát đồng thời được triển khai bằng reader-writer lock mở rộng tốt khi lấy khóa đọc và có thêm các thuộc tính khác
- Reader-writer lock của 2PLSF dành riêng 1 bit cho mỗi thread để phục vụ read-lock
- Các bit này được đặt trên cache line riêng
- Chúng được bố trí cùng với các bit read-indicator của các khóa liền kề
- Giống như bài báo về NUMA-aware reader-writer lock, chi phí được chuyển sang việc lấy khóa ghi
- Khóa ghi phải quét nhiều cache line
- Đây không phải lời giải thần kỳ mà là một đánh đổi
- Lý do đánh đổi này hữu ích là phần lớn workload thiên về read-heavy, và ngay cả workload write-intensive cũng dành đáng kể thời gian cho truy cập đọc, chẳng hạn ở bước tra cứu bản ghi
- Khi dùng reader-writer lock cải tiến, 2PL có thể mở rộng ngay cả với workload read-non-disjoint, nhưng vấn đề live-lock cần được giải quyết riêng
Các vấn đề bảo đảm tiến triển còn lại ở các biến thể 2PL
- 2PL cổ điển có các biến thể tiêu biểu như No-Wait, Deadlock-detection, Wait-Or-Die tùy theo cách xử lý tranh chấp
-
No-Wait
- Khi xảy ra xung đột, abort giao dịch của mình hoặc giao dịch của phía bên kia rồi thử lại
- Việc thử lại có thể diễn ra ngay lập tức hoặc sau đó theo kiểu exponential backoff
- Nếu một giao dịch muốn sửa A rồi B và một giao dịch khác muốn sửa B rồi A liên tục xung đột, cả hai có thể lặp lại abort-restart mà không commit được, nên có live-lock progress
-
Deadlock-detection
- Duy trì danh sách các thread đang chờ trên khóa và phát hiện chu trình, tức deadlock
- Với reader-writer lock, mỗi reader phải có danh sách riêng, và cũng cần khóa loại trừ lẫn nhau để bảo vệ từng danh sách
- Khi lấy khóa ở chế độ read-lock, phải quét tất cả danh sách reader, nên chi phí tăng cao
- Về lý thuyết có thể đạt starvation-free, nhưng điều này cần starvation-free lock và mâu thuẫn với mục tiêu vì không có reader-writer lock starvation-free có khả năng mở rộng cao nào được công bố
- Nếu mỗi reader có một danh sách riêng, mức dùng bộ nhớ cũng có thể tăng lớn
-
Wait-Or-Die
- Gán thứ tự cho mọi giao dịch; khi xảy ra xung đột khóa, so sánh timestamp của giao dịch và timestamp của chủ khóa để quyết định chờ hay abort
- Với khóa loại trừ lẫn nhau, cách này hoạt động tốt vì chủ sở hữu có thể được lưu trong khóa bằng định danh thread duy nhất
- Nếu dùng cùng cách này với reader-writer lock, cần thread-id cho từng reader
- Để hỗ trợ 256 thread, mỗi reader-writer lock cần 8 bit × 256 = 256 byte
Nút thắt bộ đếm nguyên tử trung tâm và khác biệt của 2PLSF
- Trở ngại lớn hơn của Wait-Or-Die là mọi giao dịch phải có ID giao dịch duy nhất
- Ví dụ, có thể lấy số từ biến nguyên tử trung tâm bằng fetch_and_add() để tạo thứ tự
- Trên hầu hết CPU hiện đại, khó thực hiện hơn 40 triệu lần fetch_and_add() mỗi giây trên một biến nguyên tử có tranh chấp
- Con số này có thể trông lớn khi so với khoảng 660 triệu giao dịch mỗi ngày của Visa
- Nhưng với in-memory DBMS hoặc cấu trúc dữ liệu đồng thời, nó có thể chưa đủ lớn
- Trên một máy thử nghiệm, rất khó vượt quá 20 triệu fetch_and_add() mỗi giây
- Việc fetch_and_add() này cần cho mọi giao dịch, bao gồm không chỉ giao dịch ghi mà cả giao dịch đọc, và đó là điểm hạn chế khả năng mở rộng
- TL2 cho phép giao dịch đọc thực hiện đọc lạc quan mà không gọi fetch_and_add() nguyên tử
- Xét riêng giao dịch đọc, nó có thể mở rộng tới hàng trăm triệu tps
- Ngược lại, 2PL dựa trên Wait-Or-Die không thể vượt quá 40M tps/sec
- 2PLSF chỉ đánh thứ tự các giao dịch đã rơi vào xung đột
- Số giao dịch phải thực hiện fetch_and_add() trên biến nguyên tử trung tâm giảm xuống
- Các giao dịch không xung đột không bị kẹt ở ngưỡng 40M tps
- Ví dụ, có thể có 200M tps chạy không xung đột, và chỉ 40M tps đang xung đột bị ràng buộc bởi giới hạn fetch_and_add()
- Thuật toán cung cấp starvation-freedom
Tài liệu và đánh giá cuối cùng
- Bản thân thuật toán 2PLSF không được trình bày chi tiết, nhưng được đánh giá là tương đối đơn giản đối với một thuật toán starvation-free
- Bài báo và mã nguồn được cung cấp làm tài liệu tham khảo
- 2PLSF cũng được liên kết tới bài báo ACM, và được tóm lược là thuật toán do Pedro Ramalhete, Andreia, Pascal Felber tạo ra
- Mục tiêu của 2PLSF gần với những tính chất mà 2PL lẽ ra nên có ngay từ đầu
- Mở rộng tốt ngay cả trong tình huống read-non-disjoint, nơi các lượt đọc chồng lấn nhau
- Cung cấp giao dịch starvation-free, hình thức cao nhất của blocking progress
- Có thể duy trì khả năng mở rộng ngay cả trong một số tình huống xung đột
- 2PLSF không hoàn hảo, nhưng được đánh giá tốt hơn TL2 về mặt xử lý xung đột; khác biệt giữa nó và 2PL truyền thống được ví như khác biệt giữa cuốc chim và búa khoan
1 bình luận
Ý kiến trên Hacker News
Tôi tò mò không biết best practice trong ngành là gì để đồng bộ hóa hoặc giữ cho nhiều kho dữ liệu “nhất quán” trong kiến trúc microservices phân tán
Vài ngày trước tôi đã thử giải quyết vấn đề không nhất quán bằng “settled timestamp”; nó khá giống một cách tiếp cận đa phiên bản, trong đó nếu thời gian trôi qua mà không có báo cáo lỗi thì coi đó là một lưu/commit hợp lệ. Có thể xem giai đoạn thứ hai trong two-phase commit chính là thời gian
Cách làm là giám sát đồng hồ của các máy chủ khác; nếu nó không được cập nhật thì không tin settled timestamp của máy chủ đó. Ý định là mở rộng tính nhất quán ra nhiều máy chủ, vì với mỗi lần cập nhật không cần chờ phản hồi mà chỉ cần chờ khoảng timestamp kế tiếp
Tôi đã viết mã Python đa luồng, đa xử lý để kiểm thử tính phi quyết định bằng 10 thread gửi qua lại các cập nhật ngẫu nhiên: https://replit.com/@Chronological/InconsistencySimulation#ma...
Trong mô phỏng này, thao tác đọc là giá trị nhỏ nhất trong toàn bộ timestamp mà tất cả máy chủ báo cáo; sau 10 giây, khi hỏi giá trị bộ đếm của từng thread, đôi khi tất cả trả về cùng một giá trị, nhưng khá thường xuyên rơi vào trạng thái split-brain
Tôi biết rằng trong hệ phân tán, wall clock timestamp không phù hợp để quyết định thứ tự, và nên dùng đồng hồ logic hoặc vector clock
Sẽ rất tốt nếu có thể khiến mô phỏng báo cùng một con số ở bất kỳ thời điểm nào. Bloomlang cố giải quyết vấn đề trong eventual consistency, nơi các giá trị đến muộn ảnh hưởng đến kết quả khiến hệ không thể linearizable
Tôi đặc biệt quan tâm đến việc mở rộng quy mô trong khi vẫn giữ tính nhất quán, nhưng đây có vẻ là một bài toán khá khó
Nhiều hệ thống ghi tuần tự vào nhật ký trung tâm, và nhật ký đó nhận yêu cầu giống như một kho khóa-giá trị. Nhật ký ấy được sao chép tới mọi node, rồi các node đọc nhật ký để thực thi logic phức tạp được yêu cầu
Kubernetes dùng etcd, nên nó mở rộng khá tốt với vai trò một kho khóa-giá trị có tính nhất quán mạnh
Vì bạn nói “nhiều kho dữ liệu”, tôi giả định là có dữ liệu dị thể và những lựa chọn như CockroachDB không phù hợp
Nếu là người mới thì tự xây là nguy hiểm. https://aphyr.com/ là tài liệu gần như chuẩn mực về kiểm thử và cũng rất tốt cho mục đích học tập. Bạn có thể kiểm thử hệ phân tán bằng Jepsen, nhưng tốt hơn là dùng một kho dữ liệu mà Kyle đã chứng minh là vững chắc
Tôi không quen thuộc với các kỹ thuật này, nhưng khi học về cơ sở dữ liệu, SSI được giới thiệu như một dạng two-phase locking “tốt hơn” trong tương lai. Tôi thắc mắc SSI khác 2PLSF ra sao, và vì sao nó không được nhắc đến ở đây
Nhưng với các hiệu ứng phân tán thì vẫn cần khóa, giao dịch hai pha, v.v. Cá nhân tôi xem chúng giống các tính năng bổ trợ cho nhau hơn là lựa chọn thay thế
Nếu đó là cấu trúc dữ liệu trong bộ nhớ thì điều này khá tự nhiên, nhưng nếu đang xử lý cơ sở dữ liệu bên ngoài hoặc tài nguyên bên ngoài dùng chung khác, có thể có cách tốt hơn
Thường thì có thể xử lý theo lô các yêu cầu để truy cập tài nguyên bên ngoài với mức đồng thời thấp hơn và payload lớn hơn. Nếu tài nguyên đó xử lý batch tốt, nhu cầu đồng thời và khóa sẽ giảm đi rất nhiều
Ví dụ, nếu dùng Postgres thì số lượng kết nối giảm, và có thể không cần thêm PgBouncer vốn làm tăng độ phức tạp
Tuy nhiên, gom lô yêu cầu lại không phù hợp với hầu hết ngôn ngữ lập trình. Những ngôn ngữ tối ưu cho mức đồng thời cao như channel của Go hoặc process của Elixir có thể làm tốt, nhưng với các ngôn ngữ xử lý mọi thứ bằng thread thì có thể rất đau khổ
Với các trang không thể nâng cấp lên HTTPS sẽ có cảnh báo, còn các trang hỗ trợ cả hai sẽ được chuyển thẳng sang phiên bản HTTPS
Và nếu liên kết HTTP đó nói về một thuật toán đồng thời hay thì tôi vẫn sẽ đọc
fetch_and_addđể lấy ID giao dịch không? Tôi còn nghi ngờ ngay từ đầu liệu có cần ID giao dịch hay khôngMục tiêu nghe có vẻ là đặt ra một thứ tự tùy ý nhưng nhất quán giữa các transaction đang hoạt động, để khi xảy ra xung đột thì các bên có thể thống nhất ai phải chờ và ai bị “giết”. Vậy dùng thread ID không được sao?
Một con số ngẫu nhiên cũng có thể dùng được. Nếu xử lý trường hợp hòa là “chết”, thì trong tình huống xấu nhất cả hai transaction chỉ bị hủy không cần thiết rồi thử lại với một số ngẫu nhiên mới
Dù không được nhắc đến, có vẻ mục đích là ưu tiên transaction cũ hơn để các transaction chạy lâu không bị đói bởi các transaction ngắn. Ví dụ, nếu một transaction dài trung bình xung đột với ba transaction ngắn, và ở mỗi lần xung đột người thắng về cơ bản là ngẫu nhiên, thì xác suất transaction dài thắng cả ba lần để commit chỉ là 1/8
Nhưng để chống đói, không nhất thiết lần nào cũng phải ưu tiên transaction cũ hơn; chỉ cần trong phần lớn trường hợp là đủ. Đặc biệt khi nó chỉ cũ hơn một chút xíu thì càng như vậy
Vì thế, ngay cả khi có sai lệch đồng hồ giữa các thread hoặc các độ bất chính xác khác, một thứ kiểu timestamp hay cycle counter vẫn có thể hoạt động tốt. Trường hợp hòa thì phá bằng thread ID, hoặc cũng có thể cho cả hai bên cùng hủy
Nó phù hợp với trường hợp này và nhiều trường hợp khác
Two-phase commit mới là thứ có thể so sánh với Paxos, và cả hai đều thuộc nhóm giao thức đồng thuận
Two-phase locking là một cơ chế kiểm soát đồng thời
Vấn đề là khi thông điệp khóa đầu tiên biến mất, làm sao bạn biết thứ bị mất không phải là thông điệp phản hồi
Với trường hợp đơn giản thì cứ tiếp tục như GitHub hay Dropbox rồi xử lý xung đột sau cũng được. Nếu là cơ sở dữ liệu thì chỉ còn biết chúc may mắn; nếu là ngân hàng thì lại càng như vậy
Trong transaction chỉ đọc, TL2 chỉ cần lấy mẫu phiên bản toàn cục, rồi với mọi lần đọc, kiểm tra rằng phiên bản cục bộ không lớn hơn phiên bản đã lấy mẫu
Nếu vậy thì khó hiểu vì sao biểu đồ lại dưới tuyến tính, và vì sao TL2 không nhanh bằng các triển khai STM khác
Ví dụ, giả sử thường có 1000 tác vụ và 10–100 hardware thread
Tạo một danh sách đã sắp thứ tự gồm 1000 tác vụ, tạo bản sao của nó cho từng thread, rồi mỗi lần lại ngẫu nhiên hóa thứ tự của bản sao
Khi đó mỗi thread chỉ cần đọc danh sách của mình và thực thi tác vụ, rồi đăng ký theo dõi một danh sách được triển khai bằng hàng đợi đa luồng không chặn
Trong trường hợp xấu nhất, một vài thread có thể lặp lại một tác vụ nào đó
Với cách này, atomic operation có thể mở rộng tối đa tới 1000 lần