Go 语言进阶freecache源码学习教程

目录
  • 00. 什么是 freecache?
  • 01. 简单用法
  • 02. 功能概览
  • 03. 如何做到 0 GC?
  • 04. 数据结构
  • 05. 动态索引
  • 06. 缓存失效

00. 什么是 freecache?

freecache 是一个用 go 语言实现的本地缓存系统(类似于 lru)。

相关的 github 地址:https://github.com/coocood/freecache

它有几个特性值得注意:

  • 通过优秀的内存管理方案,实现了 go 语言的零 gc
  • 是线程安全的,同时支持一定程度的并发,非常适合并发场景
  • 支持设置失效时间,动态失效过期缓存
  • 在一定程度上支持 lru,即“最近最少使用”,会在容量不足的时候优先淘汰较早的数据

这几个优秀特性使得他非常适合用在生产环境中作为本地缓存。

01. 简单用法

cacheSize := 100 * 1024 * 1024
cache := freecache.NewCache(cacheSize)
debug.SetGCPercent(20)
key := []byte("abc")
val := []byte("def")
expire := 60 // expire in 60 seconds
cache.Set(key, val, expire)
got, err := cache.Get(key)
if err != nil {
    fmt.Println(err)
} else {
    fmt.Println(string(got))
}
affected := cache.Del(key)
fmt.Println("deleted key ", affected)
fmt.Println("entry count ", cache.EntryCount())

02. 功能概览

本文计划先以自然语言描述下列功能的实现方式,再接下来的章节中深入源码,扒出其具体实现

  • 如何做到零 gc?
  • 数据结构
  • 动态索引
  • 缓存失效

03. 如何做到 0 GC?

这个库之所以做到了 0 gc,是因为设定了很巧妙的数据结构,这个数据结构有以下的特点:

  • 无论存多少数据,都只会存在 512 个指针
  • 所有的具体数据的存储空间,都是预先就分配好的,而不是动态分配的
  • 使用了一些黑科技,比如强制类型转换以及结构体对齐等技术,将所有的动态数据都管理在预先分配好的连续空间内

04. 数据结构

可以将这个数据结构大体上抽象成一个哈希表。即你会看到哈希函数以及对应的数组空间。但是他和传统的哈希表是有区别的,主要有以下几点:

  • 线程安全,支持高并发,内存空间高度优化:
  • 为了做到支持高并发以及线程安全,并且保证内存空间的可用性,freecache 实际上划分出了 256 个独立数组空间用来存储对应的底层数据。
  • 这样在并发访问的时候,通过对 key 进行分片,使得请求只会打到一个数组空间上,即只会对这 256 个空间中的一个空间加锁,这样就大大降低了资源争抢。
  • 数据的组织方式与传统哈希表不同:
  • 传统的哈希表只在数组空间中存 value。而 freecache 则不同,他将 key,value 全部存在了数组空间中。
  • 传统哈希表的数组是稀疏的。freecache 数据并不是稀疏的,而是连续的,即新的值会不断 append 到最后。
  • 传统哈希表使用 hash func 对 key 取索引,索引到稀疏数组中的位置。而 freecache 则通过维护了一个叫“slot(插槽)”的数据结构,通过对 key 进行 hash func,先拿到对应的 slot,然后 slot 中维护着一个索引,可以定位到具体的数据在数组中的位置。
  • 解决哈希冲突的方式不同。当遇到哈希冲突的时候,哈希表需要对底层的稀疏数组进行扩容,会导致可用性大大降低。而 freecache 则是只需要对“slot”的指针数组进行扩容,而无需改变底层数组。因为 slot 指针数组的大小远小于底层数组,所以扩容的成本是非常非常低的。
  • 为了实现缓存淘汰以及定时失效,它的数组空间在逻辑上是一个环状的。这么做有以下原因
  • 数组存的数据逻辑上是连续的,而非稀疏数组。充分利用了CPU对数组读取的缓存优化
  • 通过使用了一系列的首尾计算方式,是足以保证读取和存储在首尾的连续性。比如读数据的时候读到结尾如果还没读完,会跳转到头部继续往下读。
  • 能以 O(1) 的时间复杂度完成新数据对旧数据的淘汰。我们假设如果数组在逻辑上不是环形的,那么当数组写满的时候再写入新的数据,就需要把数组头部的数据删除掉,然后再把之后的数据统统向左移动删除数据的长度,然后再从最右端写入新的数据。反之,如果数组是环形的,只需要在数组头部把旧数据覆盖即可
  • 通过一些算法手段,可以实现一个很 hack 的 lru 功能。在一定程度上能保证“最近最少使用”的淘汰。

05. 动态索引

通过上面对数据结构的分析,我们知道他和传统的哈希表的实现方式大相径庭。它实际上是使用了一种叫“插槽”的数据结构,专门负责通过 key 索引到数据空间中的某个位置。他的实现比较有意思。它的底层是一个结构体指针数组。他是可以动态扩容的。每个插槽有一个 id,叫 slotId,范围是 0~255。当遇到哈希冲突的时候,比如出现了2个 slotId 为 100 的 slot,他就会检测当前的最大重复 slotID 数量 n。如果这个 2 大于 n,他就会扩容到 2n。

// slot 的数据结构
type entryPtr struct {
	offset   int64  // 记录了当前 slot 在环形数组中的偏移量
	hash16   uint16 // 一个 hash 值,用于在 segment 中定位到具体的 slot
	keyLen   uint16 // used to compare a key
	reserved uint32
}
// 每个分片的数据结构
type segment struct {
	rb            RingBuf // 环形数组
	segId         int
	hitCount      int64
	missCount     int64
	entryCount    int64
	totalCount    int64      // 之后计算 lru 的时候会用到,用于衡量一个数据是否是热点数据
	totalTime     int64      // 之后计算 lru 的时候会用到,用于衡量一个数据是否是热点数据
	totalEvacuate int64      // used for debug
	totalExpired  int64      // used for debug
	overwrites    int64      // used for debug
	vacuumLen     int64      // 环形数组可用容量,主要用于环形数组首尾相接的算法
	slotLens      [256]int32 // 每个 slotId 的长度的数组
	slotCap       int32      // 每个 slotId 的容量
	slotsData     []entryPtr // 存储 slots 的切片,根据 hash16 进行顺序排列。相同的 hash16 拥有相同的 slotId
}

06. 缓存失效

缓存失效主要包括两种:

  • 基于过期时间的失效
  • 基于最近最少使用的失效

这两种失效都有缺陷。

首先它是一种被动失效,而不是通过一个额外的线程定期check。而是每次 set 新的值的时候,如果发现空间不够用了,他才会尝试从环形数组的头端进行check。如果发现当前check的数据过期了,或者使用频率过低,就会将记录有效数据的头指针进行偏移,即相当于“失效”。如果检查多次都没能找到需要失效的数据,那么他会将这些检查过的数据转移到尾部,并强制当前的头部的数据失效。

这种失效是不可靠的。比如一个数据,如果在环形数组的中间,那么即便它过期了,也很难被 check 到。并且存在一定的失误概率,即将一个热点数据给失效了。

以上就是Go 语言进阶freecache源码学习教程的详细内容,更多关于Go语言freecache的资料请关注我们其它相关文章!

(0)

相关推荐

  • django中使用memcached示例详解

    目录 什么是memcached: 安装和启动memcached: windows linux(ubuntu) 启动memcached: telnet操作memcached: 添加数据: 获取数据: 删除数据: 通过python操作memcached: memcached的安全性: 在Django中使用memcached: 什么是memcached: memcached之前是danga的一个项目,最早是为LiveJournal服务的,当初设计师为了加速LiveJournal访问速度而开发的,后来被

  • Mango Cache缓存管理库TinyLFU源码解析

    目录 介绍 整体架构 初始化流程 读流程 写流程 事件处理机制 主流程 write 清理工作 缓存管理 什么是LRU? 什么是SLRU? 什么是TinyLFU? mango Cache中的TinyLFU counter counter的初始化 counter的使用 lruCache slruCache filter TinyLFU的初始化 TinyLFU写入 TinyLFU访问 增加entry的访问次数 估计entry访问次数 总结 介绍 据官方所述,mango Cache是对Guava Cac

  • go-cache的基本使用场景示例解析

    目录 什么是 go-cache 使用 导入 快速开始 常量与结构体 常量 结构体 Set() Get() 删除 其他 备份恢复数据 什么是 go-cache go-cache 是一个轻量级的基于内存的 K-V 储存组件,内部实现了一个线程安全的 map[string]interface{},适用于单机应用.具备如下功能: 线程安全,多 goroutine 并发安全访问: 每个 item 可以设置过期时间(或无过期时间): 自动定期清理过期的 item: 可以自定义清理回调函数: 这里的 item

  • GoFrame gcache 缓存控制 淘汰策略

    目录 打印结果 缓存控制 打印结果 场景分析 代码示例 打印结果 GetOrSetFunc的使用 基本概念 gcache模块默认提供的是一个高速的内存缓存,操作效率非常高效,CPU性能损耗在ns纳秒级别.使用简单易上手,非常适合单机应用使用. 基本使用 我们可以通过gcache.New()创建一个缓存对象 也可以直接使用gcache包方法,使用方式都是一样的. 下面代码段介绍了gcache的基本使用: package main import ( "fmt" "github.c

  • golang cache带索引超时缓存库实战示例

    目录 正文 定义泛型函数 Filter 函数 Map 函数 First 函数 带超时的cache cache 结构 集合操作 set 结构 带索引的cache index 结构 正文 cache 是一个带索引带超时的缓存库 目的在于优化代码结构,提供了若干实践. https://github.com/weapons97/cache example 定义泛型函数 1.18 已经发布一段实践了.通过泛型函数.我们可以减少循环的使用,优化代码结构.下面分享几个泛型函数和代码上的实践. Filter 函

  • C语言学生管理系统源码分享

    本文实例为大家分享了C语言学生管理系统源码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> //结构体可以存放的学生信息最大个数,不可变变量 int const MAX_LENGTH=100; //学生信息结构体数组,最多可以存放100个学生信息 struct student{ int id; //学号 char *name; //姓名 int age; //年龄 float c_score; //C语言成绩 float engl

  • Python源码学习之PyType_Type和PyBaseObject_Type详解

    PyType_Type和PyBaseObject_Type PyObject和PyTypeObject内容的最后指出下图中对实例对象和类型对象的理解是不完全正确的, 浮点类型对象全局唯一,Python在C语言层面实现过程中将其定义为一个全局静态变量,定义于Object/floatobject.c中,命名为PyFloat_Type. PyTypeObject PyFloat_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "float&quo

  • Python源码学习之PyObject和PyTypeObject

    前言 Python是C语言实现的,因此Python对象在C语言层面应该是一个结构体 ,组织对象占用的内存. 不同类型的对象,数据及行为均可能不同,因此可以大胆猜测:不同类型的对象由不同的结构体表示. 对象也有一些共性,比如每个对象都需要有一个引用计数,用于实现垃圾回收机制.因此,还可以进一步猜测:表示对象的结构体有一个公共头部. 一. 实例对象的基石-PyObject和PyVarObject PyObject和PyVarObject本质上是对象的头部信息. 1.1 PyObject结构体 Pyt

  • 企业级使用LAMP源码安装教程

    目录 LAMP架构 1.lamp介绍 2.web服务工作流程 web服务器的资源分为俩种:静态和动态资源 web服务器如何处理客户端的请求 2.1cgi和fastcgi 2.2httpd与php结合 2.3web工作流程 3.LAMP平台构建 环境: lamp安装的顺序: 3.1安装httpd 3.2安装mysql 3.3安装php 3.4配置php 3.5配置apache 4.博客创建1 5.服务开机自启配置选择性使用 LAMP架构 (同一台服务器上搭建) 1.lamp介绍 lamp,由lin

  • Python内建类型int源码学习

    目录 1 int对象的设计 1.1 PyLongObject 1.2 整数的布局 1.3 小整数静态对象池 1.4 示例 2 大整数运算 2.1 整数运算概述 2.2 大整数运算处理过程 1.long_add()源码: 2.绝对值加法x_add() 3 其他 大整数转float溢出 “深入认识Python内建类型”这部分的内容会从源码角度为大家介绍Python中各种常用的内建类型. 问题:对于C语言,下面这个程序运行后的结果是什么?是1000000000000吗? #include <stdio

  • Python内建类型str源码学习

    目录 引言 1 Unicode 2 Python中的Unicode 2.1 Unicode对象的好处 2.2 Python对Unicode的优化 3 Unicode对象的底层结构体 3.1 PyASCIIObject 3.2 PyCompactUnicodeObject 3.3 PyUnicodeObject 3.4 示例 4 interned机制 5 总结 引言 “深入认识Python内建类型”这部分的内容会从源码角度为大家介绍Python中各种常用的内建类型. 在介绍常用类型str之前,在上

  • Python对象的底层实现源码学习

    目录 1. PyObject:对象的基石 2. PyVarObject:变长对象的基础 2.1 浮点对象 2.2 列表对象 3. PyTypeObject:类型的基石 4. PyType_Type:类型的类型 5. PyBaseObject_Type:类型之基 6. 补充 在“Python源码学习笔记:Python万物皆对象”中,我们对Python的对象类型体系有了一定的认识,这篇博客将从源码层面来介绍Python中万物皆对象的底层实现. 1. PyObject:对象的基石 在Python解释器

  • Python虚拟机栈帧对象及获取源码学习

    目录 Python虚拟机 1. 栈帧对象 1.1 PyFrameObject 1.2 栈帧对象链 1.3 栈帧获取 2. 字节码执行 Python虚拟机 注:本篇是根据教程学习记录的笔记,部分内容与教程是相同的,因为转载需要填链接,但是没有,所以填的原创,如果侵权会直接删除.此外,本篇内容大部分都咨询了ChatGPT,为笔者解决了很多问题. 问题: 在Python 程序执行过程与字节码中,我们研究了Python程序的编译过程:通过Python解释器中的编译器对 Python 源码进行编译,最终获

  • vue从使用到源码实现教程详解

    搭建环境 项目github地址 项目中涉及了json-server模拟get请求,用了vue-router: 关于Vue生命周期以及vue-router钩子函数详解 生命周期 1.0版本 1.哪些生命周期接口 init Created beforeCompile Compiled Ready Attatched Detached beforeDestory destoryed 2.执行顺序 1. 不具有keep-alive 进入: init->create->beforeCompile->

  • Bootstrap源码学习笔记之bootstrap进度条

    基本样式 要实现进度条效果要使用两个容器,外容器使用"progress"样式,子容器使用"progress-bar"样式.例如: <div class="progress"> <div class="progress-bar" style="width:40%"></div> </div> progress样式主要设置进度条容器的背景色,容器高度.间距等,pr

随机推荐