leveldb源码剖析---缓存系统

2023-12-16 16:38

本文主要是介绍leveldb源码剖析---缓存系统,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

通过前面的分析可以知道,leveldb为了提高写的性能,牺牲了部分的读性能。最差的情况可能需要遍历各个level中的每个文件。为了缓解读性能,leveldb引入了缓存机制,当然,版本信息中包含各个level的文件元信息在一定程度上也可以提高读性能。


leveldb提供的缓存系统的底层数据结构是一个开链哈希

class ShardedLRUCache : public Cache :LRUCache shard_[kNumShards];
  • 1
  • 2
  • 3

它是一个数组,其中数组中的每个元素包含两个链表,和一个用于加速链表元素查找的哈希表 table_。

class LRUCache:....LRUHandle lru_;LRUHandle in_use_; HandleTable table_;....
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

链表中的每个元素就表示一个缓存单元–LRUHandle

LRUHandle :void* value;char key_data[1];....LRUHandle* next_hash; //这个指针是用来将LRUHandle链到hashtable中的LRUHandle* next;LRUHandle* prev;...
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

这里我们只关注这一部分元素。首先是链表元素的主要内容,我们可以看到,每个链表元素都是一个key-value形式的数据

1. 其中key 为对应sstable的file_number,通过它可以打开磁盘上的其所指向的sstable文件。
2. value为TableAndFile,里面包含这个sstable文件的许多元信息,包括 index_block,metadataindex_block信息等。

这里需要提一下,前面在分析版本控制时,可以看到每个版本都会包含所有level的各个文件的元信息,需要注意的是,版本信息里里面的元信息为FileMetaData,和它相比,TableAndFile包含有文件的更多信息。


这里我们简单理一下FileMetaData和TableAndFile是怎么互相帮助提高读性能的:
当用户调用leveldb的get函数,期望获得对应key的value时
1. leveldb先从版本信息中检查各个level中的各个文件的FileMetaData,查看这个key是否有可能存在于对应的sstable中
2. 如果有可能存在在这个sstable中,则根据这个sstable文件的FileMetaData提供的file_number在缓存中找到对应的TableAndFile;当然,如果缓存中没有这个sstable的TableAndFile,则从磁盘中将其读进来。
3. 进一步根据TableAndFile中的index_block,metadata_block等信息确定该key是否在这个sstable中。

具体的细节可以从

Status DBImpl::Get(const ReadOptions& options,const Slice& key,std::string* value)
  • 1
  • 2
  • 3

函数的实现中找到


下面我们继续分析缓存系统:

除了存储缓存具体数据的元素之外,缓存链表中还包括链表组织的数据
next,prev表示这是一个双向链表。它将缓存系统中的所有sstable缓存元数据组织了起来。前面讲到,为了方便缓存查找,leveldb使用了开链哈希。但是开链哈希也有可能存在问题,比如如果开链数组中单个元素指向的链表过长,则对这个链表的线性扫描还是会非常耗费时间。为了解决这个问题,leveldb在每个链表上再建立了一层哈希。这就是结构中next_hash的作用。因此leveldb利用了二维哈希来缓解了对于开链哈希可能存在的单个链表过长的问题。

如果我们深入看HandleTable的代码,就会发现,它也是一个开链哈希。通过next_hash将元素链在这个哈希表中。

最后,缓存系统中有两条链表 :in_lru_和in_use_。

作用是显而易见的。我们知道链表中的每个元素(LRUHandle)用

 uint32_t refs; 
  • 1

来做为引用计数标记该元素目前正在被多少个用户使用,显然如果refs>0,这个元素是不能从缓存中被删除的。这里需要注意的是,缓存系统本身也是这个元素的一个用户,因此从 Cache::Handle* LRUCache::Insert函数中可以看到,每个插入新插入的元素的refs都为2,表示它有两个用户,分别是
1. cache系统本身
2. 调用insert的用户

那很自然的一个问题是这个元素什么时候才被删除呢?自然是它的用户数为0的时候。当一个元素的引用计数为1时,说明它只有cache系统一个用户,此时,将它移动到lru_链表中,在这个链表中的元素随时可以被删除掉,因为没有上层用户对它使用了。它的真正删除发生在缓存系统的容量满载时,判断满载自然也是在 LRUCache::Insert函数中。当元素只cache一个用户时,则放在lru_链表中,当缓存满载时,从lru_链表中删除。如果有上层用户在使用这个元素,则将它放在in_use_链表中。缓存系统的负载是使用

 size_t usage_;
  • 1

来记录的。缓存系统的容量是用

 size_t capacity_;
  • 1

记录的。

至此leveldb的缓存系统的主要部分就讲完了。


总结

leveldb引入了缓存系统来改善它的读性能。缓存系统本质上是将最近读过的sstable文件的元信息(TableAndFile)放在内存中,以避免每次读取数据时都要直接读盘。在读取某个给定key的value时,leveldb首先通过版本信息找到可能包含该key的文件的file_number,然后通过这个file_number找到缓存系统中保存的更加完整的文件元信息。如果缓存系统中没有这个file_number对应的元素,则需要读盘,并在内存中创建对应这个sstable文件的TableAndFile,并插入缓存中。

缓存系统是通过二维开链哈希将缓存中所有的sstable的元信息组织起来的。并利用引用计数设计了二层的缓存,将暂时不用的元素也依旧缓存在系统中,只有负载过高时才真正删除。当然为了避免同步问题,对缓存元素的链表操作必须在临界区内。

这篇关于leveldb源码剖析---缓存系统的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/501160

相关文章

MySQL8.0设置redo缓存大小的实现

《MySQL8.0设置redo缓存大小的实现》本文主要在MySQL8.0.30及之后版本中使用innodb_redo_log_capacity参数在线更改redo缓存文件大小,下面就来介绍一下,具有一... mysql 8.0.30及之后版本可以使用innodb_redo_log_capacity参数来更改

在不同系统间迁移Python程序的方法与教程

《在不同系统间迁移Python程序的方法与教程》本文介绍了几种将Windows上编写的Python程序迁移到Linux服务器上的方法,包括使用虚拟环境和依赖冻结、容器化技术(如Docker)、使用An... 目录使用虚拟环境和依赖冻结1. 创建虚拟环境2. 冻结依赖使用容器化技术(如 docker)1. 创

CentOS系统Maven安装教程分享

《CentOS系统Maven安装教程分享》本文介绍了如何在CentOS系统中安装Maven,并提供了一个简单的实际应用案例,安装Maven需要先安装Java和设置环境变量,Maven可以自动管理项目的... 目录准备工作下载并安装Maven常见问题及解决方法实际应用案例总结Maven是一个流行的项目管理工具

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存(InnoDBBufferPool)和二级缓存(QueryCache),文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

C#实现系统信息监控与获取功能

《C#实现系统信息监控与获取功能》在C#开发的众多应用场景中,获取系统信息以及监控用户操作有着广泛的用途,比如在系统性能优化工具中,需要实时读取CPU、GPU资源信息,本文将详细介绍如何使用C#来实现... 目录前言一、C# 监控键盘1. 原理与实现思路2. 代码实现二、读取 CPU、GPU 资源信息1.

在C#中获取端口号与系统信息的高效实践

《在C#中获取端口号与系统信息的高效实践》在现代软件开发中,尤其是系统管理、运维、监控和性能优化等场景中,了解计算机硬件和网络的状态至关重要,C#作为一种广泛应用的编程语言,提供了丰富的API来帮助开... 目录引言1. 获取端口号信息1.1 获取活动的 TCP 和 UDP 连接说明:应用场景:2. 获取硬

JAVA系统中Spring Boot应用程序的配置文件application.yml使用详解

《JAVA系统中SpringBoot应用程序的配置文件application.yml使用详解》:本文主要介绍JAVA系统中SpringBoot应用程序的配置文件application.yml的... 目录文件路径文件内容解释1. Server 配置2. Spring 配置3. Logging 配置4. Ma

2.1/5.1和7.1声道系统有什么区别? 音频声道的专业知识科普

《2.1/5.1和7.1声道系统有什么区别?音频声道的专业知识科普》当设置环绕声系统时,会遇到2.1、5.1、7.1、7.1.2、9.1等数字,当一遍又一遍地看到它们时,可能想知道它们是什... 想要把智能电视自带的音响升级成专业级的家庭影院系统吗?那么你将面临一个重要的选择——使用 2.1、5.1 还是

高效管理你的Linux系统: Debian操作系统常用命令指南

《高效管理你的Linux系统:Debian操作系统常用命令指南》在Debian操作系统中,了解和掌握常用命令对于提高工作效率和系统管理至关重要,本文将详细介绍Debian的常用命令,帮助读者更好地使... Debian是一个流行的linux发行版,它以其稳定性、强大的软件包管理和丰富的社区资源而闻名。在使用