View profile

#188 - Transaction Isolation và thuật toán Two-phase locking (2PL)

Grokking Vietnam
Grokking Vietnam
Grokking Newsletter là newsletter hàng tuần của Grokking cho các bạn software engineers người Việt.
Tuần này: async và sync function, chuyển đổi từ monolithic sang microservice, sacrificial architecture, thuật toán Two-phase locking (2PL) và nhiều thông tin hay khác.

Những bài viết hay
Góc Database
Transaction Isolation và thuật toán Two-phase locking (2PL)
Trong các hệ thống database có hỗ trợ transactions, khi 2 (hay nhiều) transactions đồng thời cùng thực hiện truy cập một (hoặc nhiều) dữ liệu có thể gây ra hiện tượng race conditions. Một số tình huống race conditions có thể kể đến như: dirty read/writes, read/write skew, lost updates, …
Serializability là mức isolation (chữ cái I trong ACID) mà ở đó database đảm bảo kết quả khi thực hiện đồng thời các transactions sẽ tương tự như khi các transactions đó được thực hiện một cách tuần tự. Mức isolation này có thể giúp database tránh được hoàn toàn hiện tượng race conditions.
Để hỗ trợ serializability, một số ít database lựa chọn kiến trúc single-threaded (Redis, H-store), loại bỏ hoàn toàn tính concurrency, khi đó tất cả các transactions sẽ được thực hiện tuần tự trên một thread duy nhất. Với đa số DBMS phổ biến khác, 2PL là thuật toán được lựa chọn để cài đặt (MySQL, SQL Server, DB2, …).
Ý tưởng chính của 2PL là chia một transaction thành 2 phases theo thứ tự lần lượt:
  • Growing phase: transaction gửi yêu cầu tới Lock Manager của database để yêu cầu lock các tài nguyên, truy cập tới tài nguyên nào thì yêu cầu lock tài nguyên đó.
  • Shrinking phase: transaction thực hiện giải phóng lock, tại phase này transaction không được yêu cầu thêm lock mới nữa.
Tùy thuộc vào chiến thuật giải phóng lock tại shrinking phase, có thể có 2 tình huống: giải phóng sớm lần lượt từng tài nguyên, giải phóng tất cả lock ở cuối transaction (Strict-2PL). Hình minh họa:
Hình 1: Transaction lifetime khi 2PL khi giải phóng sớm lock
Hình 1: Transaction lifetime khi 2PL khi giải phóng sớm lock
Hình 2: Transaction lifetime với Strict-2PL
Hình 2: Transaction lifetime với Strict-2PL
Với chiến thuật giải phóng sớm, có thể xảy ra tình huống mà database buộc phải thực hiện cascading abort nhiều transactions nếu trong đó có 1 transaction liên quan bị abort, gây lãng phí công sức tính toán của những transactions khác. Vì vậy mà các database thường lựa chọn chiến thuật Strict-2PL (hình 2).
Mặc dù đảm bảo được tính isolation cho transaction ở mức cao, tuy nhiên 2PL có mặt hạn chế là chi phí cho việc quản lý lock lớn và dễ gây ra deadlock. Những hạn chế này làm giảm transaction thoughput và tăng response times nên nhiều database không sử dụng serializability là mức isolation mặc định, thay vào đó sử dụng các mức thấp hơn như Read Committed (PostgreSQL) hoặc Read Repeatable (InnoDB của MySQL).
Ngoài 2PL, còn kỹ thuật khác mới hơn để cài đặt serializability có tên gọi là Serializable Snapshot Isolation (SSI). Đây là kỹ thuật được PostgreSQL lựa chọn kể từ phiên bản 9.1.
Các bạn có thể tìm hiểu thêm về 2PL tại đây.
Góc Lập Trình
Đề tuần này:
Lời giải tuần trước:
Đề bài
Lời giải
Đề bài yêu cầu ta tạo một cây nhị phân khi biết kết quả của 2 trong 3 phương pháp duyệt cây: “pre-order”, “in-order”, “post-order”. Trong bài này tôi sẽ xây dựng cây khi biết kết quả của “in-order” và “post-order”, các bài còn lại cũng có cách tiếp cận tương tự.Để giải bài này, trước tiên ta cần ôn lại thế nào là duyệt cây theo “pre-order”, “in-order”, “post-order”. Bạn đọc có thể tham khảo bài viết sau
Ta có thể nhận thấy, nếu ta duyệt cây theo “in-order”, nút gốc sẽ luôn nằm ở giữa, bên trái nút gốc là tất cả các nút của cây con trái, bên phải nút gốc là tất cả các nút của cây con phải. Nếu duyệt cây theo “post-order”, ta có nút cuối cùng sẽ luôn là nút gốc của cây.
Dựa vào những đặc điểm trên, ta có thể xây dựng cây theo thuật toán đệ quy như sau:
  1. Chọn nút gốc là nút cuối cùng trong “post-order”
  2. Tìm vị trí của gốc trong “in-order”, ta tạm gọi là rootIdx. Tạo nút gốc với giá trị tương ứng
  3. Chia mảng “in-order” thành 2 mảng con lần lượt là left[start...rootIdx - 1]right[rootIdx + 1...end]
  4. Xây dựng cây con trái và cây con phải với các mảng con tương ứng
Nhằm loại bỏ thao tác copy array, phần thực hiện sử dụng biến left, right (hoặc start, end, from, to…) để mô phỏng thao tác chia mảng thành các mảng con. Bạn có thể tìm hiểu về giải thuật tại link pastebin này
Code & Tools
Góc Sponsors
Database documentation tự động với dbdocs.io
[Nội dung tài trợ] dbdocs.io là một công cụ giúp các bạn Dev có thể tự sinh ra nguyên trang document về cấu trúc database của mình chỉ bằng vài dòng lệnh command-line. Nó giúp quá trình planning và design database trong team dev dễ dàng hơn.
Hiện team dbdocs (ở TPHCM) đang tìm thêm 2 bạn fullstack/backend engineers để tham gia phát triển sản phẩm dev tool này. Bạn nào quan tâm có thể xem thêm tại: https://careers.holistics.io/job-openings/open-source-full-stack-engineer
(Team dbdocs cũng là team xây dựng công cụ dbdiagram.io phổ biến mà nhiều bạn dev đang dùng.)
Quotes
Any sufficiently advanced bug is indistinguishable from a feature
— R. Kulawiec
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam