Vector clock nhận ra hai lần ghi độc lập về nhân quả

Hai người sửa một danh sách mua sắm cũ. Một người xóa sữa; người kia thêm bánh mì nhưng vẫn giữ sữa. Khi hai phiên bản gặp nhau, so sánh một timestamp đơn lẻ không cho biết lần sửa này đã biết về lần sửa kia chưa. Vector clock giữ tiến độ riêng cho từng bên ghi, giúp hệ thống nhận ra hai nhánh nhân quả và giữ cả hai để đưa ra quyết định.

Bài này dành cho bạn nếu đã hiểu tuple và tập hợp trong Python. Ta sẽ dùng ba bên ghi cố định, so sánh từng thành phần của vector và chạy một ví dụ món đã xóa xuất hiện lại khi lấy hợp hai tập hợp. Đây là mô hình lịch sử phiên bản giả định trong một tiến trình Python. Nó không chạy Dynamo, không trao đổi gói tin mạng và không triển khai đầy đủ một danh sách mua sắm được sao chép.

Vector tóm tắt một đoạn đầu lịch sử của mỗi bên ghi

Gán vị trí cố định cho A, B và C. Phiên bản mang (1, 2, 0) biết lần ghi đầu của A và hai lần ghi đầu của B, nhưng chưa biết lần ghi nào của C. Cách hiểu này giả định mỗi định danh chỉ có một bên ghi hoạt động tuần tự, bộ đếm tăng đơn điệu, ngữ cảnh đã quan sát được truyền đầy đủ và không thành phần nào bị mất. Mỗi thành phần là số lần ghi trong mô hình, không phải thời gian vật lý hay số lượng món hàng.

Ta đang theo dõi những phiên bản do thao tác ghi tạo ra. Quan sát một phiên bản sẽ gộp ngữ cảnh của nó vào hiểu biết của bên nhận, nhưng không tạo phiên bản đối tượng mới hay tăng bộ đếm. Lần ghi tiếp theo mới tăng thành phần của chính bên ghi đó. Mô hình vector clock gán timestamp cho mọi sự kiện nhận dùng một quy ước sự kiện khác; đừng tự thêm phép tăng tại sự kiện nhận vào các tính toán dưới đây.

Với hai vector, trước tiên kiểm tra bằng nhau. Nếu khác nhau, phiên bản bên trái đứng trước bên phải khi mọi thành phần bên trái đều nhỏ hơn hoặc bằng thành phần tương ứng. Khi đó phải có ít nhất một thành phần nhỏ hơn nghiêm ngặt. Đảo chiều kiểm tra để xác định đứng sau. Nếu cả hai chiều đều không thỏa, các phiên bản là concurrent: mỗi bên chứa một lần ghi không có trong lịch sử nhân quả của bên còn lại.

Phép so sánh tuple thông thường của Python không phù hợp. Nó so theo thứ tự từ điển và dừng ở thành phần khác nhau đầu tiên. Nó sẽ xếp (1, 1, 0) lớn hơn (1, 0, 1), dù vector đầu lớn hơn ở B nhưng nhỏ hơn ở C. Thứ tự toàn phần nhất quán cho các tuple không phải thứ tự bộ phận theo từng thành phần mà ta cần ở đây.

Làm rõ hai nhánh phiên bản

A ghi danh sách ban đầu có sữa, tạo (1, 0, 0). B và C cùng quan sát phiên bản đó. B xóa sữa và ghi danh sách rỗng, tạo (1, 1, 0). C thêm bánh mì vào danh sách cũ rồi ghi sữa cùng bánh mì, tạo (1, 0, 1). Chưa bên nào quan sát phiên bản mới của bên kia.

Mở ảnh kích thước đầy đủ ↗

Cả hai phiên bản mới đều là hậu duệ của phiên bản ban đầu: mọi thành phần của (1, 0, 0) không lớn hơn thành phần tương ứng trong mỗi vector mới. Nhưng hai vector mới không so sánh được với nhau. Hai phép so sánh ngược chiều tại B và C trên biểu đồ chính là bằng chứng. Lời gọi hàm nào chạy trước trong script tập trung cũng không tạo thêm cạnh quan sát giữa hai bên ghi.

Bài báo Dynamo năm 2007, mục 4.4 “Data Versioning”, mô tả phiên bản đối tượng bất biến, phép so vector clock và ngữ cảnh trả về cho client khi cần đối soát các nhánh. Bài báo phân biệt việc xác định hậu duệ với việc chọn ý nghĩa của phép gộp. Ba bên ghi cố định giúp ta tính được sự khác biệt này mà không phải dựng lại cơ chế định tuyến, quorum hay lưu bền của Dynamo.

Triển khai nhỏ với điều kiện định danh rõ ràng

Mã dùng Version bất biến, chứa đồng hồ ba số nguyên và frozenset tên món. Hàm so sánh chỉ nhận tuple ba thành phần là số nguyên dựng sẵn không âm; boolean không được dùng làm bộ đếm. Vị trí của bên ghi là các số nguyên 0, 1 và 2. Script gọi các thao tác trên mỗi bên ghi theo thứ tự tuần tự.

Trong một lần chạy, chỉ dùng một đối tượng Writer cho mỗi tác nhân, giữ nó suốt lần chạy đó và chỉ đưa phiên bản thật của lần chạy ấy vào observe. Lớp này không cấp định danh duy nhất trên toàn hệ thống, không lưu bền bộ đếm và không xác thực lịch sử nhận vào. Python cho phép tạo một Writer khác với số tác nhân đã dùng, nhưng hành động đó vi phạm điều kiện định danh của mô hình nhân quả.

Phương thức write nhận một iterable hữu hạn gồm các chuỗi dựng sẵn không rỗng. Nó duyệt iterable một lần để tạo frozenset; tên món trùng nhau được gộp, còn iterator rỗng tạo giá trị danh sách rỗng. Truyền thẳng một chuỗi hoặc đối tượng bytes sẽ bị từ chối, tránh biến nó thành tập hợp các ký tự riêng lẻ. Toàn bộ kiểm tra hoàn tất trước khi đồng hồ của bên ghi đổi giá trị. Ví dụ giữ toàn bộ nội dung trong bộ nhớ, không phải triển khai xử lý luồng có bộ nhớ giới hạn.

from dataclasses import dataclass


def check_vector(vector):
    if type(vector) is not tuple or len(vector) != 3:
        raise TypeError('a clock is a three-component tuple')
    if any(type(x) is not int or x < 0 for x in vector):
        raise ValueError('clock components are nonnegative built-in integers')


def relation(left, right):
    check_vector(left)
    check_vector(right)
    if left == right:
        return 'equal'
    if all(a <= b for a, b in zip(left, right)):
        return 'before'
    if all(b <= a for a, b in zip(left, right)):
        return 'after'
    return 'concurrent'


@dataclass(frozen=True)
class Version:
    clock: tuple
    items: frozenset

    def __post_init__(self):
        check_vector(self.clock)
        if type(self.items) is not frozenset:
            raise TypeError('items must be a frozenset')
        if any(type(item) is not str or not item for item in self.items):
            raise TypeError('item names must be nonempty built-in strings')


class Writer:
    def __init__(self, actor):
        if type(actor) is not int or not 0 <= actor < 3:
            raise ValueError('actor must be 0, 1 or 2')
        self.actor = actor
        self.clock = (0, 0, 0)

    def observe(self, version):
        if type(version) is not Version:
            raise TypeError('observe expects a Version')
        self.clock = tuple(max(a, b) for a, b in zip(self.clock, version.clock))

    def write(self, items):
        if isinstance(items, (str, bytes)):
            raise TypeError('provide a finite iterable of item names')
        next_clock = list(self.clock)
        next_clock[self.actor] += 1
        version = Version(tuple(next_clock), frozenset(items))
        self.clock = version.clock
        return version

Một cách kiểm tra phép so sánh là hình dung các định danh lần ghi tường minh: A1, A2, B1 và tiếp tục như vậy. Một vector mở rộng thành tập hợp chứa đoạn đầu các lần ghi của mỗi tác nhân. Quan hệ chi phối theo từng thành phần tương ứng với quan hệ bao hàm giữa các tập hợp. Quan sát ngữ cảnh lấy hợp các đoạn đầu đã biết, vì thế lấy giá trị lớn nhất theo từng thành phần là đủ. Sau đó, một lần ghi tạo thêm định danh mới tại tác nhân của mình và ghi nhận nó cùng lịch sử đã biết.

Với các điều kiện định danh cố định đã nêu, cách hiểu này giải thích cả hai chiều của phép kiểm tra nhân quả cho những phiên bản được tạo ra. Định danh trong lịch sử tiền nhiệm nhân quả nằm trong lịch sử hậu duệ. Nếu toàn bộ lịch sử của một phiên bản nằm trong lịch sử phiên bản khác, định danh lần ghi tạo ra phiên bản đầu cũng nằm trong đó. Vì vậy phiên bản sau đã biết lần ghi trước. Lập luận này không cho phép ta tin các bản ghi giả mạo hay lịch sử đã bị bỏ bớt thành phần.

Gộp ngữ cảnh khác với chọn nội dung

Khi A quan sát cả hai nhánh, đồng hồ của nó trở thành giá trị lớn nhất theo từng thành phần: (1, 1, 1). Đây là ngữ cảnh đã gộp. A chưa ghi danh sách mua sắm mới. Sau khi ứng dụng chọn nội dung, lần ghi tiếp theo của A tăng thành phần riêng và tạo (2, 1, 1).

Thêm ca sau vào triển khai. Lần chạy đầu chọn phép hợp tập hợp. Đối tượng A thứ hai là một lần chạy thay thế độc lập bắt đầu từ cùng hai nhánh đã quan sát; nó không phải bên thứ hai đang đồng thời sở hữu định danh A.

A, B, C = [Writer(i) for i in range(3)]
base = A.write(['milk'])
B.observe(base)
C.observe(base)
removed = B.write([])
added = C.write(['milk', 'bread'])
assert base.clock == (1, 0, 0)
assert removed.clock == (1, 1, 0)
assert added.clock == (1, 0, 1)
assert relation(removed.clock, added.clock) == 'concurrent'
assert relation(base.clock, removed.clock) == 'before'
assert relation(base.clock, added.clock) == 'before'
A.observe(removed)
A.observe(added)
joined_context = A.clock
assert joined_context == (1, 1, 1)
union_result = A.write(removed.items | added.items)
assert union_result.clock == (2, 1, 1)
assert relation(removed.clock, union_result.clock) == 'before'
assert relation(added.clock, union_result.clock) == 'before'
print('remove:', removed.clock, sorted(removed.items))
print('add:', added.clock, sorted(added.items))
print('relation:', relation(removed.clock, added.clock))
print('joined context:', joined_context)
print('union write:', union_result.clock, sorted(union_result.items))
assert 'milk' in union_result.items

# Same observed branches, a different explicit value decision.
A2 = Writer(0)  # Independent alternative run; not another live actor A.
A2.observe(removed)
A2.observe(added)
resolved = A2.write(['bread'])
assert resolved.clock == union_result.clock
assert resolved.items != union_result.items
print('alternative write:', resolved.clock, sorted(resolved.items))

Kết quả lấy hợp chứa sữa. Danh sách rỗng của B không có phần tử nào có thể loại sữa khỏi phiên bản của C. Vector clock nhận ra các nhánh đã tách; nó không mã hóa quy tắc rằng sự vắng mặt nào phải thắng sự hiện diện nào. Sữa xuất hiện lại là hệ quả của chính sách chọn nội dung, không phải lỗi nhận diện concurrency.

Mở ảnh kích thước đầy đủ ↗

Mục 4.4 của Dynamo nêu rõ rằng cách đối soát giỏ hàng có thể giữ thao tác thêm trong khi cho phép món đã xóa xuất hiện lại. Ví dụ ngữ cảnh và Hình 3 trong bài báo cũng cho thấy vì sao lần ghi sau đối soát phải mang hiểu biết về cả hai nhánh. Phương án chỉ giữ bánh mì ở đây đại diện cho quyết định rõ ràng của ứng dụng hoặc người dùng. Nó không phải thuật toán xử lý xóa tự động do vector cung cấp.

Hai lần chạy thay thế tạo cùng vector nhưng khác nội dung. Chúng thuộc các lần chạy khác nhau, nên đây không phải va chạm trong một lịch sử thỏa điều kiện mỗi tác nhân chỉ có một bên ghi. Nó cho thấy vector không phải hash nội dung. Trong một lần chạy hợp lệ, đồng hồ bằng nhau có thể đi kèm bản sao trùng của một phiên bản. Nếu hai giá trị không tương thích cùng khai báo một đồng hồ, cần kiểm tra việc dùng lại định danh, đặt lại bộ đếm, ngữ cảnh hỏng hoặc giả định bị phá vỡ, thay vì âm thầm xem chúng là dữ liệu tương đương.

Giữ phần ngữ cảnh làm cho phép so sánh có nghĩa

Metadata có chi phí lưu trữ. Mô hình chỉ dùng ba thành phần vì tập thành viên cố định. Nếu có nhiều bên ghi mang định danh độc lập, metadata có thể tăng; phép so và phép gộp phải xét các thành phần liên quan. Điền 0 cho một thành phần vắng mặt là hợp lệ khi ngữ cảnh đang biểu diễn thực sự chưa biết lịch sử của tác nhân ấy. Đó không phải cách vô hại để quên một thành phần từng hiện diện.

Dynamo bàn về cách loại thành phần dựa trên timestamp ở mục 4.4 và lưu ý rằng khi đó có thể suy ra quan hệ hậu duệ không chính xác. Phép chiếu có chủ đích sau đây minh họa việc mất thông tin. Nó không triển khai chính sách loại thành phần cũ của hệ thống đó.

def erase_c(clock):
    return (clock[0], clock[1], 0)

assert relation(removed.clock, added.clock) == 'concurrent'
assert relation(erase_c(removed.clock), erase_c(added.clock)) == 'after'
print('before erasure:', relation(removed.clock, added.clock))
print('after erasure:', relation(erase_c(removed.clock), erase_c(added.clock)))

Sau khi xóa C khỏi cả hai đồng hồ, nhánh xóa có vẻ đứng sau nhánh thêm: (1, 1, 0) chi phối (1, 0, 0). Kết luận đó sai đối với lịch sử gốc. Thông tin chứng minh lần ghi độc lập của C đã bị bỏ, nên phép so sánh không còn giữ được ý nghĩa ban đầu.

Mở ảnh kích thước đầy đủ ↗

Báo cáo là ảnh chụp thực bằng trình duyệt của một trang tự viết, lấy nội dung từ đầu ra Python và các giá trị phép chiếu đã kiểm tra. Vector và tập món là kết quả mô hình, không phải quan sát từ kho dữ liệu đang triển khai. Khi tự kiểm tra bài, tác giả còn đối chiếu 729 cặp vector nhỏ với các tập đoạn đầu tường minh và sinh 1.500 lịch sử ghi/quan sát, rồi so các cặp lần ghi với lịch sử nhân quả được giữ riêng.

Thử một thay đổi nhân quả và một định danh bị dùng sai

Trong một lần chạy mới, cho C quan sát bản ban đầu rồi quan sát lần xóa của B trước khi ghi. Sau đó, quyết định rõ ràng C ghi riêng bánh mì hay ghi cả sữa lẫn bánh mì. Vector mới của C phải có thành phần B, khiến lần ghi của C trở thành hậu duệ của lần xóa. Vector xác nhận điều C đã biết; nội dung được chọn vẫn quyết định sữa có trở lại hay không.

Ở một phép thử lỗi riêng, tạo hai Writer mới cùng tác nhân 0 rồi cho mỗi bên thực hiện lần ghi đầu với nội dung khác nhau. Cả hai tạo (1, 0, 0). Vì vậy kiểm tra đối số cục bộ của lớp không thay thế được chính sách định danh và vòng đời bộ đếm trên toàn hệ thống. Giữ phép thử này tách khỏi lần chạy ba bên ghi hợp lệ.

Khi rà soát thiết kế đối soát dữ liệu, cần trả lời hai câu cụ thể: quan sát nào làm một phiên bản thành hậu duệ của phiên bản khác, và quy tắc nội dung nào xử lý những nhánh còn không so sánh được? Số học vector đúng chỉ trả lời câu đầu khi các giả định lịch sử được giữ. Câu thứ hai cần đặc tả riêng, nhất là với thao tác xóa.