正文 

当前位置： 首页 > java > java教程

bitcask存储模型

gccbuaa gccbuaa     2022-09-01     111

关键词：

----《大规模分布式存储系统：原理解析与架构实战》读书笔记

近期一直在分析OceanBase的源代码，恰巧碰到了OceanBase的核心开发人员的新作《大规模分布式存储系统：原理解析与架构实战》.看完样章后决定入手，果然物有所值。

对于准备学习分布式的同学，这是一本不错的书籍，相对系统，全面的介绍了分布式的相关技术和项目，基本都是干货。

另一半是在介绍OceanBase的内容，对我来说，正是踏破铁鞋无觅处。接下来会有几篇专门研究存储引擎的读书笔记哟。废话不多说，转入正题。

1.存储的介质与读写

谈存储。那么理解存储的介质的特性显然非常重要。书中谈了非常多硬件结构，但最重要的结论，都浓缩在存储介质对照这张表中了。

磁盘介质对照

类别 每秒读写(IOPS)次数 每GB价格(元) 随机读取 随机写入
内存 千万级 150 友好 友好
SSD盘 35000 20 友好 写入放大问题
SAS磁盘 180 3 磁盘寻道 磁盘寻道
SATA磁盘 90 0.5 磁盘寻道 磁盘寻道

从表中能够看出，内存的随机读写能力最强，远超SSD盘和磁盘。可是我们都知道。内存无法持久化。如今很多公司在性能要求高的地方都使用了SSD盘。相对SAS和SATA磁盘，随机读取速度有了非常大的提升。

可是对于随机写入，存在写入放大问题。

写入放大问题与SSD盘的特性有关，SSD盘不能随机写入，仅仅能整块整块的写入。最简单的样例，比方要写入一个4KB的数据。最坏的情况就是，一个块里已经没有干净空间了，可是有无效数据能够擦除，所以主控就把全部的数据读出来。擦除块，再加上这个4KB新数据写回去，这个操作带来的写入放大就是: 实际写4K的数据，造成了整个块（512KB）的写入操作，那就是128倍放大。此外，SSD盘的寿命也有写入次数相关。

假设使用SSD来作为存储引擎的存储介质。最好从设计上降低或避免随机写入，使用顺序写入取而代之。

2.Bitcask存储模型介绍

存储系统的基本功能包含：增、删、读、改。当中读取操作有分为顺序读取和随机读取。

整体来说，大部分应用使用读的功能最多，解决读的性能是存储系统的重要命题。一般来说。高速查找的思想基本源自二分查找法和哈希查询。

比如关系数据库中经常使用的B+存储模型就是使用二分查找的思想，当然，实际实现比二分查找复杂非常多。B+存储模型支持顺序扫描。另外一类则是基于哈希思想的键值模型，这类模型不支持顺序扫描，仅支持随机读取。

今天要讨论的Bitcask模型是一种日志型键值模型。

所谓日志型，是指它不直接支持随机写入。而是像日志一样支持追加操作。

Bitcask模型将随机写入转化为顺序写入。有两个优点：

  • 提高随机写入的吞吐量，由于写操作不须要查找。直接追加就可以
  • 假设使用SSD作为存储介质，可以更好的利用新硬件的特性

Bitcask中存在3种文件，包括数据文件,索引文件和线索文件(hint file,姑且就叫线索文件吧)。数据文件存储于磁盘上，包括了原始的数据的键值信息；索引文件存在于内存，用于记录记录的位置信息，启动Bitcask时。它会将所有数据的位置信息所有读入一个内存中的哈希表，也就是索引文件；线索文件(hint file)并非Bitcask的必需文件，它的存在是为了提供启动时构建索引文件的速度。

2.1 日志型的数据文件

Bitcask的数据文件组织例如以下图：随意时刻。系统中仅仅有一个数据文件支持写入。称为active data file。其余的数据文件都是仅仅读文件，称为older data file。


技术分享


文件里的数据结构很easy，是一条一条的数据写入操作。每一条数据的结构例如以下：

技术分享

上面数据项分别为：后面几项的crc校验值,时间戳,key，value，key的大小。value的大小。
数据文件里就是连续一条条上面格式的数据，例如以下图：

技术分享

2.2 索引哈希表

索引哈希表记录了所有记录的主键和位置信息，索引哈希表的值包括了：记录文件的编号,value长度,value的在文件里的位置和时间戳。Bitcask的整体数据结构例如以下图：

技术分享

2.3 线索文件(hint file)

Bitcask启动时要重建索引哈希表。假设数据量特别大。则会导致启动非常慢。

而线索文件(hint file)则是用来加速启动时重建哈希表的速度。线索文件(hint file)的记录与数据文件的格式基本同样，唯一不同的是数据文件记录数据的值。而线索文件(hint file)则是记录数据的位置。


技术分享

这样在启动的时候就能够不用读数据文件，而是读取线索文件(hint file)。一行行重建就可以，大大加快了哈希表的重建速度。

3. Bitcask功能介绍

上节提到，存储系统的基本功能包含：增、删、读、改。

那么Bitcask中怎样实现的呢？

  1. 怎样添加记录？
    用户写入的记录直接追加到活动文件，因此活动文件会越来越大。当到达一定大小时。Bitcask会冻结活动文件。新建一个活动文件用于写入，而之前的活动文件则变为了older data file。

    写入记录的同一时候还要在索引哈希表中加入索引记录。

  2. 怎样删除记录？
    Bitcask不直接删除记录。而是新增一条同样key的记录，把value值设置一个删除的标记。原有记录依旧存在于数据文件里。然后更新索引哈希表。

  3. 怎样改动记录？
    Bitcask不支持随机写入。

    由于对于存储系统的基本功能中的增和改。实际上都是一样的。都是直接写入活动数据文件。同一时候改动索引哈希表中相应记录的值。

    (这个时候。实际上数据文件里同一个key值相应了多条记录，依据时间戳记录来推断，以最新的数据为准。

    )

  4. 怎样读取记录?
    读取时，首先从索引哈希表中定位到记录在磁盘中位置，然后通过IO读取出相应的记录。

  5. 合并(Marge)操作
    Bitcask这样的仅仅增不减地不断写入，必定会是数据文件不断的膨胀。而当中有很多是被标记删除和改动后留下的无用记录。合并操作就是为了剔除这部分数据，减小数据文件大小。
    merge操作。通过定期将全部older data file中的数据扫描一遍并生成新的data file（没有包含active data file 是由于它还在不停写入）。假设同一个Key有多条记录。则仅仅保留最新的一条。

    从而去掉数据文件里的冗余数据。并且进行合并(Marge)操作时，还能够顺带生成线索文件(hint file)。合并(Marge)操作一般会在数据库较闲的时候进行。比方凌晨一两点等。

4.总结

Bitcask是一个精炼的键值存储模型。採用日志型的数据结构。仅仅追加不改写就记录，提高了随机写入的吞吐量，通过建立哈希表来加快查询速度，定期合并数据文件。并生成线索文件(hint file)，提高启动时重建哈希表的速度。

这是我參考了网上的一个python实现。并添加了部分功能后的代码:https://github.com/Winnerhust/Code-of-Book/blob/master/Large-Scale-Distributed-Storage-System/bitcask.py
除了增删读写外,主要还实现了：

  • 数据文件合并，合并时能够选择生成线索文件(hint file)
  • 能够使用线索文件(hint file)启动

參考：
bitcask
优雅的Bitcask
























跳跃表的分析与实现

...布式存储系统：原理解析与架构实战》读书笔记在了解了Bitcask存储模型后,又開始研究LSM树存储引擎。LSM在实现的过程中使用了一个非常有意思的数据结构：跳跃表。之前在《算法导论公开课》中听过这一节。当时感觉这样的结... 查看详情

分布式基础-存储引擎

...表快速定位到文件和位置，就可以迅速取到需要的值了。Bitcask折中日志型小型文件系统就采用这种存储方法，它可以提供高性能的读写，只需要经过一次磁盘的寻址就可以获取到所需要的数据。作为日志型的存储系统，Bitcask的... 查看详情

五大存储模型关系模型键值存储文档存储列式存储图形存储

...库和列式数据库解决，列式数据库在数据分析、海量存储、BI这三个领域有自己独到。1.关系型数据库(行式数据库)MySQLSybaseOracle定义：关系模型使用记录（行或者元祖）进行存储，记录存储在表中，表由 查看详情

将嵌套的 Backbone 模型存储并恢复到本地存储中

】将嵌套的Backbone模型存储并恢复到本地存储中【英文标题】：StoreandrecovernestedBackbonemodelsintolocalstorage【发布时间】：2012-08-3013:43:38【问题描述】：我正在寻找创建一个复杂的主干模型架构：主干模型A主干模型B1（A中）集合模型... 查看详情

Laravel 雄辩：用相关的新模型存储新模型

】Laravel雄辩：用相关的新模型存储新模型【英文标题】：Laraveleloquent:storenewmodelwithrelatednewmodels【发布时间】：2017-09-2315:27:58【问题描述】：我正在尝试存储一个新模型，其中包含许多相关的新模型。我有我的服务模型classServicee... 查看详情

Rails 会话存储模型对象

】Rails会话存储模型对象【英文标题】：Railssessionstoremodelobject【发布时间】：2016-07-2607:22:11【问题描述】：我使用session来存储我的购物车对象在我的购物车模型中definitialize@items=Array.newenddefclean@items=Array.newend我想使用session来存... 查看详情

动态模型、存储和视图——最好的方法

】动态模型、存储和视图——最好的方法【英文标题】：DynamicModels,Stores,andViews--Bestwayto【发布时间】：2011-11-2107:10:55【问题描述】：注意：作者是EXTJS的新手，正在尝试在他的项目中使用MVC假设我有一个数据模型不固定的Web服务... 查看详情

如何在 Django 模型上存储字典？

】如何在Django模型上存储字典？【英文标题】：HowtostoreadictionaryonaDjangoModel?【发布时间】：2010-09-2823:15:15【问题描述】：我需要在Django模型中存储一些数据。这些数据并不等于模型的所有实例。起初我考虑将模型子类化，但我试... 查看详情

一文详解rocketmq的存储模型

摘要：RocketMQ优异的性能表现，必然绕不开其优秀的存储模型。本文分享自华为云社区《​​终于弄明白了RocketMQ的存储模型​​》，作者：勇哥java实战分享。RocketMQ优异的性能表现，必然绕不开其优秀的存储模型。1整体概览首... 查看详情

为啥不使用存储库返回部分域模型结果 [关闭]

】为啥不使用存储库返回部分域模型结果[关闭]【英文标题】：Whynotusearepositorytoreturnpartialdomainmodelresults[closed]为什么不使用存储库返回部分域模型结果[关闭]【发布时间】：2018-10-0210:27:19【问题描述】：我看到一些文章指出，存... 查看详情

不能在 RedBean 中存储盒装模型？

】不能在RedBean中存储盒装模型？【英文标题】：Can\'tstoreboxedmodelinRedBean?【发布时间】：2017-01-3109:54:03【问题描述】：如何在RedBean中存储从$bean->box()返回的模型？例如，下面的代码不起作用（它只是插入一个空行）：classMod... 查看详情

在本地存储中保存模型

】在本地存储中保存模型【英文标题】：Savingamodelinlocalstorage【发布时间】：2011-11-2413:29:33【问题描述】：我正在使用带有Backbone的Jerome\'slocalStorage适配器，它非常适合收藏。但是，现在我需要保存一个模型。所以在我的模型中... 查看详情

extjs 动态存储模型网格列

】extjs动态存储模型网格列【英文标题】：extjsdynamicstoremodelgridcolumns【发布时间】：2015-03-3009:41:47【问题描述】：我遇到了一个奇怪的问题。我正在建立一个商店并调用加载函数。当存储加载时，我根据结果创建一个列模型，然... 查看详情

核心数据“找不到源存储模型”；

】核心数据“找不到源存储模型”；【英文标题】：coredata"Can\'tfindmodelforsourcestore";【发布时间】：2014-01-2311:02:11【问题描述】：问题出在这里...我在应用商店中有一个应用程序，它使用核心数据...我一直在正确更新我的... 查看详情

SailsJS 1.0：Mongo 中模型的 .create() 错误，单向关联到存储在 MySQL 中的模型

】SailsJS1.0：Mongo中模型的.create()错误，单向关联到存储在MySQL中的模型【英文标题】：SailsJS1.0:Errorin.create()foramodelinMongowithOneWayAssociationtoamodelstoredinMySQL【发布时间】：2019-01-1305:16:58【问题描述】：我有一个Users模型存储在MongoDb和... 查看详情

如何将 R 模型存储为文本？

】如何将R模型存储为文本？【英文标题】：HowtostoreanRmodelastext?【发布时间】：2014-02-2508:36:28【问题描述】：找到了一个类似的问题here，但是不全。我的问题分为两部分：我想将Rlm()对象的“精简”版本作为文本存储在DBMS中。我... 查看详情

关系数据库模型的存储结构采用啥形式

1.关系数据库模型的存储结构采用二维表格形式2.关系模型是1970年由E.F.Codd提出的。它和层次、网状模型相比，有以下特点：数据结构简单（二维表格）扎实的理论基础。关系运算理论关系模式设计理论3.关系模型：用二维表的形... 查看详情

ios coredata错误找不到源存储的模型[重复]

】ioscoredata错误找不到源存储的模型[重复]【英文标题】：ioscoredataerrorCan\'tfindmodelforsourcestore[duplicate]【发布时间】：2013-04-2011:16:08【问题描述】：我在数据模型中添加了一些更改，现在我收到了错误消息：找不到源存储的模型你... 查看详情