Chuyên Đề Redis Chiến Lược Loại Bỏ - những game nổ hũ uy tín

calendar Feb 14, 2025 · 4 phút đọc · những game nổ hũ uy tín  ·
Chia sẻ trên: linkedin copy

LRU

Sau khi đã thảo luận về chiến lược hết hạn, bây giờ chúng ta sẽ chuyển sang tìm hiểu về cách Redis xử lý chiến lược loại bỏ. Redis áp dụng một phiên bản gần đúng của thuật toán LRU (Least Recently Used). Vậy tại sao lại gọi là "gần đúng"? Hãy cùng xem qua định nghĩa cơ bản của LRU.

Theo Wikipedia, giả sử bạn có bốn vị trí lưu trữ và truy cập theo thứ tự A → B → C → D → E → D → F. Khi lần đầu tiên D được truy cập, nó sẽ chiếm đầy các vị trí với giá trị 4 (càng nhỏ càng dễ bị loại bỏ). Sau đó, khi E vào, hệ thống sẽ kiểm tra các phần tử hiện có và thấy rằng A có giá trị nhỏ nhất – tức là tồn tại lâu nhất và chưa được truy cập gần đây – nên A sẽ bị loại bỏ để nhường chỗ cho E. Tiếp theo, khi D lại được truy cập, giá trị của nó sẽ được cập nhật lên 5. Cuối cùng, khi F đến, B là phần tử cũ nhất và chưa được truy cập gần đây nhất nên sẽ bị loại bỏ.

Tuy nhiên, Redis không thực thi chính xác như vậy. Lý do nằm ở hiệu quả về tài nguyên CPU và bộ nhớ. Nếu áp dụng nghiêm ngặt, mỗi key the thao 24h ngoai hang anh sẽ cần một bộ đếm thời gian riêng, điều này tiêu tốn rất nhiều tài nguyên máy tính và không mang lại hiệu quả đáng kể về mặt bộ nhớ.

Redis giải quyết vấn đề này bằng cách sử dụng phương pháp chọn mẫu ngẫu nhiên ban đầu từ tập hợp key trong dictionary. Phiên bản đầu tiên chọn ngẫu nhiên 5 key và loại bỏ key có giá trị LRU nhỏ nhất. Tuy nhiên, cách làm này tỏ ra không đủ hiệu quả.

Từ phiên bản Redis 3.0 trở đi, thay vì chọn mẫu ngẫu nhiên, Redis duy trì một pool chứa các key sắp xếp theo giá trị LRU. Pool mặc định có kích thước 16. Mỗi lần thêm mới, chỉ những key có giá trị LRU nhỏ hơn giá trị nhỏ nhất trong pool mới được phép thay thế các key hiện có. Điều này giúp cải thiện hiệu quả của quá trình loại bỏ.

Để minh họa rõ ràng hơn, hãy xem xét ví dụ sau:

  • Các key màu xám được thêm vào và truy cập tuần tự.
  • Sau đó, các key màu xanh lá được thêm vào.
  • Theoretically, các key màu xám cũ sẽ bị loại bỏ trước.

Trong thực tế:

  • Phiên bản Redis 2.8 chỉ chọn ngẫu nhiên 5 key và loại bỏ key có LRU nhỏ nhất, dẫn đến cả key màu xám và f8betv0 xanh đều có thể bị loại bỏ.
  • Phiên bản 3.0 cải tiến bằng cách duy trì pool, kết quả tốt hơn nhưng vẫn chưa hoàn hảo.
  • Khi tăng số lượng sample lên 10, chiến lược loại bỏ của Redis 3.0 đã gần đạt mức lý tưởng.

Dưới đây là đoạn mã đơn giản minh họa cách Redis xử lý:

1typedef struct redisObject {  
2    unsigned type:4;  
3    unsigned encoding:4;  
4    unsigned lru:LRU_BITS; /* Thời gian LRU (tương đối so với đồng hồ toàn cầu lru_clock) */  
5    int refcount;  
6    void *ptr;
7} robj;

Mỗi lần dữ liệu được truy cập, Redis sẽ gọi hàm lookupKey để cập nhật giá trị LRU của key tương ứng:

 1robj *lookupKey(redisDb *db, robj *key, int flags) {
 2    dictEntry *de = dictFind(db->dict,key->ptr);
 3    if (de) {
 4        robj *val = dictGetVal(de);
 5        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
 6            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
 7                updateLFU(val);
 8            } else {
 9                val->lru = LRU_CLOCK();
10            }
11        }
12        return val;
13    } else {
14        return NULL;
15    }
16}

Redis cũng cung cấp hàm những game nổ hũ uy tín LRU_CLOCK để lấy giá trị đồng hồ LRU hiện tại:

1unsigned int LRU_CLOCK(void) {
2    unsigned int lruclock;
3    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
4        lruclock = server.lruclock;
5    } else {
6        lruclock = getLRUClock();
7    }
8    return lruclock;
9}

Khi cần dọn dẹp bộ nhớ, Redis sẽ gọi hàm freeMemoryIfNeededAndSafe, nơi mà các key sẽ được chọn để loại bỏ dựa trên chiến lược đã chọn.