Khóa, mutex và cấu trúc dữ liệu lock-free

Lỗi đồng thời bắt đầu khi một thao tác trông như không thể chia nhỏ trong mã nguồn lại trở thành nhiều hành động ở cấp máy. Với balance += amount, bộ xử lý phải đọc balance, tính giá trị mới rồi ghi lại. Nếu hai luồng xen kẽ các bước này, cả hai có thể cùng đọc một giá trị cũ và một lần cập nhật sẽ biến mất. Phép tính không sai; thứ tự thực thi mới là vấn đề.

Khóa và phép toán nguyên tử đều giới hạn cách các luồng xen kẽ, nhưng chúng đưa ra những cam kết khác nhau. Mutex trao quyền sở hữu độc quyền tạm thời đối với một vùng trạng thái. Compare-and-swap (CAS) chỉ thay đổi một word máy nếu word đó vẫn chứa giá trị mong đợi. Thuật toán lock-free kết hợp các thay đổi có điều kiện như vậy để toàn hệ thống tiếp tục tiến triển ngay cả khi một luồng bị dừng.

Không cơ chế nào tự động nhanh hơn hoặc an toàn hơn. Một trạng thái nhỏ được bảo vệ bằng mutex có thể vừa dễ chứng minh vừa nhanh hơn một vòng lặp CAS tinh vi. Ngược lại, một luồng giữ khóa không đúng lúc có thể chặn mọi luồng còn lại. Câu hỏi hữu ích không phải “khóa có xấu không?”, mà là “hợp đồng đồng bộ nào phù hợp với trạng thái, tải và mô hình lỗi này?”

Race là lỗi về thứ tự, không chỉ về thời điểm #

Data race xảy ra khi nhiều truy cập đồng thời nhắm vào cùng vùng nhớ, có ít nhất một thao tác ghi và các truy cập không được đồng bộ. Trong Rust, mã safe ngăn data race bằng ownership cùng các trait Send và Sync; trong C++, data race trên vùng nhớ thông thường là hành vi không xác định. Race condition rộng hơn: kết quả chương trình phụ thuộc vào một thứ tự kém may mắn, kể cả khi từng truy cập riêng lẻ đều nguyên tử.

Ví dụ, hai phép toán nguyên tử tách rời không biến quy trình kiểm tra-rồi-thực hiện thành một thao tác nguyên tử:

use std::sync::atomic::{AtomicUsize, Ordering};

fn reserve_one(remaining: &AtomicUsize) -> bool {
    let mut observed = remaining.load(Ordering::Relaxed);

    loop {
        if observed == 0 {
            return false;
        }

        match remaining.compare_exchange_weak(
            observed,
            observed - 1,
            Ordering::AcqRel,
            Ordering::Relaxed,
        ) {
            Ok(_) => return true,
            Err(actual) => observed = actual,
        }
    }
}

Nếu dùng một load, một lần kiểm tra rồi một store riêng biệt, hai luồng có thể cùng bán vị trí cuối. Vòng lặp CAS diễn đạt điều kiện chặt hơn: “chỉ ghi observed - 1 nếu chưa ai thay đổi giá trị kể từ lúc tôi quan sát.” compare_exchange_weak được phép thất bại giả, vì vậy nó bắt buộc phải nằm trong vòng lặp. Khi có cập nhật cạnh tranh thật sự, CAS cũng thất bại và trả về giá trị hiện tại cho lần thử tiếp theo.

Tính nguyên tử chỉ giải quyết một phần bài toán. Các luồng còn cần khả năng nhìn thấy và thứ tự bộ nhớ: khi một luồng công bố con trỏ, luồng khác quan sát được con trỏ ấy cũng phải thấy object đã được khởi tạo phía sau nó. Quan hệ đó thuộc về memory model của ngôn ngữ, không phụ thuộc trực giác theo đồng hồ hay việc test đã chạy qua trên một laptop.

Mutex làm cho invariant trở nên tường minh #

Mutex thường là lựa chọn mặc định tốt nhất khi nhiều trường cùng tạo nên một invariant. Thay vì biến từng trường thành atomic rồi suy luận về mọi tổ hợp trạng thái trung gian, hãy đặt toàn bộ trạng thái sau một khóa và cập nhật nó như một transaction.

use std::collections::HashMap;
use std::sync::Mutex;

struct Ledger {
    balances: Mutex<HashMap<String, i64>>,
}

impl Ledger {
    fn transfer(&self, from: &str, to: &str, amount: i64) -> Result<(), &'static str> {
        if amount < 0 {
            return Err("amount must be non-negative");
        }

        let mut balances = self.balances.lock().map_err(|_| "ledger lock poisoned")?;
        let from_balance = *balances.get(from).unwrap_or(&0);
        if from_balance < amount {
            return Err("insufficient funds");
        }

        *balances.entry(from.to_owned()).or_default() -= amount;
        *balances.entry(to.to_owned()).or_default() += amount;
        Ok(())
    }
}

Lifetime của guard xác định critical section, và khi guard bị drop thì mutex được mở ngay cả lúc hàm return sớm. Quan trọng hơn, không observer nào nhìn thấy tiền đã bị trừ khỏi tài khoản nguồn nhưng chưa được cộng vào tài khoản đích. Invariant ấy rõ ràng hơn nhiều so với một cặp số dư atomic.

Hãy giữ critical section có giới hạn: không gọi mạng, chờ nhập liệu hay gọi callback không rõ hành vi trong khi giữ khóa. Có thể xấp xỉ chi phí khóa bằng

Fast path khi không tranh chấp có thể rất nhỏ, nhưng xếp hàng và chuyển giao giữa scheduler sẽ chi phối khi contention cao. Vì thế cần đo tail latency, không chỉ thời gian lấy khóa trung bình.

Khóa tạo ra nhiều rủi ro về liveness:

Deadlock cần bốn điều kiện: loại trừ lẫn nhau, vừa giữ vừa chờ, không thể cưỡng chế thu hồi và chờ theo vòng tròn. Phá vỡ một điều kiện là đủ để ngăn deadlock. Quy ước toàn cục như “luôn lấy khóa tài khoản theo thứ tự ID” thường dễ audit hơn timeout; timeout chỉ phát hiện sự chậm trễ chứ không khôi phục một invariant đang cập nhật dở.

CAS và memory ordering định nghĩa việc công bố dữ liệu #

CAS so sánh một giá trị atomic với giá trị kỳ vọng rồi thay thế có điều kiện trong một thao tác không thể chia nhỏ. Nó là nền móng của counter, state machine, free list và nhiều concurrent queue. Phần khó hiếm khi nằm ở instruction CAS; phần khó là xác định vùng nhớ xung quanh nào được thao tác đó công bố.

Các ordering phổ biến gồm:

Giả sử producer khởi tạo đầy đủ một node rồi lưu con trỏ bằng Release. Consumer đọc con trỏ bằng Acquire. Nếu consumer thấy con trỏ do producer ghi, việc khởi tạo happens-before các lần đọc của consumer. Relaxed đủ cho counter thống kê độc lập, nhưng không đủ để công bố một object có các trường thông thường mà luồng khác sẽ đọc.

Vòng lặp CAS cũng có thuế hiệu năng. Với $N$ contender, một cập nhật thành công có thể làm mất hiệu lực cache line của khoảng $N - 1$ peer. Throughput hữu ích không chỉ bị chặn bởi độ trễ instruction mà còn bởi lưu lượng cache coherence:

Nếu đếm mọi attempt như một operation, retry amplification sẽ bị che khuất. Cần theo dõi riêng số lần thành công, CAS thất bại và các percentile độ trễ.

Stack lock-free vẫn cần thu hồi bộ nhớ an toàn #

Treiber stack biểu diễn stack bằng một con trỏ atomic tới linked list bất biến. Push nối node mới vào head đã quan sát rồi CAS head. Pop đọc head cùng node kế tiếp, sau đó CAS node kế tiếp vào head. Ví dụ Rust gọn dưới đây dùng epoch-based reclamation từ crossbeam-epoch; ràng buộc T: Copy giúp ví dụ tập trung vào đồng bộ thay vì cách chuyển value ra khỏi node đã retire.

use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::sync::atomic::Ordering::{Acquire, AcqRel, Relaxed, Release};

struct Node<T> {
    value: T,
    next: Atomic<Node<T>>,
}

struct Stack<T> {
    head: Atomic<Node<T>>,
}

impl<T: Copy> Stack<T> {
    fn push(&self, value: T) {
        let guard = &epoch::pin();
        let mut new = Owned::new(Node {
            value,
            next: Atomic::null(),
        });

        loop {
            let head = self.head.load(Acquire, guard);
            new.next.store(head, Relaxed);

            match self.head.compare_exchange(head, new, Release, Relaxed, guard) {
                Ok(_) => return,
                Err(error) => new = error.new,
            }
        }
    }

    fn pop(&self) -> Option<T> {
        let guard = &epoch::pin();

        loop {
            let head = self.head.load(Acquire, guard);
            let node = unsafe { head.as_ref()? };
            let next = node.next.load(Relaxed, guard);

            if self
                .head
                .compare_exchange(head, next, AcqRel, Acquire, guard)
                .is_ok()
            {
                let value = node.value;
                unsafe { guard.defer_destroy(head) };
                return Some(value);
            }
        }
    }
}

Đây là lock-free, không phải wait-free. Nếu một luồng dừng giữa push, luồng khác vẫn có thể hoàn tất operation. Tuy vậy, khi contention cao, một luồng kém may mắn có thể thua CAS mãi mãi. Lock-free bảo đảm tiến triển trên toàn hệ thống; wait-free bảo đảm mỗi operation hoàn tất trong một số bước riêng có giới hạn. Obstruction-free yếu hơn: một luồng chỉ chắc chắn hoàn thành nếu cuối cùng nó được chạy mà không bị can thiệp.

Chi tiết nguy hiểm nhất là memory reclamation. Nếu giải phóng ngay một node vừa pop, luồng khác có thể dereference vùng nhớ mà nó đã đọc ngay trước thao tác pop. Epoch pinning thông báo rằng luồng hiện tại có thể vẫn giữ shared pointer. defer_destroy retire node và chỉ hủy nó sau khi không participant nào còn giữ tham chiếu từ epoch cũ.

Reclamation cũng giải quyết bài toán ABA. Một luồng đọc địa chỉ head A rồi tạm dừng. Các luồng khác đổi A thành B, gỡ B, giải phóng A, sau đó cấp phát node mới đúng tại địa chỉ A. CAS chỉ nhìn con trỏ sẽ lại thấy A và kết luận sai rằng không có gì thay đổi. Epoch reclamation không cho tái sử dụng vùng nhớ của A khi luồng đang dừng vẫn còn pin. Các chiến lược khác gồm hazard pointer, con trỏ gắn tag/version, reference counting và garbage collection. Mỗi cách thay đổi chi phí bộ nhớ, độ trễ và độ phức tạp triển khai.

Lock-free không có nghĩa mọi tầng đều không dùng khóa. Allocator, epoch manager hoặc kiểu atomic có thể đồng bộ nội bộ; không phải target nào cũng hỗ trợ mọi độ rộng atomic mà không có fallback. Cần kiểm tra bảo đảm nền tảng như is_lock_free, tài liệu thư viện và hành vi sinh mã trên kiến trúc triển khai thật.

Contention, kiểm thử và quyết định kỹ thuật #

Lựa chọn đồng bộ phải đi theo hình dạng shared state và contention đã đo. Chia một map thành nhiều shard có mutex thường hiệu quả hơn thay nó bằng bảng lock-free tự viết. Counter riêng theo luồng rồi tổng hợp định kỳ tránh được một cache line atomic nóng. Message passing có thể trao quyền sở hữu độc quyền cho một task và loại bỏ hoàn toàn shared mutation. Giảm nhu cầu đồng bộ thường giá trị hơn tối ưu primitive.

Cần kiểm thử cả safety lẫn liveness. Unit test trước hết xác nhận semantics tuần tự. Stress test sau đó chạy nhiều operation ngẫu nhiên, dùng barrier để ép các luồng bắt đầu đồng thời, capacity nhỏ để gây wraparound và thời lượng đủ dài nhằm lộ schedule hiếm. Với queue, stack hoặc register, hãy ghi lịch sử operation và kiểm tra linearizability: mỗi kết quả phải khớp với một thứ tự tuần tự hợp lệ nằm giữa thời điểm gọi và trả về của operation đó.

Thread sanitizer bắt data race trong các native build được hỗ trợ, còn công cụ như Loom duyệt các interleaving Rust hữu hạn bằng atomic và primitive đồng bộ đã instrument. Không công cụ nào chứng minh được chương trình production tùy ý. Hãy thêm watchdog phát hiện tiến triển bị dừng, chạy trên phần cứng weakly ordered khi phù hợp, chèn pause giữa load và CAS, đồng thời test đường shutdown và cancellation. Benchmark phải thay đổi số luồng, tỷ lệ đọc/ghi, preemption, vị trí NUMA và lượng công việc thực tế bên trong critical section.

Một buổi review thực tế cần hỏi: Invariant nào được bảo vệ? Linearization point ở đâu? Operation nào công bố dữ liệu? Một luồng có thể block không, và khi đó đang giữ gì? Ai thu hồi vùng nhớ đã gỡ? Sản phẩm thật sự cần progress guarantee nào? Điều gì xảy ra khi cancellation, panic hoặc overload? Nếu câu trả lời còn mơ hồ, benchmark đẹp chưa phải bằng chứng đủ để phát hành thuật toán.

Điều cần ghi nhớ #

• Race là lỗi về thứ tự. Atomic ngăn truy cập xung đột hoặc bị xé, nhưng invariant ghép vẫn cần một protocol rõ ràng.
• Mutex là mặc định vững chắc cho trạng thái liên quan: giữ critical section ngắn, thiết lập thứ tự khóa, đồng thời tính đến deadlock, livelock và starvation.
• Ordering acquire/release nối việc công bố với quan sát; Relaxed chỉ phù hợp khi không cần quan hệ với vùng nhớ xung quanh.
• Lock-free nghĩa là luôn có một operation tiến triển; wait-free nghĩa là mọi operation hoàn tất trong số bước riêng có giới hạn.
• Container dựa trên CAS chưa hoàn chỉnh nếu thiếu chiến lược chống ABA và reclamation như epoch hoặc hazard pointer.
• Hãy tối ưu mô hình ownership và topology contention trước khi thay một khóa rõ ràng bằng thuật toán non-blocking khó hiểu, rồi kiểm chứng safety lẫn liveness dưới các schedule bất lợi.