当前位置: 首页 > news >正文

Caffeine Cache解析(一):接口设计与TinyLFU

Caffeine is a high performance Java caching library providing a near optimal hit rate.

  • 自动加载value, 支持异步加载
  • 基于size的eviction:frequency and recency
  • 基于时间的过期策略:last access or last write
  • 异步更新value
  • key支持weak reference
  • value支持weak reference和soft reference
  • 淘汰(或移除)通知
  • todo
  • 缓存获取数据统计

Caffeine的性能benchmark可参考Caffeine Benchmarks,
可以看到Caffeine在不同读写比的情况下, 吞吐量比Guava Cache和Jdk内置的HashMap都有较大提升。
接下来了解下Caffeine的使用、接口设计和TinyLFU简介。

使用

        // manual cache,Cache-Aside模式Cache<String, String> cache = Caffeine.newBuilder().expireAfterWrite(Duration.ofHours(1)).build();// null表示不存在key@Nullable String val = cache.getIfPresent("hello");if (val == null) {cache.put("hello", "world");}// key不存在则走后面的loading functionString val2 = cache.get("hello", key -> "world");// loading cache,Read-Through模式LoadingCache<String, String> loadingCache = Caffeine.newBuilder().expireAfterAccess(Duration.ofMinutes(10)).maximumSize(2000).build(new CacheLoader<String, String>() {@Overridepublic @Nullable String load(@NonNull String s) throws Exception {// your loading logicreturn "";}});// 不存在会自动loadingString val3 = loadingCache.get("hello");

接口设计

CacheCache按不同维度划分:

  • kv是否有限:Bounded or Unbounded,判断参见方法com.github.benmanes.caffeine.cache.Caffeine#isBounded,大部分场景都使用BoundedCache
  • 是否自动loading: ManualCache和LoadingCache
  • 是否异步: Cache和AsyncCache

对应接口UML如下(实现类只画出了BoundedCache),其接口和类均位于com.github.benmanes.caffeine.cache包下:

可以看到,核心的kv存储是放在了LocalCache接口(本质是一个ConcurrentMap)下,而其他的Loading和Async接口在存储基础上附加了自动加载value和异步加载的能力,以同步接口为例,接口能力如下:

  • Cache: 提供缓存基础能力,包含设置、读取、失效、获取缓存统计数据等功能;
  • LoadingCache: 提供自动加载能力,在Cache基础上新增不存在则loading value的读取以及refresh方法;
  • LocalCache: 提供核心存储能力,线程安全和原子能力保证,继承自java.util.concurrent.ConcurrentMap
  • LocalManualCache: 基于LocalCache做存储的非自动Loading Cache;
  • LocalLoadingCache: 继承自LocalManualCache,新增Loading功能。

关于以上接口的一个关键抽象实现类BoundedLocalCache,其作用解释如下:

This class performs a best-effort bounding of a ConcurrentHashMap using a page-replacement algorithm to determine which entries to evict when the capacity is exceeded.

TinyLFU & W-TinyLFU

在看BoundedLocalCache类前先来了解下TinyLFU & W-TinyLFU算法,
算法出自论文:TinyLFU: A Highly Efficient Cache Admission Policy

  • admission policy:控制一个元素是否能进入缓存
  • eviction policy:当缓存满了时选择哪一个元素剔除缓存

论文中提出的TinyLFU指的是admission policy,
TinyLFU可以和 LRU 、SLRU 的eviction policy组合。

比如 论文中使用W-TinyLFU + LRU + SLRU的组合进行实验:

Window Tiny LFU (W-TinyLFU) … consists of two cache areas.
The main cache employs the SLRU eviction policy and TinyLFU admission policy
while the window cache employs an LRU eviction policy without any admission policy.

可以看到 W-TinyLFU 的main cache area 使用 TinyLFU 作为 admission policy。

TinyLFU 在 LFU的基础上 加了Tiny,而Tiny体现在counter计数(和frequency正相关) 的记录上。
通常大部分缓存的元素访问频率都会很小,如果使用integer来记录counter计数,会导致空间浪费,因此
TinyLFU 借助 approximate counting scheme 来记录counter计数,其原理和bloom filter类似,而 schema的具体实现有:

  • Counting Bloom Filter
  • CM-Sketch : Caffeine中使用该实现,参见类com.github.benmanes.caffeine.cache.FrequencySketch,论文可参考:An Improved Data Stream Summary: The Count-Min Sketch and its Applications

Caffeine中的CM-Sketch使用4bit记录counter次数,最大只能到15,
并使用long[]类型存储,一个元素可存储16个计数器,long[]即相当于论文中的二维数组。

此外还增加了一个DoorKeeper即一个Bloom Filter来优先存储读取次数为1的元素,次数大于1的才会进入CM-Sketch结构中。

此外,TinyLFU利用Freshness Mechanism保证TinyLFU计数器记录的次数不会无限制扩大:

Every time we add an item to the approximation sketch, we increment a counter.
Once this counter reaches the sample size (W), we divide it and all other counters in the
approximation sketch by 2.

对应的可以在FrequencySketch类的increment方法中找到reset方法的调用:

// This class maintains a 4-bit CountMinSketch.
// The maximum frequency of an element is limited to 15 (4-bits) 
// and an aging process periodically halves the popularity of all elements.
final class FrequencySketch<E> {...int sampleSize;int size;public void ensureCapacity(@NonNegative long maximumSize) {...sampleSize = (maximumSize == 0) ? 10 : (10 * maximum);if (sampleSize <= 0) {sampleSize = Integer.MAX_VALUE;}size = 0;}// 计数器次数小于15时才会增加计数器public void increment(@NonNull E e) {...boolean added = ...if (added && (++size == sampleSize)) {reset();}}...
}

相关文章:

Caffeine Cache解析(一):接口设计与TinyLFU

Caffeine is a high performance Java caching library providing a near optimal hit rate. 自动加载value, 支持异步加载基于size的eviction&#xff1a;frequency and recency基于时间的过期策略&#xff1a;last access or last write异步更新valuekey支持weak referenceva…...

深入探索LINUX中AWK命令:强大的文本处理工具

深入探索LINUX中AWK命令&#xff1a;强大的文本处理工具 AWK 是一种编程语言&#xff0c;专为文本和数据处理设计&#xff0c;它以其强大的文本处理能力和简洁的语法在 Unix/Linux 系统中占据了重要地位。AWK 程序由一系列的模式(pattern)和动作(action)组成&#xff0c;对于输…...

数字化转型:解决项目管理困境的新路径

在当今这个飞速发展的数字化时代&#xff0c;企业如同在汹涌波涛中航行的船只&#xff0c;承受着前所未有的变革压力。而作为企业运作核心环节之一的项目管理&#xff0c;同样面临着巨大的挑战。 传统项目管理模式中的种种问题&#xff0c;犹如顽固的礁石&#xff0c;阻碍着项目…...

Arthas常用的命令(三)--monitor、jad 、stack

monitor&#xff1a;监控方法的执行情况 监控指定类中方法的执行情况 用来监视一个时间段中指定方法的执行次数&#xff0c;成功次数&#xff0c;失败次数&#xff0c;耗时等这些信息 参数说明 方法拥有一个命名参数 [c:]&#xff0c;意思是统计周期&#xff08;cycle of ou…...

Power BI之常用DAX函数使用介绍——提供数据源练习

前述&#xff1a; 本次使用数据是包含产品表、客户表、区域表、销售订单表的一份销售订单数据&#xff0c;数据源链接如下&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1micl_09hFrgz2aUBERkeZg 提取码&#xff1a;y17e 一、CALCULATE 1.语法结构 语法结构CALCUL…...

SQL-触发器(trigger)的详解以及代码演示

一、触发器的概念 触发器是一种特殊的存储过程&#xff0c;但是触发器不存在输入和输出参数&#xff0c;所以不能被显式的去调用&#xff0c;而是与特定的表相关联&#xff0c;当表中的数据发生变化时&#xff0c;触发器被激活并执行其定义的SQL代码。触发器可以是行级触发器&…...

【devops】x-ui 实现一键安装 x-ray 打造高速国际冲浪 | xray管理平台

一、部署X-UI篇 1、Github 地址&说明 github地址如下&#xff1a; https://github.com/FranzKafkaYu/x-ui?tabreadme-ov-file 2、一键部署 2.1、更新并安装curl #Ubuntu、Deibian系统 apt update && apt upgrade -y apt install curl -y #CentOS7 系统 yum…...

Linux系统编程——进程标识、进程创建

一、进程标识&#xff08;pid&#xff09; 每个进程都有一个非负整数形式的唯一编号&#xff0c;即 PID。PID 在任何时刻都是唯一的&#xff0c;但是可以重用&#xff0c;当进程终止并被回收以后&#xff0c;其 PID 就可以为其它进程所用。进程的 PID 由系统内核根据延迟重用算…...

【超级福利】openMind开源实习来袭,奖励高达万元,解锁你的AI实践新篇章!

亲爱的小伙伴们&#xff0c;是不是梦想着能在真实的项目中大展拳脚&#xff0c;却又苦于找不到合适的舞台&#xff1f;别担心&#xff0c;OpenI启智社区携手openMind Library工具链&#xff0c;为你量身打造了一场开源实习盛宴&#xff0c;保证让你的学习不再无聊&#xff0c;技…...

React JSX 使用条件语句渲染UI的两种写法

只针对函数组件 1. 第一种写法&#xff1a; function App({ id }) {return id1? <h1>hello</h1> : <h1>world</h1>; } 或者&#xff1a; function App({ id }) {return (<h1>{id1 && "hello" || id2 && "wo…...

谷歌-BERT-第四步:模型部署

1 需求 需求1&#xff1a;基于gradio实现大模型的WEB UI交互界面 2 接口 3 示例 import gradio as gr from transformers import *classifier pipeline("text-classification", model"./model", tokenizer"./model")gr.Interface.from_pipel…...

猫咪化身蒲公英,浮毛满屋乱飞,有哪些宠物空气净化器值得购买?

不掉毛的猫咪究竟是谁在养&#xff1f; 当初去朋友家玩&#xff0c;被猫咪捕获芳心&#xff0c;没多久自己也领养了一只。没想到啊&#xff0c;这就意味着要和猫毛纠缠一辈子了。平时白天上班不在家&#xff0c;它就在一边跑动一边掉毛&#xff0c;回到家我都能推断它的行动路…...

端到端的开源OCR模型:GOT-OCR-2.0,支持场景文本、文档、乐谱、图表、数学公式等内容识别!

今天给大家分享一个端到端的开源 OCR 模型&#xff0c;号称 OCR 2.0&#xff01; 支持场景文本、文档、乐谱、图表、数学公式等内容识别&#xff0c;拿到了 BLEU 0.972 高分。 从给出的演示图来看&#xff0c;一些非常复杂的数学公式都能正确的识别&#xff0c;颇为强大。模型…...

自注意力机制self-attention中QKV矩阵的含义

自注意力机制&#xff08;Self-Attention&#xff09;是Transformer模型的核心组件&#xff0c;其中Q、K、V矩阵分别代表查询&#xff08;Query&#xff09;、键&#xff08;Key&#xff09;、值&#xff08;Value&#xff09;。它们的作用和含义可以通过信息匹配过程来理解。在…...

【前端】Bootstrap:栅格系统 (Grid System)

Bootstrap的栅格系统是该框架的核心部分之一&#xff0c;能够让开发者轻松创建响应式网页布局&#xff0c;适配各种屏幕尺寸和设备。栅格系统通过将页面划分为12列的布局结构&#xff0c;开发者可以根据内容的重要性和设计需求灵活控制元素的宽度和排列。 在这篇文章中&#x…...

一文读懂,SSL证书怎么验签安装使用?

SSL证书目前已经有越来越多的企业网站开始使用&#xff0c;安装SSL证书后&#xff0c;原有的http协议将会变成安全性更好的https加密协议&#xff0c;这对保护用户的信息安全&#xff0c;保障企业及用户的利益起着重要作用。 一张SSL证书的获取&#xff0c;需要经历不少环节&a…...

Mysql(八) --- 视图

文章目录 前言1.什么是视图&#xff1f;2.创建视图3. 使用视图4. 修改数据4.1.注意事项 5. 删除视图6.视图的优点 前言 前面我们学习了索引&#xff0c;这次我们来学习视图 1.什么是视图&#xff1f; 视图是一个虚拟的表&#xff0c;它是基于一个或多个基本表或其他视图的查询…...

SQL注入原理、类型、危害与防御

SQL注入的原理概念 SQL注入是一种常见的网络攻击技术&#xff0c;攻击者通过在Web应用程序的输入字段中注入恶意构造的SQL代码&#xff0c;以欺骗后端数据库执行非预期的SQL命令。这种攻击可以导致数据泄露、权限提升、数据篡改甚至系统瘫痪。SQL注入可以分为多种类型&#xf…...

第2讲 数据库系统的结构抽象与演变

基本内容 数据库系统的标准结构?数据模型?数据库系统的演变与发展?重难点 一组概念的区分:三级模式两层映像,物理独立性和逻辑独立性一组概念的区分:数据→模式→数据模型几种数据模型的差异:网状/层次模型→关系模型→数据模型数据库系统的标准结构 (1)数据库系统的分…...

Git创建开发分支命名规则

git checkout -b feature/branchname 和 git checkout -b branchname 这两条命令的主要区别在于新分支的命名。 主要区别 分支命名&#xff1a; git checkout -b feature/branchname&#xff1a;新分支的名字是 feature/branchname&#xff0c;表示该分支属于一个特性开发&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...