一个简易数据库的实现 ---- APUE chapter 20 A Database library

A Database library 我会说明天上午十点考数据库,我现在还在写博客... 什么心态 QAQ 我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想) --------------------------------------------------------------------------------------------

A Database library

我会说明天上午十点考数据库,我现在还在写博客... 什么心态 QAQ

我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想)

----------------------------------------------------------------------------------------------------------------

正题... 之前一直搁置了 APUE的后面几章, 明天考数据库, 今天心血来潮, 反正APUE提供了实现一个数据的思路,

不妨我们自己写一个数据库. 哼╭(╯^╰)╮ 就是这么傲娇~

名字我的都想好了, 数据库的名字就叫 ..... jasper.

声明: 这个数据库不是我原创的(K神作品, 我完全... 不是一个数量级的),我会对其进行稍稍的改动...

先摆结果吧，有兴趣就看下去，也可以和我一起讨论，[e-mail]，没兴趣，浏览器点击X.

本来是想像很正规的成熟数据库那样，搭个shell出来的，感觉交互界面的字符串语法命令的分析有点＊＊

于是，就这样凑合着先表示概念吧～　想测试或者使用这个＂玩具＂数据库，需要一定的Ｃ语言基础，然后调用提供好的API即可．　

为了能够操作数据库，我们必须写个简单的调用程序～

#include "apue_db.h"
#include 
#include 

#define STRING_SZ 100
#define DATA_SET  3

int main()
{

	char str_key[DATA_SET][STRING_SZ] = {
					      {"Alpha"},
					      {"Belta"},
					      {"Gama"}
					     };

	char str_dat[DATA_SET][STRING_SZ] = {
					      {"data1"},
					      {"data2"},
				     	      {"data3"}
				    	    };

	DBHANDLE handler = db_open("./database",
				   O_CREAT | O_TRUNC | O_RDWR,
				   FILE_MODE);


	if(db_store(handler,str_key[0],str_dat[0],DB_INSERT) != 0)
	{
		printf("Error! db_store failed in function %s\n",
			                            __FUNCTION__);

		printf("Trying to store key:%s\t data:%s\n",
				      str_key[0],str_dat[0]);

		goto failed;
	}

	if(db_store(handler,str_key[1],str_dat[1],DB_INSERT) != 0)
	{
		printf("Error! db_store failed in function %s\n",
			                            __FUNCTION__);

		printf("Trying to store key:%s\t data:%s\n",
				      str_key[1],str_dat[1]);

		goto failed;
	}

	if(db_store(handler,str_key[2],str_dat[2],DB_INSERT) != 0)
	{
		printf("Error! db_store failed in function %s\n",
			                            __FUNCTION__);

		printf("Trying to store key:%s\t data:%s\n",
				      str_key[2],str_dat[2]);

		goto failed;
	}

failed:
	db_close(handler);

	return 0;
}

显然,我们想利用db_store来根据str_key来储存str_dat里面的数据

就这样把数据储存在了database.dat中，并且利用database.idx　进行索引

当然，我想看我啰啰嗦嗦写到这里的人是想看怎么实现的．．．

特地用分割线划开了．下面主要是个人的想法，或者遇到的个人觉得可能是难点的地方．

并不是＂介绍如何搞定这个数据库＂．　RTFSC ：）

有任何对这个数据有兴趣的viewer，　希望能通过邮箱交流[e-mail]

Don't panic

-------------------------------------------------------------------------------------------------------------------

如果觉得书上的代码风格不和口味，可以试试，去github拿我自己重新写的源代码

不懂的地方再对照书上的注释看就是了

https://github.com/jasonleaster/APUE_study_source_code/tree/liu/chapter_20

数据库的设计:

这个简易的数据库由两个文件构成---- index file & data file.

一个索引文件,一个数据文件. 实现索引和储存的数据进行分离. 在我个人看来, 这样做无非是让构架看得清晰.

试想,用一个文件来表述数据库的话,会很"乱", 冗长, 杂. Do you think so ? : ) 不得不佩服这些设计者的思想.

图1

最最值得强调的就是, 我们在储存地址指针的时候, 即图中你所看到所有有关ptr的标识符.

他们的储存形式都是ASCII码! 再三强调, 不然看代码会看哭的.

这是数据库设计的一大亮点,由于数据库的数据可能会被用在不同的系统,不同的硬件平台上面, 会由于系统表示数据的方式不同(大小端, 指针长度,等), 而导致数据可能不一致. 这时候有个办法,直接用ASCII码表示,以字符串的形式存在.

比方说地址 0x0010 就直接用 "16"来表示和储存.简直酷帅....

设计者假设了指针的最大长度为十进制的6位数.

图2

那个999999 == 10^(PTR_SZ) - 1

对于数据库可以进行的哪些操作,定义了以下API. (之后我会写一个类似于shell的东东, 使得控制这个数据库的语法像MySQL的语法,肯定不会是完全实现MySQL的语法,但是会很naive 很有意思, 这样以来, 最起码简单数据库的实现原理就明白了, 专杀纸老虎).

图3

用结构体DB , 对整个数据库进行抽象. 我们所有的API,不过是围绕这个对象打转转而已, 变着花样操作这个database.

我们把所有能用来描述一个数据库的东东,都写到这个结构体里面了, 这种思想的本质就是OO.

/*
 * Library's private representation of the database.
 */
typedef struct {
  int    idxfd;  /* fd for index file */
  int    datfd;  /* fd for data file */
  char  *idxbuf; /* malloc'ed buffer for index record */
  char  *datbuf; /* malloc'ed buffer for data record*/
  char  *name;   /* name db was opened under */
  off_t  idxoff; /* offset in index file of index record */
			      /* key is at (idxoff + PTR_SZ + IDXLEN_SZ) */
  size_t idxlen; /* length of index record */
			      /* excludes IDXLEN_SZ bytes at front of record */
			      /* includes newline at end of index record */
  off_t  datoff; /* offset in data file of data record */
  size_t datlen; /* length of data record */
			      /* includes newline at end */
  off_t  ptrval; /* contents of chain ptr in index record */
  off_t  ptroff; /* chain ptr offset pointing to this idx record */
  off_t  chainoff; /* offset of hash chain for this index record */
  off_t  hashoff;  /* offset in index file of hash table */
  DBHASH nhash;    /* current hash table size */
  COUNT  cnt_delok;    /* delete OK */
  COUNT  cnt_delerr;   /* delete error */
  COUNT  cnt_fetchok;  /* fetch OK */
  COUNT  cnt_fetcherr; /* fetch error */
  COUNT  cnt_nextrec;  /* nextrec */
  COUNT  cnt_stor1;    /* store: DB_INSERT, no empty, appended */
  COUNT  cnt_stor2;    /* store: DB_INSERT, found empty, reused */
  COUNT  cnt_stor3;    /* store: DB_REPLACE, diff len, appended */
  COUNT  cnt_stor4;    /* store: DB_REPLACE, same len, overwrote */
  COUNT  cnt_storerr;  /* store error */
} DB;

之前图3定义了很多操作DB的API,那么我们来一个个看这些API的实现.

上面的图3的API实现以来下面这些函数. 提一次深刻的体会到什么叫做接口与实现的分离...以后我也要这么干

图4

代码接近10^3 所以不一一拿出来扯了. 记录我觉得关键的部分吧

db_open(const char *pathname, int oflag, ...)

图5

根据pathname提供的文件名, 计算文件名的字符串长度(不包括NUL)

然后传递给_db_alloc(len), 这个_db_alloc会真正的返回一个DB结构体和我们的文件名pathname所指字符相关联.

图6

这里我们得到了初始的数据库之后,就开始初始化它, 确定好hash table在index file中的起始位置(HASH_OFF 6)以及hash table总的大小(NHASH_DEF 137), 这里的6 就是前面的PTR_SZ, 也就是说 index file的前6 byte是空出来的.

,每个hash 单元是PTR_SZ大小,一共有 NHASH_DEF个. 前面空出来的6bybe是故意的, 用来记录一个指针(用字符串表示的). 这个指针用法很特别, 后面会讲明白的, 叫free list pointer(这家伙折腾我好久).

_db_alloc

会注意到这里 malloc有分别的+ 5 , 2, 2. 这是因为db->name的时候要考虑 我们的数据库文件命名方式,要添加.dat

于是这里".dat" 就是5个char. 然后后面两个+2 是考虑到字符串输入的时候我们会带有 \n 和 NUL.

这确保了我们定义IDXLEN_MAX 和 DATLEN_MAX的严谨性!

图7

db_close 和_db_free() 感觉都很简单,只是APUE作者实现的时候有点略微..稍微.. 不安全.

API参数的指针没有进行NULL检测.

图8

万一db 是NULL 就跪的稳稳的了

db_fetch()

该函数用来根据key查找数据库中是否已经有了该项数据.

没什么值得强调的,这就是个接口, 成功找到了对应数据, OK.那返回一个指针ptr,

这个指针指向要查找的数据(指向data file)

接口的核心在于_find_and_lock()

_find_and_lock()

根据key指向的字符串,计算hash值, 然后确定hash表的入口,尝试找到对应项.

第三个参数,writelock, 旨在提供防止并发是带来的抢占问题.

read_lock 保证仅可读不可写, write_lock 既不可读也不可写.

图9

上面也看到了, db->chainoff 通过hash加上初始的hash table的起始偏置得到.

根据chianoff通过_db_readptr去找hash table 对应位置的数据,这个数据就是index的地址标记.

如果这个地址为0, while循环进不去, 最后返回-1, 提示_find_and_lock失败,就是说, 根据参数key,没有对应的数据.

如果offset非零,说明我们有可能找到了对应的数据.

只有真正一个个比对key ,而不是简单的hash值相同. 才可以判定找到了对应数据.

如果找到了,那么break 跳出while循环, 返回0. 提示我们找到这家伙了.

如果沿着hash chian的单向链表一直没找到,我们就会遇到_db_readidx返回0, 提示_find_and_lock失败.

图10

值得注意的是图10会有调用_db_readidx()

这个函数会更新data file的文件偏置,即db->datoff.

后记:

本来以为一天可以搞定的，磨磨蹭蹭搞了两天这东西......

摄于某教室　极力的试图通过空旷的场景和黑白的沉闷，表现当代高校学生的迷茫，无从与困惑