Chiến lược thay thế bộ nhớ đệm LRU

Bộ nhớ đệm là một thiết kế rất phổ biến giúp cải thiện tốc độ truy cập dữ liệu bằng cách lưu trữ dữ liệu vào các thiết bị lưu trữ có tốc độ truy cập nhanh hơn, chẳng hạn như bộ nhớ, bộ nhớ đệm CPU, bộ nhớ đệm ổ cứng, v.v.

Tuy nhiên, trái ngược với tốc độ cao của bộ nhớ đệm, chi phí của bộ nhớ đệm cao, do đó dung lượng thường bị hạn chế. Khi bộ nhớ đệm đầy, cần có chiến lược để quyết định dữ liệu nào sẽ xóa khỏi bộ nhớ đệm để tạo chỗ lưu trữ dữ liệu mới.

Chiến lược như vậy được gọi là chính sách thay thế bộ nhớ đệm.

Các chiến lược thay thế bộ nhớ đệm phổ biến bao gồm: FIFO (Nhập trước ra trước), LRU (Ít sử dụng gần đây nhất), LFU (Ít sử dụng thường xuyên nhất), v.v.

Hôm nay tôi sẽ giới thiệu cho các bạn thuật toán LRU.

Ý tưởng cốt lõi

Thuật toán LRU dựa trên giả định rằng nếu dữ liệu được truy cập gần đây thì khả năng dữ liệu đó được truy cập trong tương lai sẽ cao hơn.

Giả định này đúng trong hầu hết các trường hợp, do đó thuật toán LRU cũng là một chiến lược thay thế bộ nhớ đệm thường được sử dụng.

Dựa trên giả định này, chúng ta cần duy trì một cấu trúc dữ liệu có thứ tự để ghi lại lịch sử truy cập của dữ liệu khi triển khai. Khi bộ nhớ đệm đầy, chúng ta có thể quyết định dữ liệu nào sẽ xóa khỏi bộ nhớ đệm dựa trên cấu trúc dữ liệu này.

Không áp dụng được các tình huống

Tuy nhiên, nếu mẫu truy cập dữ liệu không đáp ứng được các giả định của thuật toán LRU, thuật toán LRU sẽ thất bại.

Ví dụ, nếu mẫu truy cập dữ liệu là định kỳ, thuật toán LRU sẽ loại bỏ dữ liệu định kỳ, điều này sẽ làm giảm tỷ lệ truy cập bộ đệm.

Nói cách khác, nếu dữ liệu được lưu trong bộ nhớ đệm chỉ được truy cập vào ban ngày và một lô dữ liệu khác được truy cập vào ban đêm, thì vào ban đêm, thuật toán LRU sẽ loại bỏ dữ liệu được truy cập vào ban ngày và dữ liệu được truy cập vào đêm qua sẽ bị loại bỏ vào ngày hôm sau, điều này sẽ dẫn đến giảm tỷ lệ truy cập vào bộ nhớ đệm.

Sau đây, tôi sẽ giới thiệu thuật toán LFU (Ít được sử dụng thường xuyên nhất) và sự kết hợp giữa LFU và LRU, thuật toán LFRU (Ít được sử dụng thường xuyên nhất và gần đây nhất), có thể giải quyết hiệu quả vấn đề này.

Triển khai cơ bản của thuật toán

Như đã đề cập ở trên, thuật toán LRU cần duy trì cấu trúc dữ liệu có thứ tự để ghi lại lịch sử truy cập dữ liệu. Thông thường chúng ta sử dụng danh sách liên kết kép để triển khai cấu trúc dữ liệu này, vì danh sách liên kết kép có thể chèn dữ liệu vào đầu hoặc cuối danh sách với độ phức tạp thời gian O(1) và xóa dữ liệu với độ phức tạp thời gian O(1).

Chúng tôi lưu trữ dữ liệu trong một danh sách liên kết kép và mỗi lần truy cập dữ liệu, chúng tôi di chuyển dữ liệu đến cuối danh sách liên kết để có thể đảm bảo rằng phần đuôi của danh sách liên kết là dữ liệu được truy cập gần đây nhất và phần đầu của danh sách liên kết là dữ liệu không được truy cập trong thời gian dài nhất.

Khi bộ nhớ đệm đầy, nếu cần chèn dữ liệu mới, vì phần đầu của danh sách liên kết là dữ liệu không được truy cập trong thời gian dài nhất, nên chúng ta có thể xóa trực tiếp phần đầu của danh sách liên kết rồi chèn dữ liệu mới vào phần đuôi của danh sách liên kết.

Nếu chúng ta muốn triển khai bộ đệm khóa-giá trị, chúng ta có thể sử dụng bảng băm để lưu trữ các cặp khóa-giá trị, để chúng ta có thể hoàn tất hoạt động tìm kiếm trong độ phức tạp thời gian là O(1). Trong .NET, chúng ta có thể sử dụng Dictionary.

Đồng thời, chúng tôi sử dụng LinkedList như một triển khai của danh sách liên kết hai chiều để lưu trữ các khóa được lưu trong bộ nhớ đệm và ghi lại lịch sử truy cập dữ liệu.

Mỗi khi chúng ta sử dụng Từ điển để chèn, xóa hoặc tìm kiếm, chúng ta cần chèn, xóa hoặc di chuyển khóa tương ứng đến cuối danh sách liên kết.

                        
                          // Triển khai giao diện IEnumerable để duyệt dễ dàng public class LRUCache : IEnumerable<>> { private readonly LinkedList _list; private readonly Dictionary _dictionary; private readonly int _capacity; public LRUCache(int capacity) { _capacity = capacity; _list = new LinkedList(); _dictionary = new Dictionary(); } public TValue Get(TKey key) { if (_dictionary.TryGetValue(key, out var value)) { // Xóa khóa khỏi danh sách liên kết rồi thêm khóa vào cuối danh sách liên kết // Điều này đảm bảo rằng phần đuôi của danh sách liên kết là dữ liệu được truy cập gần đây nhất và phần đầu của danh sách liên kết là dữ liệu không được truy cập trong thời gian dài nhất // Tuy nhiên, độ phức tạp về thời gian để xóa một khóa trong danh sách liên kết là O(n), do đó độ phức tạp về thời gian của thuật toán này là O(n) _list.Remove(key); _list.AddLast(key); return value; } return default; } public void Put(TKey key, TValue value) { if (_dictionary.TryGetValue(key, out _)) { // Nếu khóa được chèn đã tồn tại, hãy cập nhật giá trị tương ứng với khóa và di chuyển khóa đến cuối danh sách được liên kết _dictionary[key] = value; _list.Remove(key); _list.AddLast(key); } else { if (_list.Count == _capacity) { // Bộ nhớ đệm đã đầy, hãy xóa phần đầu của danh sách được liên kết, tức là dữ liệu không được truy cập trong thời gian dài nhất _dictionary.Remove(_list.First.Value); _list.RemoveFirst(); } _list.AddLast(key); _dictionary.Add(key, value); } } public void Remove(TKey key) { if (_dictionary.TryGetValue(key, out _)) { _dictionary.Remove(khóa); _list.Remove(khóa); } } public IEnumerator<>> GetEnumerator() { foreach (var key trong _list) { yield return new KeyValuePair(khóa, _dictionary[khóa]); } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } }

                        
                      

                        
                          var lruCache = new LRUCache(4); lruCache.Put(1, 1); lruCache.Put(2, 2); lruCache.Put(3, 3); lruCache.Put(4, 4); Console.WriteLine(chuỗi.Join(" ", lruCache)); Console.WriteLine(lruCache.Get(2)); Console.WriteLine(chuỗi.Join(" ", lruCache)); lruCache.Put(5, 5); Console.WriteLine(chuỗi.Join(" ", lruCache)); lruCache.Remove(3); Console.WriteLine(chuỗi.Join(" ", lruCache));

                        
                      

Đầu ra:

                        
                          [1, 1] [2, 2] [3, 3] [4, 4] // Khởi tạo 2 // Truy cập 2 [1, 1] [3, 3] [4, 4] [2, 2] // Di chuyển 2 đến cuối danh sách được liên kết [3, 3] [4, 4] [2, 2] [5, 5] // Chèn 5 [4, 4] [2, 2] [5, 5] // Xóa 3

                        
                      

Tối ưu hóa thuật toán

Trong triển khai ở trên, việc truy vấn, chèn và xóa bộ đệm sẽ liên quan đến việc xóa dữ liệu trong danh sách được liên kết (di chuyển cũng chính là xóa rồi chèn).

Vì chúng ta lưu trữ khóa trong LinkedList, trước tiên chúng ta cần tìm nút tương ứng trong danh sách liên kết theo khóa, sau đó xóa nó. Điều này dẫn đến độ phức tạp thời gian của hoạt động xóa danh sách liên kết là O(n).

Mặc dù độ phức tạp thời gian của các hoạt động tìm kiếm, chèn và xóa của Dictionary là O(1), nhưng do độ phức tạp thời gian của các hoạt động danh sách liên kết là O(n), nên độ phức tạp thời gian trường hợp xấu nhất của toàn bộ thuật toán là O(n).

Chìa khóa để tối ưu hóa thuật toán là làm thế nào để giảm độ phức tạp về thời gian của thao tác xóa danh sách liên kết.

Ý tưởng tối ưu hóa:

1. Lưu trữ ánh xạ giữa các nút khóa và LinkedList trong Dictionary
2. Lưu trữ cặp khóa-giá trị trong các nút LinkedList

Nói cách khác, chúng ta tạo ra một kết nối giữa hai cấu trúc dữ liệu ban đầu không liên quan đến nhau.

Cho dù chèn, xóa hay tìm kiếm bộ nhớ đệm, kết nối này có thể giảm độ phức tạp về thời gian xuống còn O(1).

1. Tìm nút tương ứng trong Từ điển theo khóa, sau đó lấy giá trị từ nút LinkedList. Độ phức tạp thời gian là O(1)
2. Trước khi xóa dữ liệu khỏi LinkedList, trước tiên hãy tìm nút tương ứng trong Dictionary theo khóa, sau đó xóa nó, để độ phức tạp thời gian của thao tác xóa danh sách được liên kết có thể giảm xuống còn O(1)
3. Khi LinkedList xóa nút đầu, vì khóa được lưu trữ trong nút, chúng ta có thể xóa nút tương ứng trong Từ điển theo khóa và độ phức tạp thời gian là O(1)

                        
                          _list = new LinkedList<>>(); _dictionary = new Dictionary<>>>(); } public TValue Get(TKey key) { if (_dictionary.TryGetValue(key, out var node)) { _list.Remove(node); _list.AddLast(node); return node.Value.Value; } return default; } public void Put(TKey key, TValue value) { if (_dictionary.TryGetValue(key, out var node)) { node.Value = new KeyValuePair(key, value); _list.Remove(node); _list.AddLast(node); } else { if (_list.Count == _capacity) { _dictionary.Remove(_list.First.Value.Key); _list.RemoveFirst(); } var newNode = new LinkedListNode<>>(new KeyValuePair(key, value)); _list.AddLast(newNode); _dictionary.Add(key, newNode); } } public void Remove(TKey key) { if (_dictionary.TryGetValue(key, out var node)) { _dictionary.Remove(key); _list.Remove(node); } } public IEnumerator<>> GetEnumerator() { return _list.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } }

                        
                      

Tối ưu hóa thêm

Vì yêu cầu lưu trữ của chúng ta đối với danh sách liên kết hai chiều được tùy chỉnh và yêu cầu khóa-giá trị được lưu trữ trong nút, nếu chúng ta sử dụng LinkedList của C# trực tiếp, chúng ta cần sử dụng một cấu trúc như KeyValuePair để lưu trữ gián tiếp, điều này sẽ gây ra một số chi phí bộ nhớ không cần thiết.

Chúng ta có thể tự triển khai danh sách liên kết hai chiều để có thể lưu trữ khóa-giá trị trực tiếp trong nút, do đó giảm chi phí bộ nhớ.

                        
                          , TValue>>(); } public TValue Get(TKey key) { nếu (_dictionary.TryGetValue(key, out var node)) { RemoveNode(node); } } public void Remove(TKey key) { if (_dictionary.TryGetValue(key, out var node)) { RemoveNode(node); AddLastNode(node); node.Value = value; } else { if (_dictionary.Count == _capacity) { var firstNode = RemoveFirstNode(); _dictionary.Remove(firstNode.Key); } var newNode = new DoubleLinkedListNode(key, value); AddLastNode(newNode); _dictionary.Add(key, newNode); } } public void Remove(TKey key) { if (_dictionary.TryGetValue(key, out var node)) { _dictionary.Remove(key); RemoveNode(node); } } private void AddLastNode(DoubleLinkedListNode node) { node.Previous _tail.Previous = node; _tail.Previous = node; } riêng tư DoubleLinkedListNode RemoveFirstNode() { var firstNode = _head.Next; _head.Next = firstNode.Next; firstNode.Next.Previous = _head; firstNode.Next = null; firstNode.Previous = null; return firstNode; } riêng tư void RemoveNode(DoubleLinkedListNode node) { node.Previous.Next = node.Next; node.Next.Previous = node.Previous; node.Next = null; node.Previous = null; } nội bộ lớp DoubleLinkedListNode { công khai DoubleLinkedListNode() { } công khai DoubleLinkedListNode(TKey key, TValue value) { Khóa = key; Giá trị = giá trị; } công khai TKey Key { lấy; đặt; } public TValue Giá trị { lấy; đặt; } public DoubleLinkedListNode Trước { lấy; đặt; } public DoubleLinkedListNode Tiếp theo { lấy; đặt; } } }

                        
                      

Điểm chuẩn

Sử dụng BenchmarkDotNet để so sánh hiệu suất của ba phiên bản.

                        
                          [MemoryDiagnoser] public class WriteBenchmarks { // Đảm bảo rằng dữ liệu được ghi có một mức độ lặp lại nhất định, do đó kiểm tra độ phức tạp thời gian tệ nhất của LRUpriv const int Capacity = 1000; private const int DataSize = 10_0000; private List _data; [GlobalSetup] public void Setup() { _data = new List(); var shared = Random.Shared; for (int i = 0; i < DataSize; i++) { _data.Add(shared.Next(0, DataSize / 10)); } } [Benchmark] public void LRUCache_V1() { var cache = new LRUCache(Capacity); foreach (var item in _data) { cache.Put(item, item); } } [Benchmark] public void LRUCache_V2() { var cache = new LRUCache_V2 _cachev2; () {_cachev1 = new lrucache_v2; LRUCache(Dung lượng); _cacheV2 = new LRUCache_V2(Dung lượng); _cacheV3 = new LRUCache_V3(Dung lượng); _data = new List(); var shared = Random.Shared; for (int i = 0; i < DataSize; i++) { int dataToPut = shared.Next(0, DataSize / 10); int dataToGet = shared.Next(0, DataSize / 10); _data.Add(dataToGet); _cacheV1.Put(dataToPut, dataToPut); _cacheV2.Put(dataToPut, dataToPut); _cacheV3.Put(dataToPut, dataToPut); } } [Điểm chuẩn] public void LRUCache_V1() { foreach (var item in _data) { _cacheV1.Get(item); } } [Điểm chuẩn] public void LRUCache_V2() { foreach (var item trong _data) { _cacheV2.Get(item); } } [Điểm chuẩn] public void LRUCache_V3() { foreach (var item trong _data) { _cacheV3.Get(item); } } }

                        
                      

Viết kết quả kiểm tra hiệu suất:

                        
                          | Phương pháp | Trung bình | Lỗi | Độ lệch chuẩn | Trung vị | Gen0 | Gen1 | Đã phân bổ | |------------ |----------:|----------:|---------:|---------:|---------:|----------:|| LRUCache_V1 | 16,890 ms | 0,3344 ms | 0,8012 ms | 16,751 ms | 750,0000 | 218,7500 | 4,65 MB | | LRUCache_V2 | 7,193 ms | 0,1395 ms | 0,3958 ms | 7,063 ms | 703,1250 | 226,5625 | 4,22 MB | | LRUCache_V3 | 5,761 ms | 0,1102 ms | 0,1132 ms | 5,742 ms | 585,9375 | 187,5000 | 3,53 MB |

                        
                      

Kết quả kiểm tra hiệu suất truy vấn:

                        
                          | Phương pháp | Trung bình | Lỗi | StdDev | Gen0 | Đã phân bổ | |------------ |----------:|----------:|----------:|----------:|----------:| | LRUCache_V1 | 19,475 ms | 0,3824 ms | 0,3390 ms | 62,5000 | 474462 B | | LRUCache_V2 | 1,994 ms | 0,0273 ms | 0,0242 ms | - | 4 B | | LRUCache_V3 | 1,595 ms | 0,0187 ms | 0,0175 ms | - | 3 B |

                        
                      

Cuối cùng, bài viết này về chiến lược thay thế bộ nhớ đệm LRU và triển khai C# đã kết thúc tại đây. Nếu bạn muốn biết thêm về chiến lược thay thế bộ nhớ đệm LRU và triển khai C#, vui lòng tìm kiếm các bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .