带有ttl的Lru在Rust中的实现及源码解析

ttl,lru,rust · 浏览次数 : 0

小编点评

本文介绍了带生存时间(TTL)的LRU缓存在Redis中的应用场景,包括缓存数据的过期时间设置、惰性删除和定期删除策略等。文章首先解释了TTL的概念,然后详细讨论了如何在Redis中使用LruCache来实现带TTL的缓存功能。最后,文章通过测试案例展示了如何验证带TTL的LRU缓存的性能和稳定性。 1. **TTL概念与应用场景**: - TTL是Time To Live的缩写,表示元素的生存时间。 - 应用场景包括缓存数据、设置过期时间以避免污染和简化程序逻辑。 2. **带TTL的LRU缓存实现**: - 在Redis中,可以通过setex命令为数据设置过期时间。 - 使用LruCache结构存储数据,并在获取元素时检查是否过期。 - 实现了惰性删除和定期删除策略,以平衡内存占用与CPU使用。 3. **测试案例**: - 测试案例展示了如何验证带TTL的LRU缓存的性能和稳定性。 - 通过惰性删除案例,演示了当数据过期时,在获取元素将为空。 - 通过定时删除案例,说明了在插入及定时到的时候进行删除数据。 总的来说,带TTL的LRU缓存能够有效地管理缓存的生命周期,提高缓存的命中率和性能,同时简化了程序逻辑,使得操作缓存更加方便。

正文

TTL是Time To Live的缩写,通常意味着元素的生存时间是多长。

应用场景

  • 数据库:在redis中我们最常见的就是缓存我们的数据元素,但是我们又不想其保留太长的时间,因为数据时间越长污染的可能性就越大,我们又不想在后续的程序中设置删除,所以我们此时需要设置过期时间来让数据自动淘汰。

setex now 10000 algorithm-rs

  • 内存缓存:通常在程序中需要缓存一定的数据结果,但是因为内存是有限的,需要在内存中储存最有效的数据进行缓存,此时需要设置过期时间,以在规定时间内淘汰无用的数据。

带ttl的Lru算法的优缺点

  • 优点
    • 可以根据过期时间自动淘汰掉无用的数据。
  • 缺点
    • 需要维护过期时间字段
    • 需要额外的cpu进行数据对比及可能出现的大量数据淘汰要额外️的进行cpu运算去淘汰数据。

了解Rust中的feature

在Rust编程语言中,feature是一个在Cargo.toml文件中定义的配置项,它允许开发者在构建和依赖项选择方面进行更细粒度的控制。
feature类似于C/C++中的#ifdef,我们可以根据需求来启用或者关闭代码,这样子可以有效的达到我们想要的功能。
在此设计中,我们在Cargo.toml定义了ttlfeature来启用ttl的功能。
在代码中我们可以在函数,也可以在某字段,也可以在某个执行中定义#[cfg(feature = "ttl")],他生效的是下一个字段或者函数或者语句

结构变化

在每个结点中,添加ttl的feature

pub(crate) struct LruEntry<K, V> {
    /// 头部节点及尾部结点均未初始化值
    pub key: mem::MaybeUninit<K>,
    /// 头部节点及尾部结点均未初始化值
    pub val: mem::MaybeUninit<V>,
    pub prev: *mut LruEntry<K, V>,
    pub next: *mut LruEntry<K, V>,
    /// 带ttl的过期时间,单位秒
    /// 如果为u64::MAX,则表示不过期
    #[cfg(feature = "ttl")]
    pub expire: u64,
}

在此处我们每个结点添加了一个u64的过期时间。

pub struct LruCache<K, V, S> {
    // ...
    #[cfg(feature = "ttl")]
    check_next: u64,
    /// 每次大检查点的时间间隔,如果不想启用该特性,可以将该值设成u64::MAX
    #[cfg(feature = "ttl")]
    check_step: u64,
    /// 所有节点中是否存在带ttl的结点,如果均为普通的元素,则过期的将不进行检查
    #[cfg(feature = "ttl")]
    has_ttl: bool,
}

函数变化

我们在获取元素结点时,需要判断其是否过期再进行返回,如果过期我们将返回空并将该结点进行删除。

pub(crate) fn get_node<Q>(&mut self, k: &Q) -> Option<*mut LruEntry<K, V>>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
{
    match self.map.get(KeyWrapper::from_ref(k)) {
        Some(l) => {
            let node = l.as_ptr();
            self.detach(node);
            #[cfg(feature = "ttl")]
            unsafe {
                if self.has_ttl && (*node).is_expire() {
                    self.map.remove(KeyWrapper::from_ref(k));
                    let _ = *Box::from_raw(node);
                    return None;
                }
            }
            
            self.attach(node);
            Some(node)
        }
        None => None,
    }
}

其中is_expire将会获取系统时间来进行当前是否过期的对比

#[cfg(feature = "ttl")]
#[inline(always)]
pub fn is_expire(&self) -> bool {
    get_timestamp() >= self.expire
}

#[inline(always)]
pub fn get_timestamp() -> u64 {
    SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).expect("ok").as_secs()
}

我们将这种函数代码量极少的进行内联的声明,以牺牲二进制包大小来提高运行速度。

插入方法我们额外提供带ttl的数据插入:

/// 插入带有生存时间的元素
/// 每次获取像redis一样,并不会更新生存时间
/// 如果需要更新则需要手动的进行重新设置
#[inline(always)]
pub fn insert_with_ttl(&mut self, k: K, v: V, ttl: u64) -> Option<V> {
    self.has_ttl = true;
    self._capture_insert_with_ttl(k, v, ttl).map(|(_, v, _)| v)
}

#[allow(unused_variables)]
fn _capture_insert_with_ttl(&mut self, k: K, mut v: V, ttl: u64) -> Option<(K, V, bool)> {
    #[cfg(feature="ttl")]
    self.clear_expire();

    let key = KeyRef::new(&k);
    match self.map.get_mut(&key) {
        Some(entry) => {
            let entry_ptr = entry.as_ptr();
            unsafe {
                mem::swap(&mut *(*entry_ptr).val.as_mut_ptr(), &mut v);
            }
            #[cfg(feature="ttl")]
            unsafe {
                (*entry_ptr).expire = ttl.saturating_add(get_timestamp());
            }
            self.detach(entry_ptr);
            self.attach(entry_ptr);

            Some((k, v, true))
        }
        None => {
            let (val, entry) = self.replace_or_create_node(k, v);
            let entry_ptr = entry.as_ptr();
            self.attach(entry_ptr);
            #[cfg(feature="ttl")]
            unsafe {
                (*entry_ptr).expire = ttl.saturating_add(get_timestamp());
            }
            unsafe {
                self.map
                    .insert(KeyRef::new((*entry_ptr).key.as_ptr()), entry);
            }
            val.map(|(k, v)| (k, v, false))
        }
    }
}

我们在插入的同时,会将过期时间进行设置,不带ttl的我们同样走该方法,只是传入的ttl参数ttl: u64将不会被使用,我们这里声明了#[allow(unused_variables)]告诉编译器,我们这里变量没有使用是我们预料之中的,不要进行警告。
我们将会设置节点的过期时间:

#[cfg(feature="ttl")]
unsafe {
    (*entry_ptr).expire = ttl.saturating_add(get_timestamp());
}

清除策略

Redis中过期数据的清除策略主要有三种:惰性删除、定时删除和定期删除。这些策略在Redis中用于平衡内存占用与CPU使用之间的关系,以确保Redis的性能和稳定性。

在这里我们实现的是惰性删除及定期删除策略,但是每次定期删除可能会遍历所有的元素,如果数据太大,容易无法在规定的时间内进行数据清理。后续可能需要单次最大遍历数据数量。

惰性删除

我们将获取元素的时候统一进行检查get_node,所有相关获取的数据将全部调用这里,这样子将函数统一化,可以更好的优化代码。

定期删除

每次执行会获取一次系统函数时间。

#[cfg(feature="ttl")]
pub fn clear_expire(&mut self) {
    if !self.has_ttl {
        return;
    }
    let now = get_timestamp();
    if now < self.check_next {
        return;
    }
    self.check_next = now + self.check_step;
    unsafe {
        let mut ptr = self.tail;
        while ptr != self.head {
            if (*ptr).is_little(&now) {
                let next = (*ptr).prev;
                self.detach(ptr);
                self.map.remove(&KeyRef::new(&*(*ptr).key.as_ptr()));
                let _ = *Box::from_raw(ptr);
                ptr = next;
            } else {
                ptr = (*ptr).prev;
            }
        }
    }
}

在清除的时候,需要先将map的数据移除掉,因为map的key只是节点的一个引用,如果先将节点删除,那么将出现map中的key指针悬空的情况。

self.map.remove(&KeyRef::new(&*(*ptr).key.as_ptr()));
let _ = *Box::from_raw(ptr);

在上述代码中,两行函数不能被调换,否则将无法正确删除map中的数据。

其它操作

  • set_ttl 设置元素的生存时间
  • del_ttl 删除元素的生存时间,表示永不过期
  • get_ttl 获取元素的生存时间
  • set_check_step 设置当前检查lru的间隔
  • 其它Lru能进行操作的均能操作
示例

以下示例示范当数据过期时,在获取元素将为空,演示了惰性删除。

#[test]
#[cfg(feature="ttl")]
fn test_ttl_cache() {
    let mut lru = LruCache::new(3);
    lru.insert_with_ttl("help", "ok", 1);
    lru.insert_with_ttl("author", "tickbh", 2);
    assert_eq!(lru.len(), 2);
    std::thread::sleep(std::time::Duration::from_secs(1));
    assert_eq!(lru.get("help"), None);
    std::thread::sleep(std::time::Duration::from_secs(1));
    assert_eq!(lru.get("author"), None);
    assert_eq!(lru.len(), 0);
}

以下演示以定时删除,将在插入及定时到的时候进行删除数据。

#[test]
#[cfg(feature="ttl")]
fn test_ttl_check_cache() {
    let mut lru = LruCache::new(3);
    lru.set_check_step(1);
    lru.insert_with_ttl("help", "ok", 1);
    lru.insert("now", "algorithm");
    assert_eq!(lru.len(), 2);
    std::thread::sleep(std::time::Duration::from_secs(1));
    assert_eq!(lru.len(), 2);
    lru.insert_with_ttl("author", "tickbh", 3);
    assert_eq!(lru.len(), 2);
    assert_eq!(lru.get("help"), None);
    assert_eq!(lru.len(), 2);
}

完整项目地址

https://github.com/tickbh/algorithm-rs

结语

带ttl的Lru可以一定程序上补充缓存的可用性。更方便的让您操作缓存。将内存与命中率进行完美的结合。

与带有ttl的Lru在Rust中的实现及源码解析相似的内容:

带有ttl的Lru在Rust中的实现及源码解析

TTL是Time To Live的缩写,通常意味着元素的生存时间是多长。 应用场景 数据库:在redis中我们最常见的就是缓存我们的数据元素,但是我们又不想其保留太长的时间,因为数据时间越长污染的可能性就越大,我们又不想在后续的程序中设置删除,所以我们此时需要设置过期时间来让数据自动淘汰。 sete

【单片机入门】(四)应用层软件开发的单片机学习之路-----ESP32开发板PWM控制电机以及中断的使用

引言 各位大佬,晚上好啊,在上一篇博客中,我们讲了什么是UART串口通讯,以及使用USB转TTL使得单片机可以和c#上位机做一个串口通讯,接下来,为大家带来PWM的概念原理,以及实际案例,使用PWM对电机进行速度调制,因为本课程的最后是做一个红外遥控的智能小车,所以是需要电机四个,驱动四个,轮胎四个

带有可旋转摄像头的移动小车(urdf+rviz)

博客地址:https://www.cnblogs.com/zylyehuo/ 成果图 step1:新建工作空间 mkdir -p catkin_ws/src cd catkin_ws catkin_make step2:建立工作包 右键src,选择 Create Catkin Package 输入包

自然语言处理 Paddle NLP - 情感分析技术及应用-理论

对带有感情色彩的主观性文本进行 分析、处理、归纳和推理的过程,输入文本 => (描述实体/entity,属性/aspect,情感/opinion ,观点持有者/holder,时间/time)

.NET Core反射获取带有自定义特性的类,通过依赖注入根据Attribute元数据信息调用对应的方法

前言 前段时间有朋友问道一个这样的问题,.NET Core中如何通过Attribute的元数据信息来调用标记的对应方法。我第一时间想到的就是通过C#反射获取带有Custom Attribute标记的类,然后通过依赖注入(DI)的方式获取对应服务的方法并通过反射动态执行类的方法,从而实现更灵活的编程方

curl 调用url时带有&符号被截断

转载请注明出处: 用curl命令在服务器上调试接口时,一直调试不通,执行如下: 在用curl 执行之后,返回了一个 作业id [ 1 ] 23926 ; 并打印出了 调用执行的url,发现 真正执行的url 与请求的url 长度不一致, 且 & 符号后面的参数都被截断了。 具体原因为:终端会将 &

[转帖]Oracle 用户密码中包括了“@”字符串的错误提示解决方法

Oracle 用户密码设置了带有“@”符号,正常登陆总是无法登陆,提示无法解析的连接字符串错误 解决办法:1:修改密码:修改密码使密码中不包括@符号;2:增加转义即可,在密码前后增加 \"示例如下: CMD中输入:C:\Users\Administrator> exp system/\"ABC@X1

AIGC革新,将文字或者LOGO融入AI视频基于PIKA-labs(Python3.10)

很多平台都会禁止用户使用带有网址或者二维码的头像以及文章配图,这样可以有效的防止用户的一些“导流”行为。当然,头像、文章或者视频现在都是AI来审,毕竟现在人工的成本实在太高,但是如果我们把文字元素直接融入图像或者视频之中,如此一来,AI也会很难识别出一些“导流”的元素。 本次我们依靠PIKA-lab

EndNote里参考文献的期刊名显示错误怎么办?

本文介绍EndNote文献管理软件导入文献引用时,期刊名称带有%J前缀从而不能正常显示的解决方法。 前期的文章中,我们多次介绍了文献管理软件EndNote的具体使用方法与技巧。而在使用EndNote软件时,我们经常下载.enw等格式的文献数据库导入文件,从而在EndNote软件中导入我们的参考文献信

nestjs入门学习总结(二):中间件、异常过滤器、守卫、管道、拦截器

### 中间件 Nest 中间件可以是一个函数,也可以是一个带有 @Injectable() 装饰器的类,且该类应该实现 NestMiddleware 接口,而函数没有任何特殊要求。 如下是一个日志中间件的简单示例: ``` import { Injectable, NestMiddleware }