Cache-aside và cuộc đua điền dữ liệu cũ

Cập nhật cơ sở dữ liệu rồi xóa mục cache không ngăn được mọi giá trị cache cũ. Một bên đọc có thể đã lấy giá trị trước đó và vẫn đang chờ đưa nó vào cache. Nếu lần điền cache đến muộn này chạy sau lệnh xóa, nó tạo lại đúng giá trị mà bên ghi muốn loại bỏ.

Bài này dành cho kỹ sư ứng dụng đã hiểu cache hit, cache miss và có thể theo dõi năm sự kiện có thứ tự. Bạn không cần máy chủ cơ sở dữ liệu để tái hiện lỗi: mô hình Python xác định cho phép xem hết các cách sắp sự kiện trong một trường hợp nhỏ. Ta sẽ tách lỗi điền cache cũ khỏi lỗi vô hiệu hóa thất bại, độ trễ bản sao nguồn và việc chia sẻ công việc đồng thời. Những vấn đề ấy cần cam kết riêng.

Lệnh xóa không thể xóa một lần điền chưa xảy ra

Bên đọc theo kiểu cache-aside hỏi cache trước. Nếu miss, nó nạp giá trị từ nguồn có thẩm quyền và có thể lưu kết quả cho các lần đọc sau. Bên ghi thay đổi nguồn rồi vô hiệu hóa bản sao trong cache. Cache là bản sao có thể bỏ: mất một mục được chấp nhận, còn coi nó là bản ghi có thẩm quyền sẽ làm đổi thiết kế.

Mẫu đọc và ghi này xuất hiện trong mục 2 và Hình 1 của Scaling Memcache at Facebook của Nishtala cùng các đồng tác giả, công bố tại NSDI 2013. Bài báo mô tả việc xóa dữ liệu cache sau khi cập nhật cơ sở dữ liệu. Phần lease phía sau xử lý các lần set giá trị cũ do thứ tự cập nhật cache bị đảo. Ví dụ dưới đây dựng lại ở quy mô nhỏ loại vấn đề đó, không tái hiện số đo hệ thống vận hành trong bài báo.

Dùng giá trị 0 cho bản cũ và 1 cho bản mới. Ban đầu nguồn là 0, cache rỗng. Bên đọc gặp miss rồi đọc được 0 từ nguồn. Bên ghi commit giá trị 1 và xóa mục cache. Cuối cùng, bên đọc lưu lại 0 đã lấy trước đó. Cả hai bên đều tuân theo thứ tự sự kiện của mình, nhưng nguồn và cache cuối cùng không khớp.

Sự kiện	Nguồn	Cache
Bên đọc gặp miss	0	vắng mặt
Bên đọc lấy từ nguồn	0	vắng mặt
Bên ghi commit	1	vắng mặt
Bên ghi vô hiệu hóa	1	vắng mặt
Bên đọc điền cache	1	0

Lệnh xóa thực sự đã chạy, sau commit. Ví dụ không có thông điệp mạng bị mất. Chỉ là tại thời điểm xóa, không có gì để loại bỏ. Bên đọc tiếp theo có thể hit mục cũ mà không hỏi nguồn.

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

Cache rỗng tại lúc vô hiệu hóa không có nghĩa không còn kết quả cũ đang trên đường quay về.

Gắn thế hệ cho các lần điền đang chờ

Gắn một số thế hệ với trạng thái cache của khóa. Khi miss, bên đọc nhớ thế hệ hiện tại làm thẻ của mình. Vô hiệu hóa xóa giá trị đã lưu và tăng thế hệ trong cùng một thao tác cache nguyên tử. Lần điền so thẻ với thế hệ hiện tại, chỉ cài giá trị nếu chúng bằng nhau; so sánh và cài đặt cũng phải là một thao tác nguyên tử.

Trong tình huống đang xét, bên đọc giữ thẻ 0. Vô hiệu hóa đưa khóa sang thế hệ 1. Thẻ của lần điền muộn không còn khớp, nên cache từ chối và vẫn rỗng. Bên đọc mới có thể nhận thẻ 1 rồi lấy giá trị mới từ nguồn. Con số cho biết yêu cầu nằm trước ranh giới vô hiệu hóa nào; nó không phải giá trị trong cơ sở dữ liệu và không mã hóa dấu thời gian.

Mục 3.2.1 của bài báo Memcache mô tả cơ chế liên quan: token lease gắn với khóa được cấp khi cache miss và được kiểm tra lúc bên gọi set giá trị. Lệnh xóa có thể vô hiệu hóa token đó. Mô hình ở đây dùng số nguyên tăng dần để làm rõ quy tắc thu hồi quyền. Nó không cài đặt việc giới hạn tốc độ cấp token, kiến trúc triển khai hay toàn bộ giao thức lease của bài báo.

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

Ranh giới quan trọng là quyết định nguyên tử tại cache. So sánh phía bên gọi từ trước không cấp quyền ghi vào một thời điểm sau.

Chạy tình huống có và không có kiểm tra thế hệ

Mô hình dưới đây có một khóa, một bên đọc và một bên ghi. Mỗi sự kiện có tên là không thể bị xen ngang. Đọc nguồn trả giá trị được commit gần nhất tại chính sự kiện đó. Commit và vô hiệu hóa là hai sự kiện riêng, nên mô hình không giả định giao dịch bao trùm cả cơ sở dữ liệu lẫn cache.

Lịch chạy là một iterable hữu hạn chứa đúng một lần mỗi chuỗi trong năm tên sự kiện, giữ thứ tự riêng của từng bên. Hàm ghi nguồn, giá trị cache và thế hệ sau mỗi sự kiện. None nghĩa là vắng mặt; 0 là giá trị cache thực sự. Biến guard là chính sách Boolean, không phải tùy chọn của một thư viện cache.

def run(schedule, *, guarded):
    actions = tuple(schedule)
    required = {'miss', 'read', 'fill', 'commit', 'invalidate'}
    if (len(actions) != 5 or set(actions) != required
            or type(guarded) is not bool):
        raise ValueError('use each event once and a Boolean policy')
    pos = {event: i for i, event in enumerate(actions)}
    if not (pos['miss'] < pos['read'] < pos['fill']
            and pos['commit'] < pos['invalidate']):
        raise ValueError('preserve each participant\'s event order')

    source, cached, generation = 0, None, 0
    ticket = snapshot = None
    accepted = False
    history = []
    for event in actions:
        if event == 'miss':
            assert cached is None
            ticket = generation
        elif event == 'read':
            snapshot = source
        elif event == 'commit':
            source = 1
        elif event == 'invalidate':
            cached = None
            generation += 1
        else:  # fill: comparison and installation are one atomic event
            accepted = not guarded or ticket == generation
            if accepted:
                cached = snapshot
        history.append((event, source, cached, generation))
    return source, cached, accepted, tuple(history)


race = ('miss', 'read', 'commit', 'invalidate', 'fill')
assert run(race, guarded=False)[:3] == (1, 0, True)
assert run(race, guarded=True)[:3] == (1, None, False)
print('unconditional:', run(race, guarded=False)[:3])
print('generation guard:', run(race, guarded=True)[:3])

Kết quả không bảo vệ kết thúc với nguồn 1 và cache 0. Kết quả có kiểm tra thế hệ kết thúc với nguồn 1, mục vắng mặt và báo lần điền bị từ chối. Cả hai được tính từ cùng các sự kiện. Không có lệnh ngủ, hành vi bộ lập lịch luồng hay thời lượng yêu cầu giả định quyết định kết quả.

Mục vắng mặt là kết quả bảo đảm tính an toàn thành công cho thuộc tính này. Lần đọc kế tiếp có thể phải hỏi nguồn, nhưng kết quả điền đã lỗi thời không được giữ cho người gọi khác. Từ chối cũng không tự thay giá trị mà bên đọc ban đầu đang cầm. Nếu bên đó sắp trả 0 cho người gọi, ứng dụng vẫn phải quyết định thử lại, báo lỗi hay chấp nhận quan sát cũ hơn.

Kiểm tra cả mười thứ tự sự kiện

Bên đọc có ba sự kiện theo thứ tự, bên ghi có hai. Chọn ba vị trí của bên đọc trong năm vị trí tạo mười cách xen kẽ. Khối sau liệt kê đúng những cách đó. Nối nó sau khối đầu trong cùng tệp Python.

def interleave(left, right):
    if not left:
        yield right
    elif not right:
        yield left
    else:
        for tail in interleave(left[1:], right):
            yield (left[0],) + tail
        for tail in interleave(left, right[1:]):
            yield (right[0],) + tail


schedules = list(interleave(('miss', 'read', 'fill'),
                            ('commit', 'invalidate')))
assert len(schedules) == 10
bad = [s for s in schedules if run(s, guarded=False)[1] == 0]
assert bad == [race]
assert all(run(s, guarded=True)[1] in (None, 1) for s in schedules)
fresh_but_rejected = ('miss', 'commit', 'read', 'invalidate', 'fill')
assert run(fresh_but_rejected, guarded=True)[:3] == (1, None, False)
print('stale final entries, unguarded/guarded:', len(bad), 0)

# A previous successful comparison is not permission to write later.
ticket, generation, snapshot = 0, 0, 0
permission = ticket == generation
source, cached = 1, None  # the writer commits and invalidates
# Invalidation also revokes tickets from generation 0.
generation += 1
if permission:
    cached = snapshot
assert (source, cached, generation) == (1, 0, 1)
print('split check/store is unsafe:', cached)

Đúng một trong mười lịch để lại mục cũ cuối cùng khi điền vô điều kiện. Cả mười lịch có kiểm tra thế hệ kết thúc bằng mục vắng mặt hoặc giá trị 1. Đây là phát biểu vét cạn về mô hình năm sự kiện đã nêu. Nó không phải xác suất sự cố mười phần trăm: tải thực tế không nhất thiết tạo các lịch với tần suất bằng nhau, và mô hình còn bỏ qua nhiều sự kiện liên quan.

Các kiểm tra cuối cố ý tách so sánh thế hệ khỏi cài đặt. So sánh thành công tại thế hệ 0, bên ghi vô hiệu hóa, rồi bên đọc dùng quyền Boolean cũ để cài 0. Cách này thất bại dù bộ đếm đã tăng đúng. Đặt kiểm tra trong mã ứng dụng rồi ghi cache vô điều kiện không tái hiện được thao tác điền có điều kiện nguyên tử.

Máy chủ cache có thể cung cấp thao tác đó trong giao thức. Tiến trình cục bộ có thể bảo vệ so sánh và cài đặt bằng cùng cơ chế đồng bộ bảo vệ việc vô hiệu hóa. Dùng cơ chế nào cũng cần mọi bên thay đổi trạng thái liên quan cùng tuân theo; khóa ở một tiến trình bên gọi không tự phối hợp các tiến trình khác hay cơ sở dữ liệu từ xa.

Chứng minh thuộc tính có phạm vi hẹp

Xét bên đọc đã quan sát 0. Lần đọc nguồn của nó xảy ra trước commit giá trị 1. Nếu điền trước vô hiệu hóa, thao tác vô hiệu hóa sau đó xóa mục. Nếu điền sau vô hiệu hóa, thẻ của nó được nhận còn sớm hơn lần đọc nguồn, nên thế hệ đã thay đổi và lần điền bị từ chối. Dù theo cách nào, bên đọc này không thể để lại 0 trong cache sau khi cả năm sự kiện kết thúc.

Bên đọc quan sát 1 chỉ có thể cài 1 hoặc bị từ chối. Hai trường hợp xác lập thuộc tính trạng thái cuối trong mô hình. Chứng minh phụ thuộc thao tác cache nguyên tử, nguồn có ngữ nghĩa đọc đã nêu, vô hiệu hóa thành công và thế hệ không được dùng lại khi thẻ cũ vẫn có khả năng quay về.

Thuộc tính ấy yếu hơn yêu cầu mọi lần đọc trả giá trị commit mới nhất. Có thể có khoảng giữa commit và vô hiệu hóa. Nếu cache đã có giá trị, yêu cầu trong khoảng ấy vẫn đọc được mục cũ. Bản sao nguồn cũng có thể trả trạng thái cũ sau vô hiệu hóa nếu cam kết đọc không loại trừ điều đó. Mô hình cố ý bắt đầu với cache rỗng và đọc một nguồn có thẩm quyền; nó không giấu các khác biệt ấy trong từ “nhất quán”.

Thu hồi quyền có chi phí lưu trữ và khả năng phục vụ

Kiểm tra thế hệ cũng có thể từ chối dữ liệu mới. Trong fresh_but_rejected, bên đọc nhận thẻ 0, bên ghi commit 1, bên đọc lấy 1 rồi vô hiệu hóa tăng thế hệ trước lúc điền. Giá trị là hiện tại, nhưng thẻ không còn chứng minh quyền cài đặt. Từ chối thận trọng giúp tránh phải xét quan hệ phiên bản nguồn mà cache này không hiểu.

Ghi liên tục vì thế có thể gây nhiều lần điền bị từ chối. Thử lại mãi không phải cam kết hoàn thành hữu ích. Hãy giới hạn công việc và chọn chính sách rõ cho bên gọi. Quy tắc thế hệ cũng không chọn một bên nạp duy nhất: nhiều bên đọc có thể giữ thẻ cùng thế hệ và đều hỏi nguồn. Ngăn một đợt nạp trùng lặp là trách nhiệm khác.

Không thể loại siêu dữ liệu thế hệ dễ dàng như nội dung cache. Giả sử thẻ cũ 0 còn đang chờ, vô hiệu hóa tăng thế hệ lên 1, rồi dọn dẹp đặt lại 0 vì mục vắng mặt. Thẻ cũ khớp trở lại. Khởi động lại cache với danh tính thẻ được dùng lại có thể gây cùng vấn đề. Thiết kế thực tế cần danh tính lần khởi tạo phù hợp, quy tắc không tái sử dụng hoặc ranh giới đã chứng minh rằng sau đó thẻ cũ không thể quay lại. Bộ đếm có độ rộng cố định cần cách xử lý quay vòng rõ ràng; số nguyên Python trong mô hình không quay vòng.

Vô hiệu hóa lặp lại vẫn thận trọng: nó xóa giá trị và thu hồi thêm các thẻ đang chờ. Lệnh xóa thông thường trong bài báo có tính lũy đẳng đối với trạng thái mục vắng mặt; tăng thế hệ không tạo trạng thái giống hệt khi lặp, dù tăng thêm không làm sống lại thẻ cũ. Vì vậy các lần thử lại đến muộn có thể giảm ích lợi của cache mà không tạo lỗi điền cũ cụ thể này.

Bài tập: thêm bên đọc thứ hai rồi liệt kê ba sự kiện của nó cùng năm sự kiện hiện có. Giữ thẻ và trạng thái đã đọc của từng bên riêng biệt. Chỉ giữ lịch mà sự kiện mang tên miss gặp mục vắng mặt, hoặc mô hình hóa hit rõ ràng thay vì coi đó là miss. Sau đó cố ý dùng lại một thế hệ và tìm lần điền cũ được nó cho phép. Kết quả hữu ích là thứ tự cụ thể vi phạm thuộc tính có tên, không phải lời bảo đảm cache an toàn chỉ vì từng yêu cầu riêng lẻ trông đúng.