Redis的LRU实现和应用-德赢Vwin官网网

在编程中，计数器是一种基本但强大的工具，用于跟踪和管理数据和资源。本文将深入探讨不同类型的计数器的应用，从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运维】欢迎添加关注！文章转载请注明出处。

声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人，不代表德赢Vwin官网网立场。文章及其配图仅供工程师学习之用，如有内容侵权或者其他违规问题，请联系本站处理。举报投诉

算法

算法

+关注

关注
23

文章
4607

浏览量
92826
内存

内存

+关注

关注
8

文章
3019

浏览量
74001
计数器

计数器

+关注

关注
32

文章
2256

浏览量
94476
Redis

Redis

+关注

关注
0

文章
374

浏览量
10871

原文标题：从Redis的LRU实现到内存效率和位操作

文章出处：【微信号：magedu-Linux，微信公众号：马哥Linux运维】欢迎添加关注！文章转载请注明出处。

LRU缓存模块最佳实践

lru模块，可以方便地实现LRU缓存。基础用法 Cargo.toml引入 lru 模块 lru = "0.10.0" 创建一个

发表于 09-30 16:47 •891次阅读

Redis Stream应用案例

的基本使用介绍和设计理念可以看我之前的一篇文章（Redis Stream简介）。Redis Stream本质上是在Redis内核上（非Redis Module）

发表于 06-26 17:15

Redis Cluster的基本原理及实现细节

Redis Cluster的基本原理和架构 Redis Cluster是分布式Redis的实现。随着Redis版本的更替，以及各种已知bug

发表于 09-28 19:09 •0次下载

<b class='flag-5'>Redis</b> Cluster的基本原理及<b class='flag-5'>实现</b>细节

谈谈Redis怎样配置实现主从复制？

之前总结过redis的持久化机制：深度剖析Redis持久化机制，持久化机制主要解决redis数据单机备份问题；redis的高可用需要考虑数据的多机备份，多机备份通过主从复制来

发表于 01-31 11:31 •666次阅读

Redis实现限流的三种方式分享

当然，限流有许多种实现的方式，Redis具有很强大的功能，我用Redis实践了三种的实现方式，可以较为简单的实现其方式。

发表于 02-22 09:52 •1070次阅读

设计并实现一个满足LRU约束的数据结构

LRUCache(int capacity)` 以 **「正整数」** 作为容量 `capacity` 初始化 `LRU` 缓存

发表于 06-07 17:05 •997次阅读

设计并<b class='flag-5'>实现</b>一个满足<b class='flag-5'>LRU</b>约束的数据结构

Redis的LRU与LFU算法实现

Redis是一款基于内存的高性能NoSQL数据库，数据都缓存在内存里，这使得Redis可以每秒轻松地处理数万的读写请求。

发表于 07-11 09:48 •1138次阅读

<b class='flag-5'>Redis</b>的<b class='flag-5'>LRU</b>与LFU算法<b class='flag-5'>实现</b>

Redis工具集的实现和使用

Redis 基本上是互联网公司必备的工具了，Redis的应用场景实在太多了，但是有很多相似的功能如果每个项目都要实现一遍就显得太麻烦了，所以为了方便，我打算开发一个基于 Redis 的

发表于 12-03 17:32 •1223次阅读

<b class='flag-5'>Redis</b>工具集的<b class='flag-5'>实现</b>和使用

Java redis锁怎么实现

在Java中实现Redis锁涉及到以下几个方面：Redis的安装配置、Redis连接池的使用、Redis数据结构的选择、

发表于 12-04 10:47 •1157次阅读

redis的淘汰策略

的写入。 Redis的淘汰策略主要有以下几种： LRU（Least Recently Used，最近最少使用）: 这是Redis默认的淘汰策略。当内存空间不足时，Redis会选择最近最

发表于 12-04 16:23 •542次阅读

redis hash底层实现原理

数据结构是如何实现的呢？本文将详细介绍Redis哈希底层的实现原理。在Redis中，每个哈希都是由一个类似于字典（Dictionary）的结构实现

发表于 12-04 16:27 •581次阅读

redis的lru原理

Redis是一种基于内存的键值数据库，它使用了LRU（Least Recently Used）算法来进行缓存的数据淘汰。LRU算法的核心思想是最近最少使用的数据将会在未来也不常用，因此应该优先

发表于 12-05 09:56 •625次阅读

redis数据结构的底层实现

Redis是一种内存键值数据库，常用于缓存、消息队列、实时数据分析等场景。它的高性能得益于其精心设计的数据结构和底层实现。本文将详细介绍Redis常用的数据结构和它们的底层实现。

发表于 12-05 10:14 •614次阅读

关于LRU(Least Recently Used)的逻辑实现

凑巧看到一个有关LRU(Least Recently Used)的逻辑实现，其采用矩阵方式进行实现，看起来颇有意思，但文章中只写方法不说原理，遂来研究下。LRU（Least Rece

发表于 11-12 11:47 •222次阅读

搜索历史

Redis的LRU实现和应用

评论