那个NoSQL数据库的实现上的一些想法

最后,放弃了JNI的方式,因为JNI的接口太恶心了。我决定先实现一个纯JAVA的先用着,除非发现效率不够我预期,否则就不换了。为啥呢? 我不就是要个简单嘛。为了简单,我更简单的是也不搞数据目录、日志目录了,整个数据库就两个文件,数据文件和日志文件。数据文件的第一个页面里面是meta info,存着table name-> tables root page number,以及其它的一些信息。

至于并发控制,我想尽力避免表锁。

按最原始的思路,每个table都是Map,Map里面存放的是value的指针或者引用。那么value还会存放其它类型的成员变量,以及Collections。那么,最原始的想法,就是每个自定义的类型,都有一个版本号和一把锁,每个table都有一个表锁。那么insert/delete语句会需要表锁。select呢?select其实也需要。因为我首先要读这个Map,然后从这个Map中查数据。那么就需要Map的version,以及所获得的记录的version。最后提交的时候,如果要达到serializable的隔离度,那么就需要重新检查这个Map的version。

我想把这个表锁去掉。换一个思路。假设我现在有一个大的Object Pool,里面有很多对象,每个对象的初始值都是null。这里所说的对象,其实只有一种类型Map.Entry\。每个对象有一个唯一标识符,(tablename,Key)。insert操作可视为把一个null的对象改成非null,delete则是反过来。那么get操作无论是否拿到了想要的数据(无论是否返回null),最终Commit的时候都再去检查一次,null是否依然是null,etc。本来想的很好,但是这样有一个漏洞,对于null,因为它是空,所以我没有地方存版本号,所以就必须假设它的版本是0。可惜,对于delete操作,应当增加Object的版本号,而不是把Object的版本号重置为0。所以这里是有问题的。可以考虑一种补救的措施,在某个点,禁止所有事务运行,然后重置版本号。所以delete操作只有在这个点的时候,才真正的删除数据,否则把key挪到一个新的Map里面,叫deletedItems,value是version,get操作在返回null的同时也要返回这个version。在重置版本号的时候,如果我不是重置所有的版本号,而是只重置null value的,也就是说只是简单的清空deletedItems。那么可以吗?

这个Map实际的实现,只是Btree上的一层cache。但是逻辑上来说,不能看作是cache。比如,我不能因为lru,导致Table的version变了。所以逻辑上来说,只有btree实际被外来的delete/insert操作更改了,

假设Value的类里面,包含了一个成员变量,是一个ArrayList,它的元素类型是另一个Object。那么对这个Object的更改,是单独记录在它自己身上的version呢,还是说它不要有version,对Map的所有get操作拿到的都是Copy而不是指针或引用? 我考虑了很久(上篇提到过)。如果要把version分散到每个类里面去,会增大内存的overhead,但是锁粒度降低了,冲突更少了。但是有另一个问题,我需要记录cache层哪些record被修改了。也就是说,任何Object的修改操作最终要反映到顶级的Map.Entry上。我想了两种办法。一种是给每个Object加一个parent字段,另一个办法是加上tablename 和key。我在想,从Object顺着parent字段回溯的过程,能保证一致性吗?还有,加了这个字段后,会对现在的使用做很多限制,比如无法实现有圈图这样的结构?

脑袋又乱了,睡吧。欢迎检查我的想法并给出意见。欢迎提供参考文档供学习。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥