- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
Redis系列1:深刻理解高性能Redis的本质 Redis系列2:数据持久化提高可用性 Redis系列3:高可用之主从架构 Redis系列4:高可用之Sentinel(哨兵模式) Redis系列5:深入分析Cluster 集群模式 追求性能极致:Redis6.0的多线程模型 追求性能极致:客户端缓存带来的革命 Redis系列8:Bitmap实现亿万级数据计算 Redis系列9:Geo 类型赋能亿级地图位置计算 Redis系列10:HyperLogLog实现海量数据基数统计 Redis系列11:内存淘汰策略 Redis系列12:Redis 的事务机制 Redis系列13:分布式锁实现 Redis系列14:使用List实现消息队列 Redis系列15:使用Stream实现消息队列 Redis系列16:聊聊布隆过滤器(原理篇) Redis系列17:聊聊布隆过滤器(实践篇) Redis系列18:过期数据的删除策略 Redis系列19:LRU内存淘汰算法分析 。
上一期我们介绍了 Redis系列19:LRU淘汰内存淘汰算法分析 ,大致了解了LRU(Least Rencently Used) 的算法原理,即将最近最久未使用的算法进行数据淘汰。 但是这样的算法也有一些比较明显缺陷:
如上图,Key 1会被优先淘汰掉,但实际上,Key 1的访问频率和可能行高很多,我们并不希望Key 1被淘汰,而是希望淘汰率是 Key 2 > Key 1 为了解决这些问题,一些改进的算法被提出来,例如LFU(Least Frequently Used)算法和FIFO(First In First Out)算法。这些算法在某些情况下比LRU算法更合理更有效.
LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法,它通过key的访问频率、访问时间比较来淘汰key,重点突出的是Frequently Used,用于在缓存容量有限时决定哪些缓存块应该被清除.
LFU算法根据缓存块的使用频率来决定哪些块应该被清除。具体来说,它会记录每个缓存块的使用次数,并按照使用次数从低到高排序。当缓存达到容量上限时,LFU算法会选择使用次数最少的缓存块进行清除,也就是最不经常使用的缓存块.
LFU算法的优点是能够有效地防止缓存溢出,并且能够最大限度地减少清除重要数据的概率。但是,由于需要记录每个缓存块的使用次数,因此LFU算法需要较大的内存空间,并且由于需要经常更新使用次数,因此其时间复杂度相对较高.
LFU算法常用于Web缓存、数据库缓存、文件系统缓存等场景,用于提高系统的性能和稳定性.
实现原理如下:
LFU近似于LRU,使用概率计数器Morris计数器来估计每个对象的访问频率,并结合衰变周期使计数器随时间减少。这样,即使在过去,我们也不再考虑频繁访问的密钥。因此,该算法可以适应访问模式的变化。 Redis4.0之后 maxmemory_policy 淘汰策略 添加了两个LFU模式:
在LFU模式下,Redis对象头的24bit lru字段被分成两段来存储。其中,高16bit用于存储最后一次计数器降低的时间(ldt),低8bit用于存储访问次数的对数值(logc).
高16bit的ldt字段用于记录最近一次计数器降低的时间。由于只有16bit,它可以表示的最大值为65535(2^16-1)。由于时间以1秒为单位进行计数,因此大约每45.5天(65535/24/60)时间戳会折返重新从0开始.
低8bit的logc字段用于记录访问次数的对数值。由于只有8bit,它可以表示的最大值为255。实际上,logc无法记录真实的Redis key的访问次数,因为每个新加入的key的logc初始值为5(LFU_INITI_VAL),这样可以保证新加入的值不会被首先选中淘汰。每次访问key时,logc都会更新.
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+
/* Return the current time in minutes, just taking the least significant
* 16 bits. The returned time is suitable to be stored as LDT (last decrement
* time) for the LFU implementation. */
// server.unixtime为Redis缓存的Unix时间戳
// 使用的Unix的分钟时间戳,取模2^16
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535;
}
/* Given an object last access time, compute the minimum number of minutes
* that elapsed since the last access. Handle overflow (ldt greater than
* the current 16 bits minutes time) considering the time as wrapping
* exactly once. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
// 获取系统当前的LFU time
unsigned long now = LFUGetTimeInMinutes();
// 如果now >= ldt 直接取差值
if (now >= ldt) return now-ldt;
// 如果now < ldt 增加上65535
return 65535-ldt+now;
}
/* Logarithmically increment a counter. The greater is the current counter value
* the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
// Logistic Counter最大值为255 (8位的最大值), 如果已经是最大值了,直接返回
if (counter == 255) return 255;
// 取一个0~1之间的随机数数
double r = (double)rand()/RAND_MAX;
// counter减去LFU_INIT_VAL (LFU_INIT_VAL为每个key的Logistic Counter基数值,默认为5)
double baseval = counter - LFU_INIT_VAL;
// 如果衰减之后counter已经小于基数(如5),那么得出的结果 < 0,也取0
if (baseval < 0) baseval = 0;
// 可以看出如果lfu_log_factor的值越大,分母越大,得到的p越小
double p = 1.0/(baseval*server.lfu_log_factor+1);
// p 越小,r < p的可能性就越小,Logistic Counter增加的概率就越小
// 综上,lfu_log_factor越大增长越缓慢,缓解255空间紧张的问题
if (r < p) counter++;
return counter;
}
可以修改redis.conf配置文件,设置maxmemory-policy volatile-lfu / allkeys-lfu 来进行开启 。
# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
# is reached. You can select one from the following behaviors:
#
# volatile-lru -> Evict using approximated LRU, only keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU, only keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key having an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.
#
# LRU means Least Recently Used
# LFU means Least Frequently Used
#
# Both LRU, LFU and volatile-ttl are implemented using approximated
# randomized algorithms.
#
# Note: with any of the above policies, when there are no suitable keys for
# eviction, Redis will return an error on write operations that require
# more memory. These are usually commands that create new keys, add data or
# modify existing keys. A few examples are: SET, INCR, HSET, LPUSH, SUNIONSTORE,
# SORT (due to the STORE argument), and EXEC (if the transaction includes any
# command that requires memory).
#
# The default is:
#
# maxmemory-policy noeviction
#
#
# 备注1:对设置了过期时间的key启用LFU淘汰算法
# maxmemory-policy volatile-lfu
# 备注2:对全部key启用LFU淘汰算法进行计算
# maxmemory-policy allkeys-lfu
LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法,它通过key的访问频率、访问时间比较来淘汰key,重点突出的是Frequently Used,用于在缓存容量有限时决定哪些缓存块应该被清除。它避免了LRU淘汰算法明显缺陷.
最后此篇关于Redis系列20:LFU内存淘汰算法分析的文章就讲到这里了,如果你想了解更多关于Redis系列20:LFU内存淘汰算法分析的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我刚刚继承了一个旧的 PostgreSQL 安装,需要进行一些诊断以找出该数据库运行缓慢的原因。在 MS SQL 上,您可以使用 Profiler 等工具来查看正在运行的查询,然后查看它们的执行计划。
将目标从Analytics(分析)导入到AdWords中,然后在Analytics(分析)中更改目标条件时,是否可以通过更改将目标“重新导入”到AdWords,还是可以自动选择? 最佳答案 更改目标值
我正在使用google analytics api来获取数据。我正在获取数据,但我想验证两个参数,它们在特定日期范围内始终为0。我正在获取['ga:transactions']和['ga:goalCo
我使用Google API从Google Analytics(分析)获取数据,但指标与Google Analytics(分析)的网络界面不同。 即:我在2015年3月1日获得数据-它返回综合浏览量79
我在我的Web应用程序中使用sammy.js进行剔除。我正在尝试向其中添加Google Analytics(分析)。我很快找到了following plugin来实现页面跟踪。 我按照步骤操作,页面如
当使用 Xcode 分析 (product>analyze) 时,有没有办法忽略给定文件中的任何错误? 例如编译指示之类的? 我们只想忽略第三方代码的任何警告,这样当我们的代码出现问题时,它对我们
目录 EFK 1. 日志系统 2. 部署ElasticSearch 2.1 创建handless服务 2.2 创建s
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗?更新问题,使其成为 on-topic对于堆栈溢出。 7年前关闭。 Improve thi
GCC/G++ 是否有可用于输出分析的选项? 能够比较以前的代码与新代码之间的差异(大小、类/结构的大小)将很有用。然后可以将它们与之前的输出进行比较以进行比较,这对于许多目的都是有用的。 如果没有此
我正在浏览 LYAH,并一直在研究处理列表时列表理解与映射/过滤器的使用。我已经分析了以下两个函数,并包含了教授的输出。如果我正确地阅读了教授的内容,我会说 FiltB 的运行速度比 FiltA 慢很
在 MySQL 中可以使用 SET profiling = 1; 设置分析 查询 SHOW PROFILES; 显示每个查询所用的时间。我想知道这个时间是只包括服务器的执行时间还是还包括将结果发送到前
我用 Python 编写了几个用于生成阶乘的模块,我想测试运行时间。我找到了一个分析示例 here我使用该模板来分析我的模块: import profile #fact def main():
前几天读了下mysqld_safe脚本,个人感觉还是收获蛮大的,其中细致的交代了MySQL数据库的启动流程,包括查找MySQL相关目录,解析配置文件以及最后如何调用mysqld程序来启动实例等,有着
1 内网基础 内网/局域网(Local Area Network,LAN),是指在某一区域内有多台计算机互联而成的计算机组,组网范围通常在数千米以内。在局域网中,可以实现文件管理、应用软件共享、打印机
1 内网基础 内网/局域网(Local Area Network,LAN),是指在某一区域内有多台计算机互联而成的计算机组,组网范围通常在数千米以内。在局域网中,可以实现文件管理、应用软件共享、打印机
我有四列形式的数据。前三列代表时间,value1,value 2。第四列是二进制,全为 0 或 1。当第四列中对应的二进制值为0时,有没有办法告诉excel删除时间、值1和值2?我知道这在 C++ 或
我正在运行一个进行长时间计算的 Haskell 程序。经过一些分析和跟踪后,我注意到以下内容: $ /usr/bin/time -v ./hl test.hl 9000045000050000 Com
我有一个缓慢的 asp.net 程序正在运行。我想分析生产服务器以查看发生了什么,但我不想显着降低生产服务器的速度。 一般而言,配置生产盒或仅本地开发盒是标准做法吗?另外,您建议使用哪些程序来实现这一
我目前正在尝试分析 Haskell 服务器。服务器永远运行,所以我只想要一个固定时间的分析报告。我尝试只运行该程序 3 分钟,然后礼貌地要求它终止,但不知何故,haskell 分析器不遵守术语信号,并
是否有工具可以分析 Maven 构建过程本身,以便我可以看到构建花费最多时间的地方? 我们在工作中遇到了关于 Maven 3.0.3 和 3.0b1 的问题。与 3.0.3 (9m00s) 相比,我们
我是一名优秀的程序员,十分优秀!