首页 > 其他分享 >从Bitcask存储模型谈超轻量级KV系统设计与实现

从Bitcask存储模型谈超轻量级KV系统设计与实现

时间:2024-01-13 16:57:34浏览次数:23  
标签:Bitcask 数据文件 value KV key offset byte 轻量级

Bitcask介绍

Bitcask是一种“基于日志结构的哈希表”(A Log-Structured Hash Table for Fast Key/Value Data)

Bitcask 最初作为分布式数据库 Riak 的后端出现,Riak 中的每个节点都运行一个 Bitcask 实例,各自存储其负责的数据。

抛开论文,我们先通过一篇博客 # Bitcask — a log-structured fast KV store 来了解bitcask的细节信息,下面是简要的译文。

Bitcask 设计

Bitcask 借鉴了大量来自日志结构文件系统和涉及日志文件合并的设计,例如 LSM 树中的合并。它本质上是一个目录,包含固定结构的追加日志文件和一个内存索引。内存索引以哈希表的形式存储所有键及其对应的值所在数据文件中的偏移量和其他必要信息,用于快速查找到对应的条目。

数据文件

数据文件是追加日志文件,存储键值对和一些元信息。一个 Bitcask 实例可以拥有多个数据文件,其中只有一个处于活动状态,用于写入,其他文件为只读文件。

数据文件中的每个条目都有固定的结构,我们可以用类似下面的数据结构来描述:

struct log_entry {
    uint32_t crc;
    uint32_t timestamp;
    uint32_t key_size;
    uint32_t value_size;
    char key[key_size];
    char value[value_size];
};

键目录(KeyDir)

键目录是一个内存哈希表,存储 Bitcask 实例中所有键及其对应的值所在数据文件中的偏移量和一些元信息,例如时间戳,可以用类似下面的数据结构来描述:

struct key_entry {
    uint32_t file_id;
    uint32_t offset;
    uint32_t timestamp;
};

写入数据

将新的键值对存储到 Bitcask 时,引擎首先将其追加到活动数据文件中,然后在键目录中创建一个新条目,指定值的存储位置。这两个动作都是原子性的,意味着条目要么同时写入两个结构,要么都不写入。

更新现有键值对

Bitcask 直接支持完全替换值,但不支持部分更新。因此,更新操作与存储新键值对非常相似,唯一的区别是不会在键目录中创建新条目,而是更新现有条目的信息,可能指向新的数据文件中的新位置。

与旧值对应的条目现在处于“游离状态”,将在合并和压缩过程中显式地进行垃圾回收。

删除键

删除键是一个特殊的操作,引擎会原子性地将一个新的条目追加到活动数据文件中,其中值等于一个标志删除的特殊值,然后从内存键目录中删除该键的条目。该标志值非常独特,不会与现有值空间冲突。

读取键值对

从存储中读取键值对需要引擎首先使用键目录找到该键对应的数据文件和偏移量。然后,引擎从相应的偏移量处执行一次磁盘读取,检索日志条目。检索到的值与存储的校验码进行正确性检查,然后将值返回给客户端。

该操作本身非常快速,只涉及一次磁盘读取和几次内存访问,但可以使用文件系统预读缓存进一步提高速度。

合并和压缩

正如我们在更新和删除操作中看到的,与键关联的旧条目保持原样,处于“游离状态”。这会导致 Bitcask 消耗大量磁盘空间。为了提高磁盘利用率,引擎会定期将较旧的已关闭数据文件压缩成一个或多个新数据文件,其结构与现有数据文件相同。

合并过程遍历 Bitcask 中所有只读文件,生成一组数据文件,只包含每个存在的键的“最新”版本。

快速启动

如果 Bitcask 发生故障并需要重启,它必须读取所有的数据文件并构建一个新的键目录(KeyDir),如果没有专门存储,需要读取所有文件重建。

其实上面的合并和压缩操作可以部分缓解这个问题,一方面它们减少了需要读取的最终会被废弃的数据量,在合并的同事,可以生成一个hint提示文件,hint记录了key和key指向的meta信息。 这样读取hint文件就可以快速重建键目录(KeyDir)。

*Bitcask 评价

优点

  • 读写操作延迟低:Bitcask 的读写操作都非常快速,因为它只需要一次磁盘查找即可检索任何值。
  • 高写入吞吐量:Bitcask 的写入操作是追加式的,并且不需要进行磁盘寻道,因此可以实现高写入吞吐量。
  • 可预测的查找和插入性能:由于其简单的设计,Bitcask 的查找和插入性能非常可预测,这对于实时应用程序非常重要。
  • 崩溃恢复快:Bitcask 的崩溃恢复速度很快,因为它只需要重建 KeyDir 即可。
  • 备份简单:Bitcask 的备份非常简单,只需复制数据文件目录即可。

缺点

  • KeyDir 占用内存:KeyDir 需要将所有键存储在内存中,这对系统的 RAM 容量提出了较高的要求,尤其是在处理大型数据集时。

解决方案

  • 分片:可以将键进行分片,将数据分布到多个 Bitcask 实例中,从而水平扩展系统并降低对内存的需求。这种方法不会影响基本的 CRUD(Create、Read、Update、Delete)操作。

为何要考虑自研轻量级KV系统

我们线上的搜索系统,检索到match的doc后,需要通过id获取doc的详情,考虑到数据量级很大,redis首先排除,我们最初的选型是mongodb,在十亿级别的数据量时,整体问题不大,但是面向未来更大的数据量级,我们需要考虑更容易维护的方案。

当前mongodb的问题:

  • mongodb的存储满了后,扩容较难
  • 每天增量数据写入,影响读取性能
  • 三地的集群,数据的一致性保障并非一件简单的事情
  • 最重要的,我们的使用场景仅仅是kv查询,mongodb在这个场景有点大材小用了

为了解决上面的问题,我们考虑一种数据分版本的方案。

具体来说,对于KV场景,将每个版本的数据,根据特定的hash规则将数据分成多片,每片离线按照Bitcask的思路,生成好hint文件和数据文件,上接一个分布式服务提供查询即可。对于增量的数据,只需要按同样的hash规则,先生成好数据,将数据文件加载即可,这样可以确保数据的一致。同一组的slot文件,如果一台机器加载不下,可以多台机器加载,分布式服务做好控制即可。查询时,像对key做hash,然后并发去查询对应slot的服务即可。

轻量级KV系统设计

实际系统中,数据的key都是int64数据,value是json string,我们来设计hint和data文件格式。在不考虑校验的情况下,我们可以用最简单的文件格式来存储。

离线写入

hint格式,按照 key,value length,offset 依次写入。

|  int64  key | int32 value length |  int64 value offset |  ... | int64  key | int32 value length |  int64 value offset |

data 格式,直接append 压缩后的数据。

|  compressed value bytes | ... |  compressed value bytes |

简单的java代码实现:


FileOutputStream dataFileWriter = new FileOutputStream (outputFile);  
FileOutputStream indexFileWriter = new FileOutputStream(outPutIndex);  
long offset = 0;  
int count = 0;  
while (dataList.hasNext()) {  
    Document doc = dataList.next();  
    Long id = doc.getLong("_id");  
    byte[] value = compress(doc.toJson(),"utf-8");  
    byte[] length = intToByteLittle(value.length);  
  
    dataFileWriter.write(value);  
    offset +=  value.length;  
  
    indexFileWriter.write(longToBytesLittle(id));  
    indexFileWriter.write(length);  
    indexFileWriter.write(longToBytesLittle(offset));  
  
    count++;  
    if (count % 10000 == 0) {  
        log.info("already load {} items", count);  
        indexFileWriter.flush();  
        dataFileWriter.flush();  
    }  
}  
  
indexFileWriter.close();  
dataFileWriter.close();

在线读取

读取,需要先读取hint索引文件,加载到内存。

// read index  
FileInputStream indexReader = new FileInputStream(indexFile);  
  
// id 8字节, offset 4字节  
byte[] entry = new byte[8+4+8];  
byte[] idBytes = new byte[8];  
byte[] lengthBytes = new byte[4];  
byte[] offsetBytes = new byte[8];  
Map<Long, Pair<Long, Integer>> id2Offset = new HashMap<>();  
// 这里直接加载到map里,可以优化  
while(indexReader.read(entry, 0, entry.length) > 0) {  
  
    System.arraycopy(entry,0, idBytes, 0, 8);  
    System.arraycopy(entry,8, lengthBytes, 0, 4);  
    System.arraycopy(entry,12, offsetBytes, 0, 8);  
    
    long id = EncodingUtils.bytesToLongLittle(idBytes);  
    int dataLength =  EncodingUtils.bytes2IntLittle(lengthBytes);  
    long offset =  EncodingUtils.bytesToLongLittle(offsetBytes);  
    id2Offset.put(id, Pair.of(offset, dataLength));  
}

从数据文件读取数据也会比较简单,先从hint数据获取到key对应的offset和dataLength,然后读取数据解压即可。

RandomAccessFile dataFileReader = new RandomAccessFile(dataFile, "r");  
while(true) {  
    System.out.print("请输入查询key:");  
    String key =  System.console().readLine();  
    long id = Long.parseLong(key);  
    if (id2Offset.containsKey(id)) {  
        long offset = id2Offset.get(id).getFirst();  
        int dataSize =  id2Offset.get(id).getSecond();  
        dataFileReader.seek(offset);  
        byte[] data = new byte[dataSize];  
        dataFileReader.read(data, 0, data.length);  
        byte[] decodeData = uncompress(data);  
        System.out.println(new String(decodeData));  
    }  
}

上面仅仅是demo性质的代码,实际过程中还要考虑数据的完整性检验,以及LRU缓存等。

总结

没有最好的K-V系统,只有最适合应用业务实际场景的系统,做任何的方案选择,要结合业务当前的实际情况综合权衡,有所取有所舍。

标签:Bitcask,数据文件,value,KV,key,offset,byte,轻量级
From: https://www.cnblogs.com/xiaoqi/p/17962558/simple-kv

相关文章

  • virt-top 命令查看kvm虚拟机的资源使用情况
    命令介绍virt-top:a'top'-likeutilityforvirtualizationSUMMARYvirt-top[-options]OPTIONS-1StartbydisplayingpCPUs(default:tasks)-2Startbydisplayingnetworkinterfaces-3Startb......
  • 界面组件DevExpress WPF v23.2 - 更轻量级的主题支持
    DevExpressWPFSubscription拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。DevExpressWPF控件日前正式发布了......
  • 简洁、轻量级的 Go API 框架
    本次分享的框架是「gin-api-mono」介绍gin-api-mono前先了解go-gin-apigo-gin-api这是一个基于Gin的API框架,它提供了WEB界面一键安装的方式,让你可以快速启动一个开箱即用的Go项目。无论你是否有项目经验,这个框架都适合作为练手项目使用(新手入门必备)。该框架采用了......
  • Flutter中GridTile中图像上方的InkVell波纹
    Flutter中GridTile中图像上方的InkVell波纹我认为这是在图像上显示波纹效果的更好方法。Ink.image(image:AssetImage('sample.jpg'),fit:BoxFit.cover,child:InkWell(onTap:(){},),),使用Stack,我们可以将Material和InkWell带到图像上。要拉伸材......
  • 怎么完全删除KVM虚拟机
    使用KVM创建的虚拟机确定不需要了可以使用以下方式删除找到改虚拟机对应的磁盘列出虚拟机磁盘,假如需要删除虚拟机名为CentOSES01213#virshdomblklistCentOSES01213目标源----------------------------------hda/kvm/CentOSES01213.qcow2hdb-删除虚拟机#停......
  • 浅谈10kV站所柜内运行状态及环境指标监测管理平台分析
    安科瑞张田田摘要:在整个电能管理系统中,配电室综合监控占据着重要的位置。现阶段,配电室通常均运用无人值守、定时巡查制度,此方式不仅需要投入诸多的物力与人力,同时也不能实时监控配电室的安全与环境。而配电室环境的可靠性与稳定性直接影响着变压器等设备的正常运行。对此,主要对10kV......
  • go-carbon v2.3.1 发布,轻量级、语义化、对开发者友好的 Golang 时间处理库
    carbon是一个轻量级、语义化、对开发者友好的golang时间处理库,支持链式调用。目前已被awesome-go收录,如果您觉得不错,请给个star吧github.com/golang-module/carbongitee.com/golang-module/carbon安装使用Golang版本大于等于1.16//使用github库goget-ugithu......
  • 低代码之光!轻量级 GUI 的设计与实现
    前言每当提起低代码,很多人都会下意识的出现过激反应,吐槽低代码都是**,唯恐避之不及。可能大部分人觉得低代码就是替代手写代码,对于程序员来说这是不可接受的。其实低代码表述的含义非常宽泛,我相信很多人可能都在低代码平台中受益过,而且确实可以提升效率。像原型工具(Figma)、建站平......
  • 轻量级力量:深入MiniZip库,实现C++中ZIP文件的简便压缩与解压
     MiniZip是一个轻量级的压缩库,它是zlib库的一部分,用于在C++中进行ZIP文件的压缩和解压缩操作。以下是MiniZip的一些功能和优点:功能:创建ZIP文件: MiniZip可以用于创建包含一个或多个文件的ZIP归档。压缩: MiniZip支持使用不同的压缩算法对文件进行压缩,例如DEFLATE。解压缩......
  • Windows平台如何实现RTSP拉流添加动态水印|视频处理后转推RTMP或轻量级RTSP服务
     技术背景我们在做Windows平台流数据转发的时候,除了常规的RTSP转RTMP推送外,还有个场景就是,好多开发者希望拉取的RTSP流,做二次视频分析,或者加动态水印等,处理后的数据,再二次编码推送到RTMP服务或轻量级RTSP服务。技术实现本文就以Windows平台拉取RTSP流,回调yuv数据到上层,处理后的数......