DBM KV数据库原理（一）

一、目的

  DBM提供了针对DBM-style、string-keyed数据库类似字典的接口。
  dbm面向DBM数据库，利用简单的字符串值作为key来访问包括字符串的记录。它内置的whichdb()方法会识别 数据库，并使用合适的模块来打开数据库。它经常也用在shelve模块的后端，shelve使用pickle模块序列化对象后存入一个DBM数据库。
  DBM对外提供的接口

extern int  dbminit (char *file);
extern datum    fetch (datum key);
extern int  store (datum key, datum content);
extern int  delete (datum key);
extern datum    firstkey (void);
extern datum    nextkey (datum key);
extern int  dbmclose (void);
二、数据库类型

  Python中自带了多个访问DBM风格数据库的模块。默认的实现取决于当前系统上可用的库和编译Python时使用的选项。与特定实现分离的接口允许Python程序与其他语言的程序交换数据，且不会自动在可用格式之间切换，也可编写在多个平台上运行的便携式数据文件。

  • dbm.gnu
      dbm.gnu是GNU项目中dbm库版本的接口，它与这里描述的其他DBM实现同样的工作，对open()方法提供了flags标志进行了一些修改。除了标准的'r'、'w'、'c'、'n'外，dbm.gun.open()还提供了：
    • 'f':表示使用fast模式打开数据库。这种模式下写入数据库是一个异步操作。
    • 's':表示使用synchronized模式打开数据库。这种模式下，对数据库所做的更改会立即写入文件，而不是在数据库关闭或其他同步操作时进行延迟写入。
    • 'u':表示使用无锁打开数据库。
      gdbm对应的接口如下：
    extern GDBM_FILE gdbm_fd_open (int fd, const char *file_name, int block_size,
int flags, void (*fatal_func) (const char *));
extern GDBM_FILE gdbm_open (const char *, int, int, int, void (*)(const char *));
extern int gdbm_close (GDBM_FILE);
extern int gdbm_store (GDBM_FILE, datum, datum, int);
extern datum gdbm_fetch (GDBM_FILE, datum);
extern int gdbm_delete (GDBM_FILE, datum);
extern datum gdbm_firstkey (GDBM_FILE);
extern datum gdbm_nextkey (GDBM_FILE, datum);
extern int gdbm_reorganize (GDBM_FILE);
extern int gdbm_sync (GDBM_FILE);
extern int gdbm_exists (GDBM_FILE, datum);
extern int gdbm_setopt (GDBM_FILE, int, void *, int);
extern int gdbm_fdesc (GDBM_FILE);
  • dbm.ndbm
      dbm.ndbm 模块提供了一个 Unix 上 ndbm 的接口实现，依赖于模块在编译时的配置。模块的 library 属性会识别出 configure 的名称然后查找出扩展模块是什么时候进行编译的。
      ndbm对应的接口如下： 
    extern DBM  *dbm_open (char *file, int flags, int mode);
extern void  dbm_close (DBM *dbf);
extern datum  dbm_fetch (DBM *dbf, datum key);
extern int  dbm_store (DBM *dbf, datum key, datum content, int flags);
extern int  dbm_delete (DBM *dbf, datum key);
extern datum  dbm_firstkey (DBM *dbf);
extern datum  dbm_nextkey (DBM *dbf);
extern int       dbm_error (DBM *dbf);
extern void      dbm_clearerr (DBM *dbf);
extern int  dbm_dirfno (DBM *dbf);
extern int  dbm_pagfno (DBM *dbf);
extern int  dbm_rdonly (DBM *dbf);
  • dbm.dumb
      当没有其他实现可用时， dbm.dumb 模块为 DBM API 提供了一个可移植的回退实现。 使用 dbm.dumb 不需要外部依赖，但比大多数其他实现要慢。
      dbm、gdbm适合存储静态的、索引话的数据结构，适用于处理那些被频繁访问但却很少被更新的数据，因为它创建数据项时非常慢，但检索数据项时非常快。
三、gdbm头文件

本系列中主要以gdbm代码为例，对dbm的原理和实现进行分析和说明。

  • 头文件
    • autoconf.h
      由configure脚本根据config.h.in模版生成。autoconf.h为平台相关的头文件、函数、库等定义常量标志。
    • systems.h
      包含平台相关的头文件和代码。一些函数不同平台名称不一致。system.h把这些函数和代码编写成统一的接口，以供程序使用，这样就隐藏了底层不同平台的差异。
    • gdbmerror.h
      gdbm的错误码列表。主要由内存分配、文件读写、文件锁定、数据库操作方面的错误。
    • gdbmconst.h
      gdbm要用到的一些常量定义。包括gdbm_open、gdbm_store、gdbm_setopt的一些常量参数、桶缓存的大小。
    • gdbmdefs.h
      包含了gdbm数据库文件的结构。这些定义具有兼容性，它们既用在gdbm中，也用在dbm、ndbm中。

四、dbm数据存储原理

  一般数据库的实现大体思路是用一个数据文件存放数据，这个数据文件其实就是普通的文件，但是文件的结构设计很复杂。另外，也可以使用一个文件来保存索引，如果数据量不是很大，则可以把索引存放在内存中(如mysql的heap)。gdbm数据库的存储方式采用的是可扩展散列表。
  散列基本思想：通过由散列函数决定键值与散列地址的对应关系来实现存储组织和查找运算，按照散列存储方式构造的存储结构称为散列表。
  散列技术：散列技术的核心是散列函数。散列函数是一种将键值映射为散列表中的存储位置的函数。对任意给定的动态查找表T，如果选定了某个理想的散列函数H以及响应的散列表L，则对T中的每个数据元素X，函数值H(X.key)就是X在散列表L中的出处位置。插入或建表时数据元素X将被放置在该文件位置上，并且查找X时也到该位置上查找。

五、gdbm数据库文件结构
  • 文件信息结构gdbm_file_info
struct gdbm_file_info
{

 char *name;                    // 文件名
 unsigned read_write :2;        // 读写模式标志
 unsigned fast_write :1;        // 同步写文件标志
 unsigned central_free :1;      //
 unsigned coalesce_blocks :1;  //
 unsigned file_locking :1;      // 文件锁标志
 unsigned memory_mapping :1;    // 是否使用mmap
 unsigned cloexec :1;          // 是否使用GDBM_CLOEXEC标志打开数据库
 unsigned need_recovery :1;    // 最后一个Fatal Error时，数据库是否需要恢复
 gdbm_error last_error;        // 最后一个错误码
 int last_syserror;            // 最后一个系统错误码
 char *last_errstr;             // 最后一个错误字符串描述
 enum { LOCKING_NONE = 0, LOCKING_FLOCK, LOCKING_LOCKF, LOCKING_FCNTL } lock_type;
 void (*fatal_err) (const char *);  // 错误处理函数指针
 int desc;                        // 文件描述
 gdbm_file_header *header;        // 文件头指针
 off_t *dir;                      // 散列表目录指针
 cache_elem *bucket_cache;        // 桶缓存数组指针
 size_t cache_size;              // 
 size_t last_read;
 hash_bucket *bucket;            // 当前缓存项读的桶指针
 int bucket_dir;                  // 当前目录项的索引
 cache_elem *cache_entry;        // 当前桶缓存项

 unsigned header_changed :1;
 unsigned directory_changed :1;
 unsigned bucket_changed :1;
 unsigned second_changed :1;
 /* Mmap info */
 size_t mapped_size_max;/* Max. allowed value for mapped_size */
 void  *mapped_region;  /* Mapped region */
 size_t mapped_size;    /* Size of the region */
 off_t  mapped_pos;     /* Current offset in the region */
 off_t  mapped_off;     /* Position in the file where the region begins */
};
  • 文件头gdbm_file_header
typedef struct
{
 int   header_magic;  // 版本
 int   block_size;    // 最佳传递大小
 off_t dir;           // 散列目录表的偏移地址
 int   dir_size;      // 目录项的大小
 int   dir_bits;      // 目录地址占用的比特数
 int   bucket_size;   // 桶的字节大小
 int   bucket_elems;  // 桶中元素个数
 off_t next_block;    // 下一个未分配的块的偏移地址
 avail_block avail;   // 可用块
} gdbm_file_header;
  • 散列桶hash_bucket
typedef struct
{
 int   av_count;                        // 可用块元素个数 
 avail_elem bucket_avail[BUCKET_AVAIL];  // 可用块元素列表
 int   bucket_bits;                     // 标识桶的二进制系列
 int   count;                           // 桶的元素个数
 bucket_element h_table[1];             // 桶的元素列表(真正的可扩展三列表，它会随着文件的增长而分裂。可用块元素中包含了可用存储块地址和大小，桶元素中包含了要管理的关键字/数据的地址和大小)
} hash_bucket;
  • 桶元素bucket_element
typedef struct
{
 int   hash_value;       // 哈希值
 char  key_start[SMALL]; // 关键字的前SMALL字节
 off_t data_pointer;     // 关键字记录的偏移地址
 int   key_size;         // 关键字的大小
 int   data_size;        // 数据大小
} bucket_element;
  • 可用块avail_block
typedef struct
{
 int   size;             // 可用块元素大小
 int   count;            // 可用块元素个数
 off_t next_block;       // 下一个可用块的偏移地址
 avail_elem av_table[1]; // 可用块元素列表
} avail_block;
  • 可用块元素avail_elem
typedef struct
{
 int   av_size;  // 可用块大小
 off_t  av_adr;  // 可用块的偏移地址(磁盘文件上各个可用存储块本身的位置不会有任何改变，而是通过操作知识可用块的avail_elem元素来对可用块进行存取)
} avail_elem;
  • 桶缓存数组bucket_cache
cache_elem *bucket_cache;  // 由多个缓存项组成的一个数组，在桶缓存初始化时，文件信息结构dbf中bucket_cache指针指向这个数组
size_t cache_size;
  • 桶缓存中的缓存项cache_elem
// 缓存中的缓存项cache_elem不仅包含了实际的桶，还包含了数据缓存块及一些标志。在桶缓存初始化时，dbf中的指针cache_entry初始时指向桶缓存中的第一个缓存项
typedef struct
{
 hash_bucket *   ca_bucket;  // 实际桶指针
 off_t           ca_adr;      // 偏移地址
 char            ca_changed;   // 更改标志
 data_cache_elem ca_data;    // 数据缓存
} cache_elem;
  • 缓存项中的数据缓存元素data_cache_elem
typedef struct
{
 int     hash_val;  // 哈希值
 int     data_size;  // 数据长度
 int     key_size;  // 关键字长度
 char    *dptr;    // 指向数据起点的指针
 size_t  dsize;    // 偏移位置值
 int     elem_loc;  //
} data_cache_elem;
  • 散列桶目录表dir
off_t *dir; // 每个元素是一个off_t类型，根据元素中存放的偏移地址值访问磁盘上相应的散列桶
gdbm fs.png

  存放在磁盘上的一个新的数据库文件只包含头文件gdbm_file_header、桶目录表dir[dir_size/4]、初始的一个桶hash_bucket(以后随着文件的增长会分裂为多个桶)，它们按照顺序存放。这里gdbm_file_header中存放了活动的可用块avali_block以及下一个可分配可用块的偏移地址，avali_block中的avali_elem猜真正指出了数据存储块的大小和偏移地址。hash_bucket中的bucket_element有指向关键字/数据的指针data_pointer（注意数据直接存储在关键字之后），关键字大小及数据的大小，同时还含有关键字的一小部分实际值。

  为了高效地对数据进行存取，这里实现了一个缓存系统，主要有缓存项cache_elem结构和数据缓存元素data_cache_elem结构。cache_elem中有指向实际的桶的指针（桶在磁盘上，用来对数据进行定位、查找、存取等），还包含了数据缓存元素及一些标志。数据缓存元素中指明了我们要存取的实际数据，通过内存中的缓存系统，我们可以大大提高数据的存取速度。

公众号:变成之禅，专注CDN、后台开发、算法和大数据，欢迎关注交流

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容