#188 - Transaction Isolation và thuật toán Two-phase locking (2PL)
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
Trong bài viết này tác giả Bop Nystrong - thành viên trong team Dart của Google đã khai sinh ra khái niệm "function coloring". Function coloring là một ẩn dụ về sự phân hoạch toàn bộ functions thành hai tập: async (màu đỏ) và sync functions - function bình thường (màu xanh).
Ý tưởng chính là async và sync function không thể kết hợp với nhau một cách hoàn hảo bởi vì async function có thể sử dụng bất cứ kiểu function nào trong khi đó sync function không thể gọi async function được. Do đó nếu muốn gọi async function trong sync function thì bắt buộc phải chuyển đổi toàn bộ sang async. Điều này đã tạo nên một sự chia rẽ giữa các functions và làm phức tạp hoá tất cả mọi thứ.
Không chỉ đưa ra khái niệm, tác giả còn phân tích một số giải pháp mà các ngôn ngữ vào thời điểm bài viết được viết (2015) giải quyết cho vấn đề này. Ví dụ như Promise với NodeJs, Async/Await với C# hoặc Go currency model.
Nếu bạn cảm thấy vấn đề hấp dẫn bởi vấn đề này thì các bạn có thể đọc bài viết và tìm hiểu thêm với một số bài viết/tranh luận sau:
Pitfalls and Patterns in Microservice Dependency Management
Mỗi khi bạn thay đổi hệ thống của mình, việc thay đổi sẽ ảnh hưởng đến nhiều bộ phận khác và nhiều thành phần khác của toàn bộ sản phẩm. Những thay đổi hệ thống này tạo ra hiệu ứng gợn sóng (ripple effect) tới tận người dùng cuối, những người mà bạn luôn phải để tâm. Bài viết này là tổng hợp kinh nghiệm cá nhân của 1 kỹ sư Google trong 10 năm với nhiều vai trò khác nhau, với bài thuyết trình cùng tên ở đây. Tác giả miêu tả về lí do và quá trình chuyển đổi từ monolithic sang microservices, với nhiều lợi ích, nhưng cùng với đó là nhiều thử thách qua các use cases thực tế, cùng với đó là bài học rút ra và kinh nghiệm chúng ta có thể tránh, có thể tóm tắt lại như sau:
Mỗi sản phẩm và mỗi tập khách hàng có những loại số đo tăng trưởng khác nhau. Khi quản lý các dependency cho kiến trúc microservice phân tán, chúng ta phải xem xét các loại tăng trưởng khác nhau như số lượng người dùng, hành vi người dùng, và tương tác giữa các dịch vụ và hệ thống con.
Các service stateless thường dễ quản lí hơn stateful.
Xây dựng các stacks tách biệt riêng giữa các vùng để tránh trường hợp outage toàn bộ, bao gồm các dependency của bên thứ ba hoặc trên cloud.
Vài chiến lược về architecture có thể giúp giảm chất lượng từ từ thay vì trả lỗi về ngay cho người dùng khi xảy ra outage. Ví dụ: sử dụng cache giữa API và database.
Khi xây dựng một bản SLO thì chúng ta phải tính đến SLO của tất cả dịch vụ backends đằng sau đó và các hành trình người dùng khác nhau (user journey), bao bồm các edge case.
Bài viết gốc có nói rõ chi tiết và ngữ cảnh của usecase, cùng với lí do cụ thể để đưa ra bài học, mời các bạn tham khảo thêm ở bài viết.
Sacrificial architecture: Learning from abandoned systems
Là một kỹ sư phần mềm, chắc chắn chúng ta sẽ gặp phải tình huống khi mà phải đưa ra lựa chọn đánh đổi giữa các tính năng, công nghệ khác nhau để tạo ra một hệ thống phù hợp nhất, hay nói cách khác là tìm được điểm cân bằng hợp lý cho hệ thống của mình. Một trong những quyết định khó khăn nhất mà bạn và nhóm của bạn có thể phải đối mặt đó là quyết định giữa việc giữ nguyên codebase của hệ thống hiện tại hay lựa chọn xây dựng lại từ đầu bằng một kiến trúc mới.
Đối với một số công ty công nghệ, quyết định xây dựng lại hệ thống của họ từ đầu là một quyết định dũng cảm và mang lại cho họ thành công lớn. Tuy nhiên đối với một số khác, đó lại là một sự thất bại.
eBay và Twitter là 2 ví dụ điển hình được đưa ra cho việc xây dựng hệ thống mới là một quyết định đúng đắn. Họ đều đã trải qua quá trình thiết kế lại hoàn toàn kiến trúc của mình để có được một hệ thống ổn định và có thể mở rộng quy mô hay hỗ trợ các tính năng mới một cách dễ dàng hơn. Nói như vậy không có nghĩa là hệ thống cũ của họ rất tồi, mà ngược lại, nó chính là nền tảng cần thiết để xây dựng nên hệ thống mới.
Trong bài viết này, tác giả đã thảo luận về tư duy kiến trúc hy sinh (Sacrificial architecture) và nêu lên vì sao nó có thể giúp bạn đưa ra quyết định chấp nhận vứt bỏ codebase cũ để xây dựng một hệ thống mới tốt hơn. Tác giả cũng đã nhấn mạnh rằng, hãy cố gắng thiết kế hệ thống như thể nó sẽ hoạt động tốt mãi mãi, nhưng sẵn sàng chấp nhận từ bỏ nó nếu nó trở nên lỗi thời.
Tracing at Slack: Thinking in Causal Graphs - Slack Engineering
Một số dự án mã nguồn mở như Zipkin và Jaegar đang được sử dụng rộng rãi cho bài toán distributed tracing. Tuy nhiên, ở bài viết sau đây, tác giả Suman Karumuri hiện đang là senior staff software engineer ở Slack thảo luận về các hạn chế của mô hình distributed tracing hiện tại, và sau đó nói về cách họ đã xây dựng và cải thiện hệ thống tracing ở Slack như thế nào. Trong đó, tác giả nhấn mạnh rằng họ không thể hoàn toàn sử dụng các giải pháp distributed tracing hiện tại out-of-the-box như Zipkin và Jaegar để mà theo dõi toàn bộ luồng đi của hệ thống, không chỉ riêng các hệ thống backend mà kể cả mobile, desktop clients, và async services.
Nhìn chung thì kiến trúc hệ thống tracing ở Slack được đề cập trong bài viết cũng không quá phức tạp. Tuy nhiên, chúng ta vẫn có thể học hỏi thêm về cách họ tiếp cận vấn đề và thiết kế SpanEvent object như thế nào để mà đáp ứng được nhiều nhu cầu tracing khác nhau như là theo dõi các luồng CI/CD của các tác vụ Jenkins ở Slack, hay là các nhu cầu truy vấn dữ liệu tracing bằng SQL queries.
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:
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:
https://www.hackerrank.com/challenges/ctci-merge-sort/problem
Lời giải tuần trước:
Đề bài
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
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:
Chọn nút gốc là nút cuối cùng trong “post-order”
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 ứngChia mảng “in-order” thành 2 mảng con lần lượt là
left[start...rootIdx - 1]
vàright[rootIdx + 1...end]
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