Chuỗi truy cập LRU có thể chạy bằng tay

Cache LRU giữ các mục vừa được dùng gần đây và loại mục lâu nhất chưa được dùng khi cần chỗ. Từ “dùng” rất quan trọng: đọc một giá trị đang có trong cache vẫn đổi vị trí của nó dù giá trị không thay đổi.

Nếu bạn mới cài đặt cache nhỏ cho ứng dụng, hãy bắt đầu bằng chuỗi truy cập tường minh thay vì một khẩu hiệu về tỷ lệ hit. Ví dụ cần kiến thức cơ bản về dictionary và hàm trong Python. Ta giữ ba giá trị hồ sơ, theo dõi từng thay đổi về độ gần đây và thử tải làm chính sách này thất bại. Ví dụ chạy tuần tự với hàm nạp đồng bộ; nó không phối hợp các yêu cầu đồng thời.

Đặt mục lâu nhất chưa dùng ở bên trái

Biểu diễn cache bằng danh sách khóa có thứ tự, lâu nhất chưa dùng ở đầu và vừa dùng gần đây nhất ở cuối. Sau các truy cập A, B, C, thứ tự là [A, B, C]. A sẽ bị chọn loại tiếp vì B và C đều được dùng sau A.

Truy cập A lần nữa. Đây là hit, tức khóa đã có trong cache, nên không cần nạp, nhưng thứ tự thành [B, C, A]. A đã chuyển sang vị trí mới nhất. Khi D chưa có, tức miss, thêm D vào bên phải và loại B ở bên trái. Thứ tự còn lại là [C, A, D].

Đây không phải thứ tự chèn. Hàng đợi chỉ xét lúc chèn vẫn coi A là cũ nhất sau hit và sẽ loại A khi D đến. Khác biệt xuất hiện trước mọi phép tính hiệu năng: hai chính sách giữ trạng thái khác nhau. Luôn ghi rõ đầu nào lâu nhất chưa dùng, vì có tài liệu vẽ cùng thứ tự LRU theo chiều ngược lại.

Operating Systems: Three Easy Pieces, phần 22.5, giới thiệu LRU dựa trên độ gần đây của truy cập và tính cục bộ theo thời gian. Vừa dùng gần đây là dấu hiệu có thể dùng lại, không phải bảo đảm. Ở đây ta áp dụng quy tắc thứ tự cho mục trong ứng dụng, không mô phỏng cài đặt thay trang của kernel.

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

Tách việc có khóa khỏi giá trị đang lưu

Cache cần phân biệt “không có khóa này” với “khóa này lưu một giá trị được coi là sai khi kiểm tra Boolean”. Kết quả hợp lệ có thể là None, số 0 hoặc chuỗi rỗng. Dùng if not cache.get(key) để quyết định nạp sẽ nhầm những giá trị ấy với miss.

Cài đặt kiểm tra sự hiện diện của khóa trước. Khi hit, nó chuyển khóa đang có đến vị trí mới nhất và trả giá trị đã lưu. Khi miss, nó gọi hàm nạp một lần, lưu kết quả thành công nếu dung lượng cho phép, và chỉ loại mục cũ nhất khi cần. Dung lượng 0 cố ý có nghĩa là bỏ qua việc lưu cache nhưng vẫn gọi hàm nạp.

Tài liệu OrderedDict của Python mô tả move_to_end và popitem(last=False), hai thao tác thứ tự cần dùng. Dictionary thường giữ thứ tự chèn, nhưng riêng một lần đọc không biến nó thành cache LRU. Cập nhật độ gần đây phải được thực hiện rõ ràng.

from collections import OrderedDict


class LRU:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity < 0:
            raise ValueError('capacity must be a nonnegative integer')
        self._capacity = capacity
        self._items = OrderedDict()

    def get(self, key, load):
        if type(key) is not str:
            raise ValueError('keys must be built-in strings')
        if key in self._items:
            self._items.move_to_end(key)
            return self._items[key]
        value = load(key)
        if self._capacity:
            self._items[key] = value
            if len(self._items) > self._capacity:
                self._items.popitem(last=False)
        return value

    def order(self):
        return tuple(self._items)  # Least recent first; no recency change.


calls = []
def load_profile(key):
    calls.append(key)
    return 'profile:' + key

cache = LRU(3)
trace = ('A', 'B', 'C', 'A', 'D', 'B', 'A', 'C')
expected = (
    ('A',), ('A', 'B'), ('A', 'B', 'C'), ('B', 'C', 'A'),
    ('C', 'A', 'D'), ('A', 'D', 'B'), ('D', 'B', 'A'),
    ('B', 'A', 'C'),
)
hits = []
for key, order in zip(trace, expected):
    hits.append(key in cache.order())
    assert cache.get(key, load_profile) == 'profile:' + key
    assert cache.order() == order
    print(key, 'hit' if hits[-1] else 'miss', order)
assert sum(hits) == 2 and len(calls) == 6
assert calls == ['A', 'B', 'C', 'D', 'B', 'C']

Khóa phải đúng kiểu chuỗi dựng sẵn; định danh viết hoa và viết thường khác nhau. Dung lượng là số nguyên không âm cố định, loại Boolean thay vì coi True là một chỗ. Bên gọi nên dùng phương thức công khai và không sửa trạng thái riêng. Hàm nạp nhận khóa bị miss và có thể trả bất kỳ giá trị nào; chuỗi truy cập chính dùng các chuỗi bất biến.

Hàm nạp không được gọi lại chính cache này theo cách đệ quy, và các lời gọi không được chồng lấn. Nếu không, một miss có thể thành hit trong lúc lần nạp ban đầu còn chạy, làm thay đổi lập luận về nhận mục mới và loại mục cũ. Hỗ trợ hành vi ấy cần hợp đồng phối hợp riêng. Chỉ thêm khóa quanh một thao tác dictionary chưa xác định vòng đời công việc nạp được chia sẻ.

order() trả ảnh chụp khóa dưới dạng tuple để học và kiểm tra. Nhìn tuple đó không tính là truy cập thêm. Nó chép các khóa đang lưu nên lượng công việc tỷ lệ với số mục. Không nên nhầm chi phí quan sát này với chi phí của một hit thông thường.

Đếm hit, miss và lần loại mục riêng

Chuỗi có tám truy cập. Chỉ truy cập thứ tư và thứ bảy, đều vào A, là hit. Vì vậy sáu truy cập gọi hàm nạp, cho tỷ lệ hit 2/8 trong lượt chạy cụ thể bắt đầu từ cache rỗng này. Ba miss đầu lấp chỗ trống; ba miss còn lại cần loại mục. Miss không tự động có nghĩa là một mục đã bị loại.

B và C đều được nạp hai lần. Lần ghé đầu không bảo đảm chúng còn trong cache đến lần ghé thứ hai: truy cập xen giữa có thể đẩy chúng ra. A chỉ nạp một lần vì các hit chuyển nó đến vị trí gần đây nhất vào đúng lúc cần. D nạp một lần nhưng bị loại bởi miss C cuối cùng.

Tỷ lệ hit tự nó không cho biết thời gian chạy. Hàm nạp có thể tính cục bộ rất rẻ hoặc gửi yêu cầu từ xa tốn kém, còn duy trì cache cũng có chi phí. Tám truy cập này là ví dụ tính cụ thể, không phải phép đo dịch vụ thật. So sánh trong sản phẩm cần chuỗi yêu cầu đại diện và chi phí miss được đo riêng.

Một bất biến hữu ích là các khóa được lưu không trùng, số mục không vượt dung lượng sau lời gọi hoàn tất, và khóa ngoài cùng bên phải là mục còn ở cache vừa được truy cập thành công gần đây nhất. Miss thành công tính là truy cập khi giá trị nạp được nhận vào. Lần nạp thất bại không tham gia thứ tự gần đây trong cài đặt này.

Giữ cache khi nạp thất bại

Nhánh miss nạp trước khi loại. Nếu hàm nạp phát sinh ngoại lệ, lỗi truyền ra ngoài và các mục sẵn có giữ nguyên giá trị cùng thứ tự. Loại trước sẽ bỏ một mục dùng được dù giá trị thay thế yêu cầu chưa bao giờ đến. Đoạn sau làm hành vi này quan sát được thay vì chỉ mô tả.

nullable = LRU(1)
none_calls = []
def load_none(key):
    none_calls.append(key)
    return None

assert nullable.get('optional', load_none) is None
assert nullable.get('optional', load_none) is None
assert none_calls == ['optional']

before = cache.order()
def fail(key):
    raise LookupError('upstream unavailable')

try:
    cache.get('E', fail)
except LookupError:
    pass
else:
    raise AssertionError('loader failure must propagate')
assert cache.order() == before

bypass = LRU(0)
assert bypass.get('optional', load_none) is None
assert bypass.get('optional', load_none) is None
assert len(none_calls) == 3 and bypass.order() == ()

scan_cache = LRU(3)
scan_calls = []
def scan_load(key):
    scan_calls.append(key)
    return key

for key in ('A', 'B', 'C', 'D') * 3:
    assert scan_cache.get(key, scan_load) == key
assert len(scan_calls) == 12
assert scan_cache.order() == ('B', 'C', 'D')

wide = LRU(4)
wide_calls = []
def wide_load(key):
    wide_calls.append(key)
    return key

for key in ('A', 'B', 'C', 'D') * 3:
    assert wide.get(key, wide_load) == key
assert wide_calls == ['A', 'B', 'C', 'D']
assert wide.order() == ('A', 'B', 'C', 'D')

Ví dụ None gọi hàm nạp một lần trong hai truy cập vì sự hiện diện độc lập với giá trị. Ví dụ dung lượng 0 gọi hàm nạp cả hai lần vì không giữ gì. Lần nạp E thất bại giữ nguyên thứ tự [B, A, C] cuối chuỗi chính.

Bảo đảm này chỉ nói về trạng thái riêng của cache. Nó không hoàn tác tác động ngoài mà hàm nạp đã gây trước khi báo lỗi. Nó cũng giả định hàm nạp không gián tiếp sửa cache. Chỉ quyết định lưu lỗi như kết quả sau khi xác định ý nghĩa và thời hạn của lỗi; ngoại lệ tùy ý không tự động là câu trả lời phủ định có thể dùng lại.

Quét lặp có thể loại đúng mục sắp được yêu cầu

Các đối chứng cuối quét A, B, C, D ba lần. Với ba chỗ, cả mười hai truy cập đều miss. Sau lượt đầu, thứ tự là [B, C, D]. A tiếp theo loại B; B tiếp theo lại loại C; C tiếp theo loại D; D tiếp theo loại A. Mẫu ấy tiếp tục lặp.

Với bốn chỗ, bốn truy cập đầu miss và tám truy cập còn lại hit. Chỗ bổ sung vượt qua ranh giới tập làm việc bốn mục của tải này. Kết quả chính xác đó không có nghĩa tăng một chỗ thường tạo ra cải thiện tương tự. Chuỗi có lượt quét lạnh lớn hơn nhiều hoặc tập khóa thay đổi có thể hành xử khác.

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

Ví dụ tuần tự lặp của OSTEP bàn cùng dạng thất bại khi chu kỳ lớn hơn cache. Phép tính mười hai yêu cầu ở đây dùng chuỗi nhỏ riêng. Chính sách nhận mục từ chối khóa chỉ dùng một lần, hoặc chính sách xét thêm tần suất, có thể giữ mục hữu ích trước một số lượt quét. Chúng cần thêm trạng thái và đánh đổi; một phản ví dụ này không đủ coi chúng là thay thế luôn đúng.

Xác định dung lượng và khóa thực sự có nghĩa gì

Ba mục không có nghĩa là ba lượng bộ nhớ bằng nhau. Một hồ sơ có thể chỉ giữ chuỗi nhỏ, trong khi hồ sơ khác giữ cả mạng đối tượng lớn. Cài đặt giới hạn số mục, không giới hạn tổng byte, cấp phát của hàm nạp hay tham chiếu bên gọi còn giữ sau khi mục bị loại. Cache theo ngân sách byte cần định nghĩa kích thước và quy tắc cho mục quá lớn.

Giá trị trả về không được sao chép. Nếu bên gọi sửa đối tượng khả biến đang được cache, các hit sau thấy chính đối tượng ấy. Chọn giá trị bất biến, sao chép khi trả hoặc ghi rõ việc sửa dùng chung sẽ đổi hợp đồng ứng dụng. Thứ tự gần đây không giải quyết quyền sở hữu giá trị.

Khóa còn phải chứa mọi đầu vào quyết định kết quả có thể dùng lại. Nếu hai người dùng có thể nhận biểu diễn hồ sơ khác nhau dưới cùng định danh, khóa bỏ sót ngữ cảnh cần thiết có thể trả sai dù ghi sổ LRU hoàn hảo. Chuyển chữ hoa thành chữ thường hay cắt khoảng trắng trong khóa cũng cần quy tắc định danh có chủ đích; ví dụ không làm cả hai.

LRU cũng không cung cấp hạn bảo đảm độ mới. Mục được đọc thường xuyên có thể ở lại vô hạn dù nguồn đã đổi. Hết hạn và vô hiệu hóa cần quyết định riêng. Loại mục trả lời nên bỏ mục đang lưu nào khi thiếu chỗ; độ mới trả lời kết quả đã lưu còn hợp lệ để phục vụ hay không.

Bài tập: bỏ move_to_end khỏi nhánh hit và chạy tay năm truy cập đầu. Cài đặt sai loại A thay vì B khi D đến. Sau đó thêm khóa chuỗi rỗng, giá trị false-like và lỗi hàm nạp vào mô hình tham chiếu dùng danh sách trực tiếp. So thứ tự sau từng truy cập thành công, không chỉ số hit cuối. Chuỗi nhỏ chỉ ra lần loại sai đầu tiên thường hữu ích hơn một tỷ lệ lớn không giải thích được.