在編程中，計數器是一種基本但強大的工具，用于跟蹤和管理數據和資源。本文將深入探討不同類型的計數器的應用，從Redis的LRU（最近最少使用）緩存淘汰算法的實現，到如何在內存受限的環境中有效地使用計數器，再到普通計數器的巧妙應用。

1. Redis的LRU實現

Redis，作為一個高性能的鍵值存儲系統，使用LRU算法來決定淘汰哪些數據以釋放內存。這個算法的關鍵在于跟蹤每個對象最后一次被訪問的時間，但為了節約內存，Redis并不使用完整的時間戳。相反，它采用了一種巧妙的方法：

時間戳精度的簡化：Redis通過將時間戳除以一個固定的分辨率（例如1000毫秒）來降低其精度。

位數限制：Redis進一步使用固定位數（例如24位）來存儲這些簡化的時間戳。

按位與操作：通過使用按位與操作確保計數器在達到最大值后自動從零開始，有效避免溢出。

這種方法在減少內存占用和保持時間戳更新效率之間取得了平衡，從而使LRU算法的實現既高效又節省空間。

Redis計算LRU時間的源碼如下(6.0.6)

#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<lru */
#define LRU_CLOCK_RESOLUTION 1000 




 * in a reduced-bits format that can be used to set and check the
 * object->lru field of redisObject structures. */
unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

在Redis的LRU算法實現中，使用24位來存儲時間戳是一種權衡內存使用和精度的方法。下面我們分析這種方法的具體細節：

24位時間戳的最大值:

首先，24位可以表示的最大值是 (2^{24} - 1)，即16777215。這是因為每個二進制位有兩個可能的值（0或1），所以24位可以表示 (2^{24}) 個不同的值，從0開始計數，最大值就是 (2^{24} - 1)。

精度

Redis中，時間戳的精度被降低到秒。這意味著每個時間戳表示從某個固定點（通常是Unix紀元，即1970年1月1日0000 UTC）開始的秒數。

相對時間點

使用24位存儲時間戳，意味著能夠表示的最大秒數是16777215秒。換算成更直觀的時間單位：

天數：194天

小時數: 4655小時

因此，24位時間戳可以表示從某個起始點開始的大約194天內的任意秒。

位運算和精度

當時間戳的值超過24位可以表示的最大值時，由于按位與操作（與16777215按位與），時間戳將自動回繞到0。這意味著每過194天左右，時間戳就會重置。重置后的時間戳值是從0開始的，但這并不影響Redis LRU算法的有效性，因為該算法主要關心的是對象相對于彼此的“最近使用”狀態，而不是絕對的時間點。

總結

所以，在Redis的LRU算法中，雖然時間戳的精度仍然是秒，但由于使用24位存儲，它只能表示大約194天的時間跨度。一旦超過這個時間跨度，時間戳就會回繞。這種設計在維持足夠精度的同時，大幅減少了每個對象的內存占用，非常適合于內存受限的高效緩存系統。

2. 內存效率和時間戳的近似表示

除了Redis的應用，固定位數的計數器在其他許多場景中也非常有用，特別是在需要以內存高效的方式存儲大量數據時。以下是兩個具體的應用示例：

2.1 內存效率的例子

假設你正在開發一個高性能的日志處理系統，該系統需要跟蹤數百萬條日志記錄的時間戳。如果使用完整的64位時間戳（精確到毫秒），對于每個日志記錄，時間戳將占用8字節的存儲空間。這在大量數據的情況下會導致巨大的內存消耗。

為了提高內存效率，你可以選擇使用24位來表示時間戳。雖然這會減少時間的精度，但對于很多日志分析任務來說，這種精度已經足夠。在這種情況下，每個時間戳只占用3字節的存儲空間。

通過這種方法，你可以顯著減少內存使用，同時仍然保留了足夠的信息來進行有效的日志分析。

不節省內存情況

使用標準的64位時間戳（精確到毫秒）。

每個時間戳占用8字節。

總內存使用量 = 100萬個事件 × 8字節/事件 = 800萬字節（約7.63 MB）。

節省內存情況

使用24位時間戳（精確到某個更大的時間單位，比如分鐘）。

每個時間戳占用3字節。

總內存使用量 = 100萬個事件 × 3字節/事件 = 300萬字節（約2.86 MB）。

節省效果

節省了約4.77 MB的內存。

對于某些應用（如日志分析），精確到分鐘可能已足夠，因此這種方法既節省內存又能提供所需的時間信息。

2.2 時間戳的近似表示

考慮一個網站緩存系統，它需要記錄每個頁面最后一次被訪問的時間。通過將Unix時間戳轉換為以10分鐘為單位的近似值，可以減少存儲需求，同時仍然提供足夠的信息來有效管理緩存。

下面是一個舉例說明:

完整精度情況

使用完整的32位Unix時間戳（精確到秒）。

時間戳示例：1617181723（代表2021年3月31日1423 UTC）。

近似精度情況

使用簡化的20位時間戳（以10分鐘為單位）。

假設我們以2021年1月1日為基準，計算從那時起經過的10分鐘間隔的數量。

時間戳示例：對于2021年3月31日14:15的時間，計算得到的20位時間戳可能是99000（這是一個假設的值，具體取決于基準日期和計算方法）。

精度對比

完整精度時間戳能精確到秒。

近似精度時間戳精確到10分鐘，對于緩存淘汰決策而言，這通常是足夠的。例如，它可以用來判斷一個頁面是在最近一小時內被訪問過，還是在更久之前。

3. 循環計數器的實際應用

利用固定位數和按位與操作實現高效的循環計數器

在編程中，經常需要跟蹤特定的事件或狀態的次數，尤其是在資源受限（如內存或存儲空間有限）的環境中。傳統的方法可能會涉及檢查計數器是否達到某個值，然后手動將其重置。然而，這種方法既繁瑣又容易出錯。幸運的是，有一種更優雅、高效的方法可以實現同樣的目標：使用固定位數的計數器結合按位與操作。

固定位數計數器的原理

固定位數計數器的概念很簡單。就是選擇一個特定的位數（比如16位、24位或32位）來存儲計數器的值。這個選擇直接決定了計數器的最大值，計數器的最大值為 (2^{位數} - 1)。例如，一個24位計數器的最大值是 (2^{24} - 1 = 16777215)。

為何選擇按位與操作

按位與操作 (&) 是一種基本的位運算，它對兩個數的每一位進行比較，只有當相同位置的兩個位都為1時，結果的那位才為1。在這種用法中，它的作用是確保計數器值在達到其最大值后自動歸零。

實現步驟

確定位數：首先，確定你需要的計數器位數。這將取決于你的特定應用和所需的最大計數范圍。

計算掩碼值：計算掩碼值，即計數器的最大值。對于一個N位計數器，掩碼值為 (2^N - 1)。

應用按位與：在增加計數器值時使用按位與操作，以確保計數器在達到最大值后自動回繞。

示例代碼

假設我們使用一個16位計數器：

#include 


#define COUNTER_BITS 16
#define COUNTER_MAX ((1 << COUNTER_BITS) - 1)


int main() {
    unsigned int counter = 0;


    for(int i = 0; i < 70000; i++) {
        counter = (counter + 1) & COUNTER_MAX;
        // 可以在這里執行其他操作
    }


    printf("Final counter value: %u
", counter);
    return 0;
}

在這個例子中，計數器將在65535之后回繞到0，這種方法適用于需要循環計數器的場景，如緩存淘汰、時間標記或狀態跟蹤。

結論

使用固定位數和按位與操作的循環計數器是一種節省資源、減少錯誤和提高代碼效率的強大工具。特別是在內存和存儲資源受限的情況下，這種方法顯得尤為重要。通過簡單的位運算，我們可以優雅地實現計數器的自動回繞功能，從而使我們的代碼更加簡潔和健壯。

4. 如何有效存儲固定位數

在大多數編程環境中，基本的整型（如int）通常占用4字節（32位）。對于只需要3字節來存儲的情況，確實會面臨內存分配和管理的挑戰。有幾種方法可以處理這種情況：

使用位域結構體

在C或C++中，你可以使用位域（bit fields）在結構體中精確指定每個成員的位數。例如，你可以定義一個24位的位域來存儲時間戳：

struct Timestamp {
    unsigned int time: 24;
};

這種方法允許你以3字節的存儲空間存儲時間戳，但它可能會引起端對齊（endian）問題，因此在跨平臺時需要小心處理。

使用字節數組你也可以使用一個字節數組（如3個char或uint8_t）來存儲這個值。在這種情況下，你需要手動處理值的設置和解析：

uint8_t timestamp[3];


// 設置值（示例）
timestamp[0] = (value >> 16) & 0xFF; // 最高有效字節
timestamp[1] = (value >> 8) & 0xFF;  // 中間字節
timestamp[2] = value & 0xFF;         // 最低有效字節


// 解析值
uint32_t recovered_value = (timestamp[0] << 16) | (timestamp[1] << 8) | timestamp[2];

這種方法給予了你更多控制，但增加了代碼的復雜性。

使用內置類型并接受一些空間浪費

有時，簡單地使用標準的4字節整型（如int或uint32_t）可能是更實際的選擇，即使這意味著你不會完全利用所有的位。雖然這會浪費一些空間，但代碼會更簡單、更清晰，并且更容易維護。這在不是極度內存受限的環境下通常是可接受的。

選擇方法

選擇哪種方法取決于你的具體需求。如果內存效率至關重要，并且你能夠處理額外的復雜性，那么使用位域或字節數組可能是合適的。如果代碼的可讀性和維護性更重要，那么簡單地使用標準的整型類型可能是更好的選擇。

鏈接：https://juejin.cn/post/7312035412159528969

（版權歸原作者所有，侵刪）

原文標題：從Redis的LRU實現到內存效率和位操作

文章出處：【微信公眾號：馬哥Linux運維】歡迎添加關注！文章轉載請注明出處。