#190 - Thuật toán đồng thuận Viewstamped Replication

Sep 27, 2021

Grokking Newsletter là newsletter hàng tuần của Grokking cho các bạn software engineers người Việt.

Trong số này chúng ta cùng tìm hiểu về: Cách hoạt động của Bộ tối ưu hóa truy vấn SQL Server, thuật toán đồng thuận Viewstamped Replication, tổng quan về RocksDB, testing trong phát triển phần mềm, và một video của Joe Armstrong - cha đẻ của ngôn ngữ Erlang - nói về những khó khăn trong việc phát triển phần mềm.

Những bài viết hay

The SQL Server Query Optimizer

Một trong những điểm quan trọng để viết câu lệnh truy vấn tốt cho SQL Server đó là hiểu được cách hoạt động của Bộ tối ưu hóa truy vấn SQL Server (SQL Server Query Optimizer).

Bộ tối ưu hóa truy vấn của SQL Server là một bộ tối ưu dựa trên chi phí thực thi (cost-based optimizer). Khi nhận được một câu lệnh truy vấn từ phía client, bộ tối ưu hóa sẽ thực hiện tối ưu câu truy vấn thông qua các bước xử lý sau:

Phân tích cú pháp. Kết quả của bước này là một cây logic, mỗi nút trong cây đại diện cho một thao tác logic mà truy vấn phải thực hiện, chẳng hạn như đọc dữ liệu từ một bảng cụ thể hoặc thực hiện một phép Join 2 bảng bằng Hash Join hay Merge Join,… Cây logic này sau đó được sử dụng để thực hiện 2 bước tối ưu hóa truy vấn tiếp theo.
Tạo các kể hoạch thực thi truy vấn (execution plans). Sử dụng cây logic ở bước đầu tiên, bộ tối ưu thực hiện tạo một số các kế hoạch thực thi. Về lý thuyết, kế hoạch thực thi là một tập hợp các thao tác xử lý (index seek, nested loop join,…) được mô tả ở cây logic ở bước đầu tiên.
Đánh giá chi phi của từng kế hoạch. Mặc dù bộ tối ưu hóa không tạo ra tất cả các kế hoạch thực thi (vì không gian tìm kiếm sẽ tăng theo cấp số nhân khi số lượng bảng tăng lên), nhưng nó sẽ cố gắng tạo ra các kế hoạch được cho là tối ưu nhất có thể dựa trên phương pháp phỏng đoán (heuristics) và ước lượng chi phi của từng kế hoạch này.
Thực thi truy vấn, lưu kết quả vào bộ nhớ đệm

Bài viết đã giới thiệu các hoạt động cơ bản của Bộ tối ưu hóa truy vấn SQL Server, từ cách mà nó phân tích cú pháp câu truy vấn ban đầu đến cách tìm ra kế hoạch thực thi tốt nhất có thể cho mọi truy vấn được gửi đến SQL Server. Ngoài ra, tác giả cũng đã đề cập đến vấn đề làm thế nào để Bộ tối ưu hóa xác định một thứ tự JOIN table tối ưu trong một câu truy vấn, đây vẫn là một thách thức cơ bản trong việc tối ưu hóa truy vấn tính đến thời điểm hiện nay. Mời bạn tham khảo nội dung chi tiết hơn qua bài viết gốc.

We need to talk about testing

Bạn có tự hỏi tại sao chúng ta không tự động hoá hết mọi testcase không? Test coverage có phải một số liệu hữu ích không? Chúng ta nên test ở đâu và lúc nào? Bao nhiêu testing là đủ? Qua nhiều năm tác giả đã thảo luận nhiều lần về những câu hỏi tương tự, với các programmer và tester. Chúng là những chủ đề quan trọng, và thường bị hiểu nhầm và gây nhầm lẫn. Những cuộc thảo luận thường đưa mọi người tiến xa hơn so với điểm ban đầu, và vì vậy tác giả muốn chia sẻ lại một số cuộc thảo luận đó.

Một trong những ý chính trong bài viết cho là: mục đích của việc test là để tăng sự tin tưởng cho các stakeholders thông qua bằng chứng. Và từ đó, chúng ta chỉ test khi và chỉ khí nó phục vụ mục đích nêu trên. Nếu việc bạn đang làm không tăng sự tin tưởng rõ ràng cho ít nhất 1 stakeholder thông qua bằng chứng hữu hình, thì bạn đang không testing. Tác giả định nghĩa cụm từ "test theater" (nhà hát test) là những hành động mang lại ảo giác đang "test" khi không mang lại bất cứ thông tin hữu ích nào.

Tác giả cho rằng chúng ta đang hiểu sai khái niệm Test-driven development, hoặc TDD, và đa số các TDDers sẽ thường viết ít test nhất có thể, bởi vì theo Kent Beck, tác giả của Extreme Programming Explained: một lập trình viên không được trả công để viết test, họ được trả công để viết code chạy được. TDD, BDD, ATDD và những phương pháp liên quan không thay thế testing. Chúng chỉ là những kĩ thuật thiết kế và phát triển phần mềm. Vậy testing thật sự là như thế nào?

Trong bài viết gốc, tác giả giúp chúng ta trả lời câu hỏi chính đó bằng cách thảo luận sâu sắc về các câu hỏi phụ như: Tại sao chúng ta không tự động hoá hết mọi test? Test coverage có phải một số liệu hữu ích không? "Đẩy testing về bên trái" (shift testing left) có nghĩa là gì? Chúng ta nên test ở đâu và lúc nào? Bao nhiêu testing là đủ? Mời các bạn đón đọc để hiểu thêm về testing nhé.

Góc Distributed System

Viewstamped Replication Revisited

Nhắc tới thuật toán đồng thuận trong hệ thống phân tán, có 2 thuật toán nổi bật là Paxos và Raft. Paxos lần đầu được phát biểu năm 1989 - nhưng chỉ giải quyết cho đồng thuận trên đơn giá trị, do vậy tương đối hạn chế và chỉ được thảo luận trong cộng đồng học thuật. Lamport - tác giả của Paxos phát biểu lại thuật toán và đồng thời mở rộng ra đồng thuận trên một chuỗi các giá trị, tên là Multi Paxos, vào năm 2001. Tuy vậy, vẫn còn nhiều khó khăn trong việc hiểu và hiện thực thuật toán. Raft được phát biểu lần đầu năm 2012, được trình bày với định hướng engineering-focused, và đầy đủ hết mọi thành phần của một hệ thống như đồng thuận trên nhiều giá trị, discovery, recovery, tương tác với client … Do vậy, Raft trở nên phổ biến và được implement trên các hệ thống mới như CockroachDB, TiDB, Kafka, …

Tuy nhiên, thông tin ít được biết hơn là Raft dựa rất lớn trên thuật toán đồng thuận là Viewstamped Replication - được phát biểu năm 1988 trên tạp chí ACM computing. Đồng tác giả của paper là Liskov - nổi tiếng với định lí FLP Impossibility. Ngay từ version này đã giới thiệu các khái niệm như đồng thuận trên đa giá trị, tương tác với client, pseudo-code … Paper pBFT, xử lí đồng thuận trong môi trường byzantine, cũng được mở rộng từ Viewstamped Replication. Tác giả của thuật toán Raft cũng từng phát biểu:

ViewStamped Replication (VR) introduced some great ideas, and ViewStamped Replication Revisited was a huge improvement in clarity. I think the industry would be in a better place now with respect to consensus if it had paid less attention to Paxos and more to VR.

Tác giả đã trình bày lại thuật toán, ViewStamped Replication Revisited , với những cải tiến mới vào năm 2012. Ta có thể tìm hiểu thêm qua paper sau

Góc Database

RocksDB Overview

RocksDB, một embedded key-value database được Facebook phát triển vào năm 2012 (intial release) từ bản fork của Google’s LevelDB. RocksDB hiện nay được dùng khá là rộng rãi, đặc biệt là làm nền tảng cho các databases như là CockroachDB, Facebook ZippyDB, TiKV, Parity Ethereum Client, …

RocksDB là một storage engine chứa dữ liệu về key-value pairs với keys và values là một arbitrary byte streams. RocksDB sẽ tự sort tất cả dữ liệu và hỗ trợ các câu lệnh phổ biến như là Get(Key), NewIterator(), Put(key, val), Delete(key), và SingleDelete(key).

Theo như biểu đồ trên thì chúng ta có thể thấy rằng workflow của một lệnh viết sẽ đi theo các bước sau đây:

Tất cả các câu lệnh writes sẽ được ghi vào Memtable ở trên memory và Write-Ahead Log (WAL) ở trên một persistent storage. Các memtable sẽ được phân chia cho mỗi column family trong khi WAL được dùng chung cho tất cả column families. Mặc định thì chỉ có một column family gọi là “default” cho tất cả các keys. Tuy nhiên, người dùng có thể tạo nhiều column families khác nhau
Khi mà memtable đầy thì nó sẽ chuyển qua trạng thái immutable và được flush qua SST Table file ở level 0. RocksDB sẽ có background process để compact SST files qua nhiều level
Khi mà hệ thống có thay đổi gì thì sẽ được lưu ở Manifest Log. Ví dụ như là WAL file được đổi, SST file được đổi, Last consistent pointer, …

Để có thể hiểu rõ hơn về kiến trúc của RocksDB, mời các bạn tham khảo thêm qua các wikis trên RocksDB github.

Góc Lập Trình

Đề tuần này:

Cho trước node root của một cây nhị phân, tưởng tượng bạn đang đứng ở phía bên phải của cây, hãy trả về những node mà bạn có thể nhìn thấy từ trên xuống dưới.

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Các bạn có thể thử sức tại đây.

Lời giải tuần trước:

Ta có thể giải bài này theo phương pháp quy hoạch động, bạn đọc có thể tham khảo tại link: https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

Một cách tiếp cận khác để giải bài này là ta tìm longest increasing subsequence từ mảng rỗng sub = []. Ta lần lượt duyệt qua các phần tử và thêm vào mảng sub nếu phần tử hiện tại lớn hơn tất cả các phần tử trong mảng sub.

Ví dụ: ta có mảng nums = [1, 9, 2, 3, 10]

Khởi tạo mảng sub = []
i = 0, nums[i] = 1, ta có sub = [1]
i = 1, nums[i] = 9, do 9 > 1 nên ta có sub = [1, 9]

Với i = 3, nums[i] = 2, do 2 < 9 nên ta không thể thêm 2 vào mảng sub, tuy nhiên ta thấy 2 nằm trong longest increasing subsequence: [1, 2, 3, 10]. Vì vậy, ta cần thay thế số 9 bằng 2, sub = [1, 2]. Tiếp tục duyệt mảng đầu vào, ta sẽ có sub = [1, 2, 3, 10], vậy longest increasing subsequence là 4.

Cần lưu ý rằng mảng sub chỉ chứa longest increasing subsequence tại phần tử thứ i. Kết quả cuối cùng của mảng sub có thể không phải là subsequence. Bạn đọc có thể thử với mảng đầu vào nums = [8, 9, 10, 1, 2].

Giải thuật được thực hiện như sau: https://pastebin.com/v84yTK78

Giải thuât đòi hỏi time complexity là O(n^2).

Ta có thể tối ưu giải thuật để có độ phức tạp O(nlogn) bằng việc tìm vị trí thay thế phù hợp trong mảng sub bằng binary search.

Tech Talks

"The Mess We're In" by Joe Armstrong

Bạn đã bao giờ băn khoăn tại sao việc tạo ra một hệ thống phần mềm lại khó khăn đến vậy? Joe Armstrong cha đẻ của ngôn ngữ Erlang, đã đưa ra lời giải thích cho vấn đề đó trong video này. Ông đã kết nối những khái niệm vật lý, toán học với những giới hạn mà chúng ta gặp phải khi thiết kế và phát triển hệ thống phần mềm. Ở cuối bài ông đưa ra một số giải pháp, ý tưởng mà ông nghĩ có thể giúp chúng ta thoát khỏi "Đống hỗn độn mà chúng ta đang mắc kẹt ở trong".

Code & Tools

Graphviz - open source graph visualization software.
rust-analyzer - an implementation of Language Server Protocol for the Rust programming language.

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

Wer Ordnung hält, ist nur zu faul zum Suchen. (If you keep things tidily ordered, you’re just too lazy to go searching.)

- German Proverb