Lab 2 khóa MIT 6.5840: Xây dựng Key/Value Store và Distributed Lock với tính nhất quán tuyến tính

Lab 2 của khóa học Hệ thống phân tán MIT 6.5840 là một bài thực hành thú vị giúp bạn tiếp cận cách xây dựng một hệ thống đáng tin cậy, ngay cả khi gặp lỗi mạng - chẳng hạn như gói tin bị mất hoặc trễ khiến client gửi lại yêu cầu nhiều lần - hay khi phải xử lý nhiều client truy cập song song. Bắt đầu từ một key/value server đơn giản chạy trên một máy, bạn sẽ dần hoàn thiện nó để đáp ứng những yêu cầu khắt khe về tính nhất quán tuyến tính (linearizability) và at-most-once semantics — hai yếu tố đóng vai trò then chốt trong việc xây dựng các hệ thống phân tán hiện đại như Amazon DynamoDB. Cụ thể, bạn sẽ phát triển hệ thống với các mục tiêu sau:

Đảm bảo các thao tác Put và Get luôn cho kết quả chính xác, kể cả khi nhiều client truy cập và thao tác đồng thời.
Xử lý đúng các trường hợp client gửi lại yêu cầu nhiều lần do gặp lỗi mạng hoặc hết thời gian chờ (timeout).
Xây dựng nền tảng cho cơ chế distributed lock - một công cụ quan trọng để đồng bộ hóa các tiến trình trong hệ thống phân tán.

Server bạn sẽ xây dựng hỗ trợ hai thao tác chính:

Put(key, value, version): Ghi một giá trị cho key tương ứng, nhưng chỉ khi version trùng khớp với dữ liệu hiện tại trên server.
Get(key): Trả về giá trị hiện tại của key cùng với version tương ứng.

Dù chỉ chạy trên một máy, server này phải đảm bảo hoạt động đúng trong môi trường mô phỏng có nhiều client đồng thời và các sự cố mạng. Điều khiến Lab 2 trở nên đặc biệt là bộ kiểm thử được thiết kế cực kỳ kỹ lưỡng — không chỉ kiểm tra các trường hợp đơn giản, mà còn mô phỏng các tình huống phức tạp như retry, race condition và truy cập song song. Bạn sẽ phải thực sự hiểu bản chất của vấn đề để vượt qua từng bài kiểm thử.

Hoàn thành lab này sẽ giúp bạn hiểu và nắm chắc một số khái niệm quan trọng trong hệ thống phân tán:

At-most-once semantics: Cách đảm bảo một thao tác chỉ được thực thi một lần, kể cả khi client gửi lại yêu cầu do lỗi mạng.
Linearizability: Mô hình nhất quán mạnh, trong đó mọi thao tác xảy ra như thể được xử lý tuần tự bởi một tiến trình duy nhất.
Distributed lock: Cách xây dựng cơ chế khóa phân tán dựa trên một key/value store đơn giản.
Phát triển dựa trên kiểm thử (test-driven development): Kỹ năng đọc hiểu và tận dụng bộ kiểm thử có sẵn để thiết kế một hệ thống chính xác và ổn định.

Linearizability là gì?

Trước khi bắt tay vào xây dựng server, chúng ta cần làm rõ một nguyên tắc nền tảng mà toàn bộ hệ thống sẽ dựa vào: linearizability.

Lý do rất đơn giản: bạn sẽ phát triển một server xử lý các thao tác đọc/ghi từ nhiều client đồng thời, trong điều kiện mạng không ổn định - có thể bị trễ, mất gói, hoặc thay đổi thứ tự truyền tải. Trong môi trường như vậy, không thể đơn giản giả định rằng “ai gửi trước thì được xử lý trước” — bởi vì “gửi trước” không đồng nghĩa với “đến trước” hay “xử lý trước”.

Để đảm bảo tính đúng đắn và nhất quán của dữ liệu, bạn cần một mô hình xác định rõ: khi nào một thao tác đọc/ghi được xem là đã thực sự xảy ra, và làm thế nào để toàn hệ thống phản ánh điều đó một cách nhất quán. Mô hình linearizability chính là câu trả lời cho yêu cầu này.

Hiểu và nắm vững linearizability là bước nền quan trọng. Không chỉ để vượt qua các test của bài lab - nơi mô phỏng đầy đủ các tình huống thực tế như retry, race condition hay lỗi mạng - mà còn để hình thành tư duy xây dựng hệ thống phân tán đáng tin cậy trong thực tế.

1. Tình huống giả định

Giả sử Bob đang mở ứng dụng ngân hàng trên điện thoại để kiểm tra số dư tài khoản, trong khi Alice, người thân của anh, đang rút tiền từ cây ATM cách đó vài cây số. Câu hỏi đặt ra là: Bob sẽ nhìn thấy gì trên màn hình? Số dư đã được cập nhật theo giao dịch của Alice chưa?

Linearizability - hay tính nhất quán tuyến tính - chính là mô hình giúp trả lời câu hỏi này một cách chặt chẽ. Nó định nghĩa rằng mỗi thao tác phải được xem như có hiệu lực tại một thời điểm duy nhất, nằm đâu đó giữa thời điểm bắt đầu và kết thúc của chính thao tác đó. Nhìn từ bên ngoài, hệ thống sẽ hành xử như thể các thao tác được thực hiện tuần tự, từng cái một, theo một thứ tự rõ ràng bởi một luồng duy nhất - bất kể thực tế đang có nhiều client và các thao tác diễn ra song song.

Mô hình linearizability dựa trên ba nguyên tắc cốt lõi:

Kết quả đọc phản ánh lần ghi gần nhất: Nếu một thao tác ghi đã hoàn tất, thì mọi thao tác đọc xảy ra sau đó phải nhìn thấy kết quả mà thao tác ghi đã tạo ra.
Ghi có thứ tự nhất quán: Khi nhiều thao tác ghi diễn ra gần như cùng lúc (chồng lấn về thời gian), hệ thống phải sắp xếp chúng theo một thứ tự duy nhất và đảm bảo rằng tất cả các thao tác đọc đều thấy cùng một thứ tự đó.
Phản ánh đúng thứ tự thao tác diễn ra quan sát được: Nếu thao tác A kết thúc trước khi thao tác B bắt đầu (tức là có thể quan sát được rõ ràng rằng A xảy ra trước B), thì hệ thống phải đảm bảo rằng A được xử lý trước B. Kết quả mà hệ thống phản hồi cho client không được đảo ngược thứ tự đó.

Vậy thế nào là đồng thời hay chồng lấn về mặt thời gian? Hãy tưởng tượng thao tác A bắt đầu lúc 00:00:00.000 và kết thúc lúc 00:00:00.005 (tức 5 mili giây sau). Trong khi đó, thao tác B bắt đầu lúc 00:00:00.003 và kết thúc lúc 00:00:00.007. Rõ ràng, khoảng thời gian thực hiện hai thao tác này bị chồng lấn lên nhau. Vì thao tác B bắt đầu trước khi thao tác A kết thúc, bạn không thể xác định một cách rõ ràng rằng thao tác nào xảy ra “trước” thao tác còn lại. Do đó, hệ thống được phép chọn bất kỳ thứ tự nào trong hai thao tác này — miễn là thứ tự đó hợp lệ và được duy trì nhất quán trong toàn bộ hệ thống.

Một hệ quả quan trọng của mô hình linearizability là: các thao tác xảy ra đồng thời – tức là chồng lấn nhau về mặt thời gian – có thể được hệ thống sắp xếp theo bất kỳ thứ tự nào, miễn là thứ tự đó hợp lệ và được duy trì nhất quán trong toàn bộ hệ thống. Tuy nhiên, đối với các thao tác có thứ tự rõ ràng về mặt thời điểm, nghĩa là thao tác A kết thúc trước khi thao tác B bắt đầu, thì hệ thống bắt buộc phải giữ đúng trình tự này khi phản hồi kết quả cho các client.

Để hiểu rõ hơn cách linearizability trả lời cho tình huống Bob kiểm tra số dư trong khi Alice đang rút tiền, hãy xem xét hai kịch bản dưới đây:

2. Phân tích tình huống

Để hiểu rõ hơn cách linearizability trả lời cho tình huống Bob kiểm tra số dư trong khi Alice đang rút tiền, hãy xem xét hai kịch bản dưới đây:

Kịch bản 1: Các thao tác diễn ra không đồng thời

Giả sử Alice thực hiện thao tác rút 100 đô la khỏi tài khoản của mình khi số dư ban đầu là 600 đô. Giao dịch của cô hoàn tất trước khi Bob mở ứng dụng ngân hàng để kiểm tra số dư. Cụ thể:

Lúc 8 giờ 00 phút 00 giây, Alice bắt đầu thao tác rút tiền.
Đến 8 giờ 00 phút 05 giây, giao dịch của Alice hoàn tất. Số dư lúc này còn lại 500 đô.
Đến 8 giờ 00 phút 10 giây, Bob mở ứng dụng và yêu cầu kiểm tra số dư.
Đến 8 giờ 00 phút 15 giây, hệ thống phản hồi kết quả kiểm tra cho Bob.

Trong trường hợp này, vì Alice đã rút tiền xong trước khi Bob bắt đầu kiểm tra số dư, nên theo mô hình linearizability, Bob phải thấy số dư đã được cập nhật — tức là 500 đô la. Hệ thống cần đảm bảo rằng nếu một thao tác ghi kết thúc trước khi một thao tác đọc bắt đầu, thì thao tác đọc đó phải phản ánh kết quả của thao tác ghi.

Kịch bản 2: Các thao tác đồng thời

Giả sử lần này, khi Alice đang trong quá trình rút tiền, thì Bob gần như đồng thời mở ứng dụng để kiểm tra số dư. Cụ thể:

Lúc 8 giờ 00 phút 00 giây, Alice bắt đầu thao tác rút 100 đô la.
Lúc 8 giờ 00 phút 01 giây, Bob bắt đầu yêu cầu kiểm tra số dư.
Đến 8 giờ 00 phút 04 giây, giao dịch của Alice hoàn tất.
Đến 8 giờ 00 phút 06 giây, hệ thống phản hồi kết quả kiểm tra cho Bob.

Vì các thao tác này chồng chéo về mặt thời gian, máy chủ có thể chọn một trong hai thứ tự:

Lúc này, thao tác của Bob diễn ra trong lúc giao dịch của Alice đang được xử lý – tức là hai thao tác đồng thời, hay nói cách khác, bị chồng lấn về mặt thời gian. Trong tình huống như vậy, hệ thống được phép lựa chọn một trong hai thứ tự thực thi hợp lệ:

Trường hợp 1: Hệ thống coi như Alice đã rút tiền xong trước khi Bob kiểm tra → Bob thấy số dư là 500 đô.
Trường hợp 2: Hệ thống coi như Bob kiểm tra trước khi Alice rút xong → Bob thấy số dư vẫn là 600 đô.

Cả hai phản hồi đều hợp lệ theo linearizability, miễn là hệ thống nhất quán với thứ tự đó cho tất cả các thao tác khác liên quan. Điều cốt lõi nằm ở chỗ: mỗi thao tác phải được gắn với một thời điểm duy nhất nằm trong khoảng thời gian nó thực thi, và toàn bộ hệ thống cần hành xử như thể các thao tác được thực hiện lần lượt, theo một dòng thời gian logic duy nhất.

Bây giờ, hãy cùng bắt tay vào thực hành.

Phần 1: Key/Value server với tính nhất quán tuyến tính (linearizability)

1. Yêu cầu chức năng

Trong phần này, chúng ta sẽ xây dựng một Key/Value Server đơn giản hỗ trợ hai thao tác RPC cơ bản:

Put(key, value, version): ghi dữ liệu có kiểm tra phiên bản.
Get(key): truy xuất giá trị và phiên bản hiện tại của một khóa.

1.1. Mục tiêu chính

Hệ thống cần đảm bảo hai yếu tố quan trọng:

Tính đúng đắn “at-most-once”: mỗi thao tác Put chỉ được thực hiện tối đa một lần, ngay cả khi client phải gửi lại yêu cầu do sự cố mạng.
Tính tuần tự (linearizability): mọi thao tác từ phía client phải được thực hiện theo một thứ tự hợp lý như thể tất cả thao tác đều diễn ra tuần tự trên một hệ thống đơn luồng.

1.2. Quy tắc xử lý thao tác Put

Nếu phiên bản được gửi lên khớp với phiên bản hiện tại trên server, server sẽ cập nhật giá trị và tăng phiên bản lên 1.
Nếu phiên bản bằng 0 và key chưa tồn tại, server sẽ tạo mới key-value tương ứng.
Nếu phiên bản không khớp, server từ chối thao tác và trả về lỗi ErrVersion.

1.3. Mạng không tin cậy và cách xử lý

Khi hoạt động trong môi trường mạng không tin cậy, client cần xử lý tình huống mất phản hồi bằng cách tự động gửi lại yêu cầu.

Một trường hợp khó xử lý là khi server phản hồi lại bằng rpc.ErrVersion đối với một RPC mà client đã gửi lại (retry). Trong tình huống này, client không thể biết chắc liệu thao tác Put của mình có thực sự được server thực hiện hay chưa: có thể RPC đầu tiên đã được server xử lý thành công, nhưng phản hồi từ server bị mất trên đường truyền, khiến client phải gửi lại yêu cầu, và server trả về rpc.ErrVersion cho lần gửi lại đó.

Hoặc cũng có thể một client khác đã cập nhật key trước khi RPC gửi lại của client này đến được server, khiến server không thực hiện RPC từ client này và trả về rpc.ErrVersion.

Do đó, nếu client nhận được rpc.ErrVersion cho một yêu cầu Put đã được gửi lại (retransmitted), client.Put phải trả về rpc.ErrMaybe cho ứng dụng, bởi vì không thể xác định liệu thao tác đã được thực hiện hay chưa. Việc xử lý tiếp theo trong trường hợp không chắc chắn này sẽ do ứng dụng quyết định.

Ngược lại, nếu server phản hồi rpc.ErrVersion cho một yêu cầu Put ban đầu (không phải là bản gửi lại), thì client có thể chắc chắn rằng RPC đó chưa từng được thực hiện và nên trả về rpc.ErrVersion cho ứng dụng.

2. Hiểu cách hệ thống được kiểm chứng qua các test cases

Bài lab cung cấp một tập hợp test case giá trị, giúp chúng ta kiểm chứng tính đúng đắn và hành vi của hệ thống. Hãy cùng phân tích từng test case để hiểu rõ nó đang kiểm tra điều gì.

TestReliablePut: Đây là test case cơ bản, kiểm tra hoạt động của các thao tác Put và Get trong điều kiện lý tưởng - mạng hoạt động ổn định, không có độ trễ, mất gói tin, hay trùng lặp thông điệp. Mục tiêu là xác minh rằng thao tác Put ghi dữ liệu thành công, Get có thể đọc lại chính xác giá trị vừa ghi, và máy chủ lưu trữ đúng phiên bản (version) của dữ liệu.
TestPutConcurrentReliable: Đây là test case kiểm tra tính đồng thời trong điều kiện mạng ổn định. Nó cho nhiều client đồng thời ghi vào cùng một key, nhằm đảm bảo hệ thống xử lý đúng khi có xung đột ghi. Cơ chế khóa bằng sync.Mutex được dùng để bảo vệ dữ liệu tránh khỏi lỗi ghi chồng. Ngoài ra, test case này còn sử dụng công cụ Porcupine để xác minh tính nhất quán tuyến tính (linearizability) bằng cách phân tích toàn bộ lịch sử các thao tác.
TestMemPutManyClientsReliable: Test case này đánh giá khả năng quản lý tài nguyên của hệ thống. Nó khởi tạo đến 100,000 client để kiểm tra xem máy chủ có bị rò rỉ bộ nhớ hay không. Một hệ thống triển khai đúng cần chỉ lưu lại trạng thái cuối cùng của dữ liệu, thay vì duy trì thông tin riêng biệt của từng client hoặc từng yêu cầu.
TestUnreliableNet: Đây là test case đánh giá khả năng chịu lỗi trong điều kiện mạng không ổn định, khi các thông điệp RPC có thể bị mất ở cả chiều gửi và nhận. Mục tiêu là kiểm tra logic thử lại (retry logic) của client, cũng như đảm bảo rằng máy chủ vẫn cung cấp đúng ngữ nghĩa at-most-once, tức là mỗi thao tác chỉ được thực hiện tối đa một lần.

3. Giải thích các mã lỗi sử dụng trong bài lab

Hệ thống RPC sử dụng một vài mã lỗi sau để biểu diễn trạng thái của các thao tác:

OK: Thao tác đã thực hiện thành công.
ErrNoKey: Khóa (key) được truy vấn không tồn tại trong hệ thống.
ErrVersion: Server từ chối thao tác Put vì phiên bản (version) mà client gửi lên không hợp lệ. Mã lỗi này đóng vai trò quan trọng trong việc ngăn chặn việc ghi trùng lặp và đảm bảo tính nhất quán.
ErrMaybe: Mã lỗi này xuất hiện khi client không nhận được phản hồi từ server sau khi gửi yêu cầu, do mất gói tin trong mạng. Khi đó, client không thể xác định thao tác đã được thực hiện hay chưa, và trả về ErrMaybe cho ứng dụng.

4. Triển khai

4.1. Thiết kế cấu trúc dữ liệu cho Server

K/V server sử dụng một map trong bộ nhớ để lưu các cặp key-value. Vì server có thể xử lý nhiều yêu cầu cùng lúc, nên cần thêm một sync.Mutex để đảm bảo việc truy cập dữ liệu được an toàn, tránh xung đột.

Mỗi key trong hệ thống không chỉ lưu giá trị (value) đơn thuần, mà còn kèm theo một trường version. Trường này ghi lại số lần giá trị của key đó đã được ghi đè, giúp hệ thống dễ dàng kiểm soát các thao tác cập nhật có điều kiện (ví dụ, chỉ thực hiện ghi nếu version hiện tại trùng khớp với version được gửi trong request. Nếu không khớp, thao tác sẽ bị từ chối để tránh ghi đè dữ liệu không mong muốn).
Để biểu diễn dữ liệu này, ta sử dụng một cấu trúc ValueHandle, chứa cả Value và Version.

Dưới đây là phần mã khởi tạo server trong file src/kvsrv1/server.go.

src/kvsrv1/server.go

package kvsrv

import (
	"sync"
	"6.5840/kvsrv1/rpc"
)

// ValueHandle lưu trữ cả giá trị và phiên bản hiện tại của nó.
type ValueHandle struct {
	Value   string
	Version rpc.Tversion
}

type KVServer struct {
	mu   sync.Mutex
	data map[string]ValueHandle
}

func MakeKVServer() *KVServer {
	kv := &KVServer{}
	kv.data = make(map[string]ValueHandle)
	return kv
}

4.2. Triển khai thao tác Get

Phía Server: Xử lý yêu cầu Get một cách an toàn

Hàm xử lý Get trên server chịu trách nhiệm truy xuất dữ liệu. Đây là một thao tác chỉ đọc (read-only), không làm thay đổi trạng thái của server, nên logic của nó khá đơn giản. Tuy nhiên, điểm mấu chốt là phải đảm bảo an toàn trong môi trường đa luồng. Bằng cách khóa mutex (kv.mu.Lock()) ngay khi bắt đầu và sử dụng defer kv.mu.Unlock() để đảm bảo nó luôn được giải phóng, chúng ta ngăn chặn được tình trạng đọc phải dữ liệu cũ hoặc không nhất quán (stale or inconsistent reads) trong khi một thao tác Put đang diễn ra.

func (kv *KVServer) Get(args *rpc.GetArgs, reply *rpc.GetReply) {
	// Khóa để bảo vệ quyền truy cập vào `kv.data` từ các yêu cầu đồng thời.
	kv.mu.Lock()
	defer kv.mu.Unlock()

	// Tra cứu key trong map.
	if value, ok := kv.data[args.Key]; ok {
		// Nếu tìm thấy, trả về giá trị và phiên bản hiện tại.
		reply.Value = value.Value
		reply.Version = value.Version
		reply.Err = rpc.OK
	} else {
		// Nếu không tìm thấy, trả về lỗi.
		reply.Err = rpc.ErrNoKey
	}
}

Phía Client: Gọi và xử lý Get với cơ chế retry

Phía client, việc gọi Get phải tính đến khả năng mạng không ổn định. May mắn là Get là một thao tác idempotent (an toàn để lặp lại), nghĩa là việc gửi lại yêu cầu nhiều lần không gây ra tác dụng phụ hay làm thay đổi trạng thái của server.

Dựa vào tính chất này, client có thể triển khai một vòng lặp for đơn giản để đảm bảo độ tin cậy:

Liên tục gửi yêu cầu RPC KVServer.Get.
Nếu nhận được phản hồi (ok là true), vòng lặp kết thúc và trả về kết quả.
Nếu yêu cầu thất bại do lỗi mạng (ok là false), client sẽ đợi một khoảng thời gian ngắn rồi tự động thử lại.

Cách tiếp cận này giúp Get hoạt động ổn định ngay cả khi có sự cố mất gói tin trên đường truyền.

func (ck *Clerk) Get(key string) (string, rpc.Tversion, rpc.Err) {
	args := rpc.GetArgs{Key: key}
	reply := rpc.GetReply{}
	// Bắt đầu một vòng lặp vô hạn để thử lại cho đến khi thành công.
	for {
		// Thực hiện cuộc gọi RPC đến phương thức "KVServer.Get".
		ok := ck.clnt.Call(ck.server, "KVServer.Get", &args, &reply)
		if ok {
			// Nếu cuộc gọi thành công (nhận được phản hồi),
			// trả về kết quả ngay lập tức.
			return reply.Value, reply.Version, reply.Err
		}
		// Nếu cuộc gọi thất bại (lỗi mạng), đợi một chút rồi lặp lại.
		// Đây là cơ chế retry đơn giản.
		time.Sleep(100 * time.Millisecond)
	}
}

4.3. Triển khai Put có điều kiện để đảm bảo At-Most-Once

Đây là phần thử thách nhưng cũng thú vị nhất của bài lab. Khác với Get, thao tác Put có thể thay đổi trạng thái của server (cập nhật giá trị và tăng phiên bản). Điều này khiến nó trở thành một thao tác không idempotent: nếu thực hiện nhiều lần, kết quả có thể khác so với chỉ thực hiện một lần, dẫn đến nguy cơ sai lệch hoặc mất dữ liệu.

Thử thách đặt ra là: làm sao để client có thể gửi lại yêu cầu Put khi gặp lỗi mạng, mà vẫn đảm bảo rằng thao tác đó chỉ được thực thi tối đa một lần (at-most-once) trên server?

Giải pháp nằm ở việc thiết kế hợp lý giữa logic xử lý ở client và server, trong đó cơ chế kiểm tra phiên bản (version checking) đóng vai trò then chốt.

a) Phía Server: Logic Put có điều kiện

Cốt lõi của cơ chế at-most-once nằm trong hàm xử lý Put ở phía server. Tại đây, server sử dụng args.Version do client gửi lên như một “vé kiểm soát” để quyết định có chấp nhận yêu cầu cập nhật hay không. Logic xử lý xoay quanh hai tình huống chính:

Cập nhật một key đã tồn tại: Server chỉ cho phép cập nhật nếu phiên bản từ client (args.Version) khớp chính xác với phiên bản hiện tại của key. Khi điều kiện này thỏa mãn, server sẽ ghi đè với giá trị mới và tăng phiên bản lên 1. Việc tăng phiên bản ngay lập tức khiến các yêu cầu Put cũ hơn (ví dụ bị gửi lại sau do lỗi mạng) trở nên vô hiệu, vì phiên bản không còn khớp. Nếu phiên bản không khớp, server trả về lỗi ErrVersion.
Tạo một key mới: Theo quy ước, việc tạo mới chỉ hợp lệ nếu args.Version == 0. Đây là tín hiệu cho biết client muốn khởi tạo chứ không phải cập nhật. Trong trường hợp này, server tạo key mới với giá trị được cung cấp và gán phiên bản bắt đầu là 1. Nếu args.Version khác 0, server từ chối với lỗi ErrNoKey (vì client đang cố cập nhật một key không tồn tại với một phiên bản không hợp lệ).

// Put là trình xử lý RPC, thực hiện cập nhật giá trị cho một key có điều kiện.
// Thao tác chỉ thành công nếu phiên bản từ client khớp với phiên bản hiện tại trên server.
func (kv *KVServer) Put(args *rpc.PutArgs, reply *rpc.PutReply) {
	kv.mu.Lock()
	defer kv.mu.Unlock()

	key := args.Key
	current, exists := kv.data[key]

	if exists {
		// Trường hợp 1: Key đã tồn tại.
		if args.Version != current.Version {
			// Phiên bản của client đã cũ, từ chối yêu cầu và trả về lỗi.
			reply.Err = rpc.ErrVersion
			return
		}
		// Phiên bản khớp, thực hiện cập nhật và tăng phiên bản.
		kv.data[key] = ValueHandle{Value: args.Value, Version: args.Version + 1}
	} else {
		// Trường hợp 2: Key chưa tồn tại.
		// Key mới chỉ có thể được tạo nếu client gửi phiên bản 0.
		if args.Version != 0 {
			// Client đang cố cập nhật một key không tồn tại với phiên bản khác 0 -> không hợp lệ.
			reply.Err = rpc.ErrNoKey
			return
		}
		// Tạo key mới với phiên bản đầu tiên là 1.
		kv.data[key] = ValueHandle{Value: args.Value, Version: 1}
	}

	// Nếu không có lỗi nào xảy ra, trả về OK.
	reply.Err = rpc.OK
}

b) Phía Client: Xử lý sự không chắc chắn với `ErrMaybe`

Khác với Get, thao tác Put có thể thay đổi dữ liệu trên server, nên client không thể đơn giản gửi lại yêu cầu nếu gặp lỗi mạng. Việc gửi lại có thể dẫn đến những tình huống khó xử, đặc biệt là khi client không biết chắc yêu cầu ban đầu đã được xử lý hay chưa.

Tình huống tiến thoái lưỡng nan Giả sử xảy ra kịch bản sau:

Client gửi yêu cầu Put đến server.
Server nhận được và xử lý thành công — giá trị được cập nhật, version được tăng lên — nhưng phản hồi OK bị mất trên đường truyền.
Không nhận được phản hồi, client nghĩ rằng yêu cầu đã thất bại nên gửi lại với nội dung y hệt (cùng args.Version).
Lúc này, server đã tăng version sau lần xử lý trước, nên khi nhận lại yêu cầu cũ, nó phát hiện version không khớp và trả về lỗi ErrVersion.

Khi nhận được lỗi ErrVersion trong lần gửi lại, client rơi vào thế khó xử — vì không thể biết chuyện gì thực sự đã xảy ra:

Trường hợp 1 (Yêu cầu đã thành công): Yêu cầu ban đầu đã được server xử lý, chỉ có điều phản hồi bị mất.
Trường hợp 2 (Yêu cầu thất bại): Yêu cầu chưa đến được server, hoặc một client khác đã cập nhật key đó trước.

Trong tình huống mơ hồ này, client không thể tự quyết định là có nên thử lại hay không. Cách xử lý tốt nhất là thông báo lên tầng ứng dụng rằng: “Tôi không chắc yêu cầu có được xử lý hay không.”
Đó chính là ý nghĩa của mã lỗi rpc.ErrMaybe.

Khi gặp lỗi mạng và sau đó nhận lại lỗi ErrVersion cho một yêu cầu đã từng gửi, client cần trả về ErrMaybe để báo cho ứng dụng biết rằng trạng thái có thể đã thay đổi, và tầng ứng dụng nên tự xử lý tiếp.

func (ck *Clerk) Put(key, value string, version rpc.Tversion) rpc.Err {
	args := rpc.PutArgs{Key: key, Value: value, Version: version}
	reply := rpc.PutReply{}
	// Sử dụng một biến đếm để theo dõi số lần gửi lại.
	retries := 0
	for {
		ok := ck.clnt.Call(ck.server, "KVServer.Put", &args, &reply)
		if ok {
			// Đã nhận được phản hồi từ server.

			// Đây là logic quan trọng nhất:
			// Nếu đây là một lần gửi lại (retries > 0) VÀ server trả về ErrVersion,
			// chúng ta rơi vào kịch bản không chắc chắn.
			if retries > 0 && reply.Err == rpc.ErrVersion {
				return rpc.ErrMaybe
			}

			// Trong mọi trường hợp khác, phản hồi của server là rõ ràng và đáng tin cậy
			// (ví dụ: OK, hoặc ErrVersion trong lần gửi đầu tiên).
			return reply.Err
		}
		// Không nhận được phản hồi (lỗi mạng), tăng biến đếm và thử lại.
		retries++
		time.Sleep(100 * time.Millisecond)
	}
}

Với sự kết hợp giữa sync.Mutex ở server và chế kiểm tra phiên bản (version checking), hệ thống K/V của chúng ta đã hoàn thiện. Nó không chỉ đảm bảo an toàn truy cập đồng thời mà còn cung cấp ngữ nghĩa at-most-once mạnh mẽ, giúp hệ thống hoạt động đáng tin cậy ngay cả khi đối mặt với lỗi mạng.

Nền tảng vững chắc này đã sẵn sàng để chúng ta xây dựng các ứng dụng phức tạp hơn ở phần tiếp theo.

Phần 2: Xây dựng Khóa Phân tán (Distributed Lock)

Giờ đây, khi đã xây dựng xong một K/V store với tính chất at-most-once đáng tin cậy, chúng ta có thể sử dụng nó làm nền để triển khai một tính năng cao cấp hơn và cực kỳ quan trọng trong các hệ thống phân tán: khóa phân tán (distributed lock).

Mục tiêu của phần này là xây dựng một client có thể thực hiện hai thao tác:

Acquire: giành quyền sở hữu khóa.
Release: nhả khóa ra khi không còn sử dụng.

Hệ thống cần đảm bảo các thao tác này diễn ra chính xác, ngay cả khi có nhiều client cùng tranh giành khóa, và đặc biệt phải chịu lỗi tốt trong môi trường mạng không ổn định — một đặc điểm phổ biến của các hệ thống phân tán thực tế.

1. Yêu cầu chức năng

Để đảm bảo hoạt động an toàn trong môi trường phân tán, một cơ chế khóa phân tán cần thỏa mãn các tiêu chí sau:

1.1. Loại trừ tương hỗ (Mutual Exclusion)

Chỉ một client duy nhất được giữ khóa tại một thời điểm. Điều này giúp ngăn chặn tình trạng nhiều client truy cập đồng thời vào cùng một tài nguyên, từ đó tránh xung đột và lỗi dữ liệu (race condition).

1.2. API rõ ràng: `Acquire` và `Release`

Acquire(): Được gọi khi client muốn giữ khóa. Nếu khóa đang trống, client sẽ lấy được ngay. Nếu đã có client khác giữ khóa, lệnh này sẽ chờ (block) cho đến khi khóa được nhả ra.
Release(): Được gọi để nhả khóa mà client đang giữ, tạo cơ hội cho client khác tiếp quản.

1.3. Chống chịu lỗi (Fault Tolerance)

Cơ chế khóa phải hoạt động đúng ngay cả khi mạng không ổn định — nơi các gói tin RPC có thể bị mất hoặc trễ. Do đó, cả Acquire và Release cần được thiết kế để xử lý việc gửi lại (retry) mà không làm hỏng trạng thái khóa.

1.4. Không xảy ra deadlock (Deadlock Freedom)

Hệ thống phải đảm bảo rằng nếu client giữ khóa cuối cùng cũng nhả nó ra, thì các client khác sẽ cuối cùng giành được quyền truy cập. Không để tình trạng “chờ mãi không đến lượt” xảy ra.

2. Phân tích các kịch bản kiểm thử

Để đảm bảo khóa phân tán của chúng ta hoạt động đúng đắn trong mọi tình huống, bộ kiểm thử được chia thành các kịch bản sau, mỗi kịch bản tập trung vào một khía cạnh khác nhau:

TestOneClientReliable (Kiểm tra cơ bản trên mạng ổn định):
- Mục tiêu: Đây là bài kiểm tra “sanity check” đơn giản nhất, xác minh rằng một client duy nhất có thể Acquire và Release khóa một cách chính xác trong điều kiện mạng lý tưởng.
- Kịch bản: Một client gọi Acquire(), sau đó gọi Release(). Bài test đảm bảo các thao tác cơ bản hoạt động như mong đợi.
TestManyClientsReliable (Kiểm tra tranh chấp trên mạng ổn định):
- Mục tiêu: Xác minh tính đúng đắn của cơ chế loại trừ tương hỗ (mutual exclusion) khi có nhiều client cùng tranh giành khóa.
- Kịch bản: Nhiều client đồng thời gọi Acquire(). Bài test sẽ thất bại nếu có nhiều hơn một client vào được vùng tranh chấp (critical section) tại cùng một thời điểm.
TestOneClientUnreliable (Kiểm tra khả năng chịu lỗi của một client):
- Mục tiêu: Đảm bảo các thao tác Acquire và Release có khả năng phục hồi sau lỗi mạng.
- Kịch bản: Một client duy nhất thực hiện Acquire và Release trên một mạng không ổn định, nơi các gói tin RPC có thể bị mất. Bài test kiểm tra xem client có thể xử lý việc gửi lại (retry) một cách an toàn hay không.
TestManyClientsUnreliable (Tranh chấp trên mạng không ổn định):
- Mục-tiêu: Đây là bài kiểm tra khó nhất, kết hợp cả hai thử thách: tranh chấp đồng thời và lỗi mạng.
- Kịch bản: Nhiều client cùng tranh giành khóa trên một mạng không ổn định. Bài test này đảm bảo rằng việc triển khai của chúng ta đủ mạnh mẽ để duy trì tính đúng đắn trong những điều kiện khó khăn nhất.

3. Cách triển khai Distributed Lock: Dựa trên “test-and-set” spinlock

Chúng ta sẽ xây dựng cơ chế khóa phân tán bằng một chiến lược kinh điển và hiệu quả: “test-and-set” spinlock. Ý tưởng cốt lõi là client sẽ liên tục kiểm tra (test) trạng thái của khóa và cố gắng chiếm lấy nó (set) cho đến khi thành công.

Quy ước trạng thái khóa trên K/V Store: Để biểu diễn trạng thái của khóa, chúng ta sẽ sử dụng một key duy nhất trong K/V store:

Khóa rảnh (Unlocked): Giá trị của key là một chuỗi rỗng ("").
Khóa đã bị chiếm (Locked): Giá trị của key là một ID định danh duy nhất của client đang giữ khóa.

Cách hoạt động của các thao tác

Acquire: Khi muốn giành khóa, client sẽ gửi một yêu cầu Put có điều kiện — chỉ thực hiện nếu giá trị hiện tại của key là "". Nếu điều kiện đúng, server sẽ cập nhật giá trị thành ID của client. Nếu không, client sẽ phải thử lại sau.
Release: Khi không còn cần giữ khóa, client sẽ gửi một lệnh Put khác để đặt giá trị của key trở lại "", trả khóa về trạng thái rảnh cho client khác sử dụng.

3.1. `MakeLock` - Khởi tạo Client Lock Handle

Hàm MakeLock không trực tiếp tạo khóa trên server, mà tạo ra một handle phía client — một đối tượng đại diện cho khóa, cho phép client tương tác với nó (giành và nhả khóa).

Mỗi handle bao gồm:

clerk – đối tượng dùng để gửi yêu cầu RPC đến K/V server.
key – tên của khóa, được lưu dưới dạng một key trong K/V store.
value (ID định danh) – một chuỗi ngẫu nhiên, duy nhất cho mỗi client. Đây là cách để xác định client nào đang giữ khóa. ID này rất quan trọng cho việc xác thực trong thao tác Release.

Khi được gọi, MakeLock sẽ cố gắng khởi tạo khóa trên server bằng cách đặt giá trị của key thành chuỗi rỗng ("") — thể hiện trạng thái “chưa bị chiếm”. Việc này được thực hiện thông qua một thao tác Put có điều kiện với version = 0. Nghĩa là thao tác chỉ thành công nếu key chưa tồn tại.

Nếu key đã được khởi tạo trước bởi một client khác (tức là server trả về lỗi ErrVersion), thì không sao — điều đó có nghĩa là khóa đã tồn tại, và handle vẫn có thể sử dụng bình thường.

src/kvsrv1/lock/lock.go

package lock

import (
	"time"
	"6.5840/kvsrv1/rpc"
	kvtest "6.5840/kvtest1"
)

type Lock struct {
	ck    kvtest.IKVClerk
	key   string // Key trong kho k/v đại diện cho khóa.
	value string // ID duy nhất của client này, dùng để "ký tên" khi giữ khóa.
}

// MakeLock tạo một "tay cầm" (handle) cho khóa mới ở phía client.
// Nó cũng đảm bảo rằng key của khóa đã được khởi tạo trên K/V store.
func MakeLock(ck kvtest.IKVClerk, l string) *Lock {
	lk := &Lock{
		ck:    ck,
		key:   l,
		value: kvtest.RandValue(8), // Một ID duy nhất cho "tay cầm" khóa của client này.
	}

	// Cố gắng khởi tạo key của khóa trên store.
	// Vòng lặp này đảm bảo thao tác có thể vượt qua các lỗi mạng tạm thời.
	for {
		// Đầu tiên, kiểm tra xem key đã tồn tại chưa.
		_, _, err := ck.Get(l)
		if err == rpc.ErrNoKey {
			// Key chưa tồn tại, thử tạo nó với trạng thái "rảnh" (giá trị rỗng, phiên bản 0).
			err = ck.Put(l, "", 0)
			if err == rpc.OK || err == rpc.ErrVersion {
				// Nếu thành công (OK), hoặc nếu một client khác đã tạo nó ngay trước chúng ta (ErrVersion),
				// thì mục tiêu đã đạt được.
				break
			}
		} else if err == rpc.OK {
			// Key đã tồn tại, không cần làm gì thêm.
			break
		}
		// Nếu gặp ErrMaybe hoặc các lỗi mạng khác, đợi một chút rồi thử lại.
		time.Sleep(10 * time.Millisecond)
	}

	return lk
}

3.2. Hàm `Acquire`: Giành lấy khóa theo cơ chế “test-and-set”

Hàm Acquire triển khai cơ chế spinlock, nơi client sẽ lặp lại việc kiểm tra và cố gắng chiếm khóa cho đến khi thành công. Đây là một hàm blocking - chỉ trả về khi client chắc chắn đã nắm giữ khóa.

Trong mỗi vòng lặp for, client thực hiện hai bước chính:

Kiểm tra (Test): Gọi Get để lấy giá trị hiện tại và phiên bản của key đại diện cho khóa.
Thiết lập (Set): Tùy vào trạng thái đọc được, quyết định có nên cố gắng chiếm khóa không.

Có hai tình huống chính:

Khóa đang rảnh (state == ""): Đây là thời điểm để giành quyền sở hữu. Client sẽ dùng Put có điều kiện để thay giá trị từ "" thành lk.value. Nếu phiên bản không bị thay đổi kể từ lần Get trước, thao tác sẽ thành công và client đã giữ được khóa. Nếu thất bại (do race với client khác), vòng lặp sẽ tiếp tục thử lại.
Client đã giữ khóa (state == lk.value): Trường hợp này xảy ra nếu lần gọi Acquire trước đã thành công nhưng phản hồi bị mất (ví dụ: do lỗi mạng). Vì vậy, client có thể yên tâm kết luận rằng mình vẫn đang giữ khóa và trả về thành công. Đây là cách đảm bảo tính idempotent cho Acquire.

src/kvsrv1/lock/lock.go

// Acquire giành lấy khóa.
// Hàm này sẽ block cho đến khi khóa được giành thành công.
func (lk *Lock) Acquire() {
	// Vòng lặp vô hạn để thử lại cho đến khi thành công (spinlock).
	for {
		// --- Giai đoạn Test: Đọc trạng thái hiện tại của khóa ---
		state, version, err := lk.ck.Get(lk.key)

		if err == rpc.OK {
			if state == "" {
				// --- Giai đoạn Set: Khóa đang rảnh, cố gắng chiếm lấy ---
				// Thao tác Put có điều kiện này là nguyên tử.
				putErr := lk.ck.Put(lk.key, lk.value, version)
				if putErr == rpc.OK {
					// Thành công! Chúng ta đã giành được khóa.
					return
				}
				// Nếu putErr là ErrVersion, có nghĩa là một client khác đã thắng cuộc đua.
				// Nếu là ErrMaybe, chúng ta không chắc chắn, nhưng vòng lặp tiếp theo sẽ làm rõ.
				// Trong cả hai trường hợp, chúng ta chỉ cần lặp lại.

			} else if state == lk.value {
				// Chúng ta đã là người giữ khóa. Điều này có thể xảy ra nếu phản hồi của
				// lần Acquire thành công trước đó bị mất. Chỉ cần trả về.
				return
			}
		}
		
		// Đợi một chút trước khi thử lại để tránh làm quá tải server.
		time.Sleep(10 * time.Millisecond)
	}
}

Triển khai này mang lại độ tin cậy cao. Nó không chỉ xử lý hiệu quả tình huống nhiều client cạnh tranh để giành khóa (race condition), mà còn đảm bảo rằng client có thể xác nhận lại quyền sở hữu của mình trong trường hợp xảy ra lỗi mạng. Nhờ cơ chế kiểm tra và thiết lập có điều kiện, logic này đủ mạnh để vượt qua toàn bộ các bài kiểm thử - từ những tình huống đơn giản đến các kịch bản phức tạp nhất.

3.3. `Release` – Trả khóa một cách an toàn và idempotent

Việc trả khóa cần được thiết kế cẩn thận để tránh các lỗi khó lường. Nguyên tắc vàng là: một client chỉ được phép trả khóa khi nó thực sự đang giữ khóa đó. Điều này giúp ngăn một yêu cầu Release bị trễ (do lỗi mạng) vô tình làm mất quyền sở hữu của một client khác đã giành được khóa sau đó.

Logic của Release cũng theo mô hình “test-and-set”:

Test: Dùng Get để kiểm tra xem ai đang giữ khóa hiện tại.
Set: Nếu người giữ khóa là chính chúng ta (state == lk.value), thì thực hiện Put có điều kiện để đặt giá trị về "". Nếu không phải, không làm gì cả.

src/kvsrv1/lock/lock.go

func (lk *Lock) Release() {
	for {
		state, version, err := lk.ck.Get(lk.key)

		// Chúng ta chỉ giải phóng khóa nếu chúng ta là người giữ hiện tại.
		if err == rpc.OK && state == lk.value {
			// Cố gắng đặt lại khóa thành "" (rảnh).
			putErr := lk.ck.Put(lk.key, "", version)
			if putErr == rpc.OK || putErr == rpc.ErrVersion {
				// Thành công, hoặc ai đó khác đã lấy khóa sau chúng ta.
				// Trong cả hai trường hợp, chúng ta không còn là người giữ, vì vậy công việc của chúng ta đã xong.
				return
			}
			// Nếu putErr là ErrMaybe, lặp lại và thử lại để đảm bảo giải phóng.
		} else if err == rpc.OK {
			// Chúng ta không phải là người giữ, vì vậy không có gì để làm.
			return
		}

		// Khi có lỗi Get, đợi và thử lại.
		time.Sleep(10 * time.Millisecond)
	}
}

Triển khai này đảm bảo độ an toàn cao. Nó ngăn chặn tình huống một client vô tình giải phóng sai một khóa mà một client khác đã chiếm được - một lỗi có thể xảy ra nếu có sự chậm trễ hoặc mất gói tin trong mạng. Nhờ được xây dựng trên nền tảng các thao tác Get và Put có khả năng xử lý lỗi tốt, logic Release hoạt động cho tất cả các trường hợp kiểm thử, bao gồm cả những trường hợp không đáng tin cậy.

Lời kết

Qua bài viết này, chúng ta đã cùng nhau tìm hiểu và triển khai một hệ thống key-value đơn giản, có khả năng chịu lỗi và đảm bảo tính nhất quán tuyến tính - nền tảng để xây dựng các cơ chế đồng bộ hóa trong hệ thống phân tán. Dựa trên đó, bài lab đã mở rộng thành cơ chế khóa phân tán - một ví dụ cụ thể của việc xây dựng tính đồng bộ trong môi trường không tin cậy.

Những điểm chính cần rút ra là:

Thiết kế đúng các thao tác cơ bản: Ngay cả những thao tác đơn giản như Put có điều kiện, nếu được xây dựng chính xác, cũng có thể trở thành nền tảng vững chắc cho các cơ chế đồng bộ hóa phức tạp hơn sau này.
Phân tách rõ ràng giữa các tầng hệ thống: Việc xử lý lỗi và cơ chế thử lại (retry) được đặt ở tầng client giúp hệ thống tổng thể đơn giản, dễ bảo trì, đồng thời vẫn đảm bảo tính đúng đắn khi có lỗi mạng xảy ra.
Tư duy idempotent để tăng khả năng chịu lỗi: Thiết kế các thao tác sao cho có thể thực thi lại nhiều lần mà không gây ra tác dụng phụ là cách hiệu quả để đảm bảo hệ thống hoạt động ổn định trong môi trường phân tán, nơi các lỗi như timeout hay retry là điều tất yếu.

Các thành phần đã xây dựng trong lab này sẽ được mở rộng trong Lab 3, nơi hệ thống chuyển sang mô hình nhiều node và sử dụng thuật toán đồng thuận Raft để đảm bảo tính nhất quán. Những nguyên tắc thiết kế đã được áp dụng tại đây sẽ đóng vai trò làm nền tảng vững chắc cho việc phát triển các hệ thống phân tán có khả năng chịu lỗi và hoạt động ổn định trong môi trường thực tế.

Linearizability là gì?

1. Tình huống giả định

2. Phân tích tình huống

Kịch bản 1: Các thao tác diễn ra không đồng thời

Kịch bản 2: Các thao tác đồng thời

Phần 1: Key/Value server với tính nhất quán tuyến tính (linearizability)

1. Yêu cầu chức năng

1.1. Mục tiêu chính

1.2. Quy tắc xử lý thao tác Put

1.3. Mạng không tin cậy và cách xử lý

2. Hiểu cách hệ thống được kiểm chứng qua các test cases

3. Giải thích các mã lỗi sử dụng trong bài lab

4. Triển khai

4.1. Thiết kế cấu trúc dữ liệu cho Server

4.2. Triển khai thao tác Get

Phía Server: Xử lý yêu cầu Get một cách an toàn

Phía Client: Gọi và xử lý Get với cơ chế retry

4.3. Triển khai Put có điều kiện để đảm bảo At-Most-Once

a) Phía Server: Logic Put có điều kiện

b) Phía Client: Xử lý sự không chắc chắn với ErrMaybe

Phần 2: Xây dựng Khóa Phân tán (Distributed Lock)

1. Yêu cầu chức năng

1.1. Loại trừ tương hỗ (Mutual Exclusion)

1.2. API rõ ràng: Acquire và Release

1.3. Chống chịu lỗi (Fault Tolerance)

1.4. Không xảy ra deadlock (Deadlock Freedom)

2. Phân tích các kịch bản kiểm thử

3. Cách triển khai Distributed Lock: Dựa trên “test-and-set” spinlock

3.1. MakeLock - Khởi tạo Client Lock Handle

3.2. Hàm Acquire: Giành lấy khóa theo cơ chế “test-and-set”

3.3. Release – Trả khóa một cách an toàn và idempotent

Lời kết

b) Phía Client: Xử lý sự không chắc chắn với `ErrMaybe`

1.2. API rõ ràng: `Acquire` và `Release`

3.1. `MakeLock` - Khởi tạo Client Lock Handle

3.2. Hàm `Acquire`: Giành lấy khóa theo cơ chế “test-and-set”

3.3. `Release` – Trả khóa một cách an toàn và idempotent