Mô hình State Machine trong Distributed Systems

Bài viết được sự cho phép của tác giả Huy Hoàng

Khi tìm hiểu và làm việc với Hệ thống phân tán, chúng ta có thể thường gặp những thuật ngữ như: Bộ nhớ được nhân bản, Sao chép log hoặc Sự kiện-truyền, Sự kiện-lưu trữ. Tất cả những khái niệm này đều xoay quanh mô hình “Máy trạng thái”. Bài viết này sẽ miêu tả mô hình này và lý do tại sao Máy trạng thái được áp dụng rộng rãi trong Hệ thống phân tán.

Bạn đang xem: Mô hình State Machine trong Distributed Systems

Nhắc lại một số khái niệm cơ bản

• Trạng thái (state) của một tiến trình có thể hiểu là tập hợp các giá trị của các biến (variable) trong tiến trình đó. Ví dụ, nếu tiến trình p1 có thể có trạng thái S1 = {x=1, y=2}. Thường thì trong thực tế, một tiến trình sẽ có cả dữ liệu trong bộ nhớ RAM và trên đĩa cứng, tất cả các dữ liệu này đều được coi là trạng thái của tiến trình đó.
• Máy trạng thái trong tin học là một mô hình tính toán, trong đó một máy tính (máy) thay đổi trạng thái dựa trên chuỗi đầu vào mà nó nhận được. Hãy xem một ví dụ về bài toán: xác định xem trong một chuỗi số nhị phân (Ví dụ: 110100101), số lượng số 0 có phải là số chẵn hay không. Bài toán này có thể giải quyết bằng cấu trúc Máy trạng thái, trong đó chuỗi đầu vào là chuỗi các số nhị phân và “trạng thái” có thể là “chẵn” (S1) hoặc “lẻ” (S2). Máy trạng thái này bắt đầu từ trạng thái S1 (không có số 0), và với mỗi giá trị số, nó thay đổi trạng thái theo như hình vẽ bên dưới. Trạng thái cuối cùng cũng là kết quả (đầu ra) của bài toán.
• Về thứ tự của các phần tử trong một tập hợp. Giả sử ta có một tập hợp S={x1,x2,x3,x4}. Nếu tất cả các phần tử của tập hợp này có thể được sắp xếp theo một thứ tự cố định (Ví dụ: x1 < x2 < x3 < x4), bao gồm cả tính chất phản xứng (x1 < x2, x2 < x3 => x1 < x3) và phản xứng nghịch (x1 <= x2 & x2 <= x1 => x1 = x2), thì tập hợp này được gọi là có thứ tự hoàn toàn (toàn phần). Nếu không thỏa mãn điều kiện trên, thì tập hợp này có thứ tự một phần (bất kỳ). Khái niệm này quan trọng trong việc xác định thứ tự của các sự kiện trong Hệ thống phân tán. Bạn có thể tìm hiểu thêm về lý thuyết về thứ tự của tập hợp tại đây.

Bắt đầu từ một cấu trúc quen thuộc: log

Hầu như ai làm lập trình cũng phải làm việc với log. Đơn giản mà nói, log là một chuỗi các sự kiện để lưu thông tin về những sự kiện đã xảy ra trong quá trình hoạt động của phần mềm. Mỗi sự kiện được gọi là một bước. Ví dụ, đây là một đoạn log của dpkg trên Ubuntu:

$ tail -f /var/log/dpkg.log 2020-09-21 01:51:20 status installed man-db:amd64 2.9.1-1 2020-09-21 01:51:21 trigproc dbus:amd64 1.12.16-2ubuntu2.1 <none> 2020-09-21 01:51:22 status half-configured dbus:amd64 1.12.16-2ubuntu2.1 2020-09-21 01:51:23 status installed dbus:amd64 1.12.16-2ubuntu2.1 2020-09-21 01:51:24 trigproc mime-support:all 3.64ubuntu1 <none> 2020-09-21 01:51:25 status half-configured mime-support:all 3.64ubuntu1 2020-09-21 01:51:26 status installed mime-support:all 3.64ubuntu1 2020-09-21 01:51:27 trigproc initramfs-tools:all 0.136ubuntu6.3 <none> 2020-09-21 01:51:28 status half-configured initramfs-tools:all 0.136ubuntu6.3 2020-09-21 01:51:29 status installed initramfs-tools:all 0.136ubuntu6.3

Một bước trong ví dụ trên bao gồm hai thông tin: mô tả về sự kiện và thời điểm (timestamp) xảy ra sự kiện. Loại log quen thuộc này thường được gọi là log của ứng dụng, mục đích chính của nó là giúp chúng ta tìm thông tin khi cần thiết (ví dụ như để theo dõi lỗi chẳng hạn). Lưu ý là các bước trong log luôn có thứ tự toàn phần. Đối với log được trình bày trên, giá trị của timestamp là yếu tố xác định thứ tự các bước trong log. Bước log chỉ có thể được thêm vào log, không thể bị xóa hoặc thay đổi. Quy tắc này được gọi là “append-only” (chỉ thêm vào).

Trong lý thuyết về Hệ thống phân tán, hai thành phần thông tin trong log (nội dung và thứ tự của sự kiện) rất quan trọng. Các hệ thống Hệ thống phân tán hiện nay được xây dựng xung quanh việc đồng thuận về nội dung của chuỗi log. Quyền căn cứ này dựa trên nguyên tắc (tạm gọi là nguyên tắc nhân bản trạng thái) như sau:

Nếu chúng ta có hai tiến trình xác định (xác định) như nhau và chúng xử lý cùng một chuỗi dữ liệu đầu vào (đầu vào) như nhau, thì chúng sẽ có cùng đầu ra (đầu ra) và trạng thái cuối cùng (trạng thái).

Xem thêm : Full grain, top grain và genuine grain – Đâu là loại da tốt nhất?

Tiến trình xác định ở đây được hiểu là tiến trình chỉ hoạt động dựa trên xử lý các đầu vào mà không phụ thuộc vào các yếu tố bên ngoài (ví dụ như yếu tố thời gian, yếu tố ngẫu nhiên…). Rõ ràng là hai hệ thống xác định sẽ cho ra kết quả giống nhau nếu cùng nhận một chuỗi đầu vào. Do đó, chúng ta có thể lưu trữ toàn bộ lịch sử trạng thái của một hệ thống bằng cách lưu trữ chuỗi đầu vào dưới dạng log.

Từ đây, chúng ta có thể nhận thấy sự liên quan giữa “log” và “Máy trạng thái”. Nếu chúng ta có một tiến trình xác định được thiết kế theo cấu trúc Máy trạng thái và một log lưu trữ các đầu vào của tiến trình này, chúng ta có thông tin đầy đủ về quá trình hoạt động của tiến trình. Ví dụ, một hệ thống ngân hàng cần lưu trữ thông tin tài khoản của khách hàng. Chúng ta có thể lưu các yêu cầu xử lý của khách hàng dưới dạng log đầu vào như sau:

1. Khởi tạo tài khoản X.
2. Nạp 100.000 VND vào tài khoản X.
3. Khởi tạo tài khoản Y.
4. Chuyển 50.000 VND từ tài khoản X sang tài khoản Y.
5. Rút 20.000 VND từ tài khoản Y.

Từ log trên, chúng ta có thể dễ dàng tính toán ra trạng thái cuối cùng của hệ thống này (sau bước 5) là {X=50.000, Y=30.000}. Tuy nhiên, ngoài ra, cấu trúc log đầu vào này còn có một số ưu điểm như sau:

• Thứ nhất, cấu trúc này lưu trữ thông tin nhiều hơn so với việc lưu trạng thái thông thường. Ở đây, chúng ta có một lịch sử giao dịch đầy đủ cho tài khoản X và Y. Điều này cho phép chúng ta có thể xác định trạng thái của hệ thống tại bất kỳ thời điểm nào.
• Thứ hai, cấu trúc này hỗ trợ khả năng phục hồi thông qua sự cố của hệ thống. Nếu một máy chủ gặp sự cố trong quá trình hoạt động, khi phục hồi, chúng ta có thể tái tạo lại trạng thái cho máy chủ đó bằng cách “chạy lại” log đầu vào này (còn được gọi là ‘log replay’).
• Cấu trúc này cũng có khả năng mở rộng cao. Dữ liệu log được trình bày ở trên có thể nhân bản hoặc chuyển đổi thành các dạng dữ liệu khác để phục vụ cho các mục đích khác nhau. Chúng ta sẽ thảo luận thêm về điều này trong phần Sự kiện-lưu trữ.

Sao chép log và Máy trạng thái được nhân bản

Ở phần 2, chúng ta đã đề cập ngắn gọn về tầm quan trọng của bài toán đồng thuận (consensus) trong Hệ thống phân tán. Bài toán này thực ra là một phiên bản đơn giản hóa, vì yêu cầu được đặt ra chỉ là giúp các máy chủ đạt đồng thuận về một giá trị. Trên thực tế, các hệ thống khi hoạt động phải tiếp nhận yêu cầu từ người dùng và thay đổi trạng thái liên tục, do đó, bài toán ở đây là các máy chủ phải đạt đồng thuận về một chuỗi giá trị thay đổi theo thời gian. Các máy chủ cũng có thể bị mất kết nối hoặc gặp sự cố, làm cho việc đồng bộ thông tin giữa các máy càng trở nên phức tạp. Lấy ví dụ, nếu một máy chủ gặp sự cố và sau đó phục hồi, lúc đó trạng thái của máy chủ này đã khác biệt so với các máy chủ khác. Làm thế nào để ta biết trạng thái mới nào là trạng thái chính xác?

Mô hình Máy trạng thái được nhân bản (Replicated State machine – RSM) hoặc sao chép log, được phát triển để giải quyết vấn đề này. Trong mô hình này, mỗi máy chủ trong hệ thống được cấu trúc dưới dạng Máy trạng thái, tương tự với tiến trình xác định đã được nêu ở phần trên. Log trong trường hợp này là chuỗi các đầu vào mà hệ thống nhận được từ người dùng (khách hàng), được sắp xếp theo thứ tự thời gian (toàn phần). Máy trạng thái và log này được nhân bản đến tất cả các máy chủ trong hệ thống để giúp các máy chủ đạt đồng thuận với nhau. Có nhiều cơ chế để thực hiện thao tác nhân bản này, ví dụ như leader/follower (thuật toán Raft) hoặc atomic broadcast (thuật toán ZAB). Chúng ta sẽ tìm hiểu sâu hơn về các thuật toán này trong các bài viết tiếp theo.

Ưu điểm chính của cơ chế này là, trong trường hợp một máy chủ nào đó gặp sự cố, máy chủ này có thể khôi phục trạng thái bằng cách chạy lại log. Các máy chủ cũng có thể so sánh phiên bản log của mình và xác định phiên bản nào là phiên bản mới nhất (dựa trên thứ tự của các bước trong log). Ngoài ra, nếu một máy chủ mới được thêm vào hệ thống, máy chủ này cũng có thể đồng thuận với các máy chủ còn lại thông qua cơ chế tương tự.

Mối quan hệ với Sự kiện-lưu trữ

Mô hình Máy trạng thái nhân bản (RSM) và Sự kiện-lưu trữ (ES) là hai khái niệm khác nhau. RSM chỉ đề cập đến mô hình đồng thuận trong Hệ thống phân tán nói chung, trong khi đó ES thì nói về cách tổ chức và sắp xếp dữ liệu của một ứng dụng cụ thể. Tuy nhiên, hai khái niệm này đều dựa trên nguyên tắc nhân bản trạng thái đã được đề cập ở trên, vì vậy hãy cùng xem ES một chút ở đây.

Xem thêm : Bột nở Baking powder là gì? cách sử dụng và thay thế baking powder

Sự kiện-lưu trữ hoạt động dựa trên việc lưu trữ dữ liệu của một hệ thống dưới dạng một chuỗi các sự kiện (event) theo thứ tự thời gian trong một cấu trúc Log Sự kiện. Log sự kiện này là dữ liệu duy nhất mô tả trạng thái của hệ thống, cả tại thời điểm hiện tại và trong quá khứ. Kiến trúc ES hoạt động khác biệt so với kiểu truyền thống thêm-sửa-xóa (CRUD). Hãy lấy ví dụ về hệ thống ngân hàng ở phần trước: một hệ thống theo kiểu CRUD có thể lưu mỗi tài khoản trong một dòng trong bảng SQL, trong khi với ES, chúng ta lưu tất cả sự kiện trong hệ thống vào một chuỗi sự kiện duy nhất (như đã thấy ở trên). Giống như với log đầu vào, log sự kiện cho phép tái tạo lại dữ liệu của hệ thống vào bất kỳ thời điểm nào.

Ưu điểm lớn nhất của việc tổ chức dữ liệu theo kiểu này là tính đơn giản: một chuỗi sự kiện duy nhất chứa tất cả thông tin của hệ thống, từ số tiền hiện tại đến lịch sử giao dịch của mỗi tài khoản. Theo kiểu CRUD, chúng ta phải có một bảng riêng để lưu lịch sử giao dịch của các tài khoản và sử dụng JOIN khi cần truy cập dữ liệu từ nhiều bảng. Với ES, chúng ta chỉ cần một chuỗi duy nhất (thường được gọi là nguồn thông tin duy nhất).

Đơn giản này giúp cho các hệ thống sử dụng ES có tính đàn hồi (khả năng mở rộng) cao. Với kiểu CRUD, chúng ta thường cần thiết kế Cơ sở dữ liệu để tối ưu cho cả việc đọc và ghi dữ liệu. Tuy nhiên, không phải dữ liệu nào cũng có thể được tối ưu hoàn hảo. Hầu hết các hệ thống phải hy sinh hiệu năng đọc (hoặc ghi) để tối ưu cho hoạt động khác. Hơn nữa, các ứng dụng trong thực tế thường phải thay đổi theo thời gian để liên tục đáp ứng yêu cầu mới, do đó, việc tối ưu cơ sở dữ liệu từ đầu gần như không khả thi.

Với ES, dữ liệu được tổ chức theo cách hoàn toàn khác biệt. Mọi tiến trình ghi (write) đều có hiệu năng cao, vì chỉ cần thêm (append) sự kiện (vì sự kiện không được phép sửa/xóa). Các sự kiện này sau đó được chuyển đổi thành các dạng dữ liệu được tối ưu cho đọc (có thể là trong một bảng SQL hoặc các cơ sở dữ liệu khác). Quá trình này được gọi là chiếu (projection) (như hình minh hoạ trên), trong đó Log Sự kiện tại từng thời điểm nhất định được chuyển đổi thành các snapshot nhằm tối ưu hóa việc truy cập dữ liệu. Điều này giúp cho hệ thống không bị ràng buộc bởi cấu trúc mối quan hệ – thực thể (entity-relationship) trong các kiểu dữ liệu truyền thống.

Bài viết gốc được đăng tải tại dhhoang.github.io

Có thể bạn quan tâm:

• [P1] Tổng quan về Hệ thống phân tán
• Bài toán đồng thuận trong Hệ thống phân tán
• Bất biến và Có trạng thái trong Hệ thống phân tán

Xem thêm các công việc phát triển hấp dẫn trên TopDev

Nguồn: https://suphamyenbai.edu.vn
Danh mục: Wiki