Fourinone4.0版新特性：一个高性能的数据库引擎CoolHash（酷哈嘻）
一、前言：如何写一个数据库
如果将操作系统和业务应用之间的软件都统称中间件的话，那么最重要的软件无疑是数据库，它比web应用服务器市场更大，几乎所有的业务系统都需要数据库，所有的企业都会购买数据库。无论是早期的商业智能也好，数据分析挖掘也好，近年的分布式存储也好，大数据也好...围绕数据变着花样的新理念新技术再多，都是“乱花渐欲迷人眼，浅草才能没马蹄”，其实最核心的还是数据库技术。
就像华为想进军软件市场已经很久了，我脑海里一直惦记着数据库技术，几年来不断收集数据库实现技术，但是一直不得要领，几欲放弃，没有碰到一个白胡子老头传授秘籍，国内也几乎没有这方面的书籍，找了几本国外的教材，要么翻译的不好，要么英文啃起来费劲，书里更多是讲数据库相关的基础知识，但是不会告诉你怎么做，好比是你想学变脸，但是总在教你唱戏，其实你只想知道变脸是用线拉的就行了。行业技术机密都是避而不谈的，感觉从书本上是学不到的。
去年给一个银行技术老总讲解大数据方案，他突然问到，你们能不能不用别人的，自己写个ORACLE这样的数据库出来，我们每年花在license和服务费非常昂贵，升级也很痛苦，但是也没有办法。我承诺可以抽业余时间研究一下，不过他马上又说，就算有也不会马上用，可以先开源出来，可以看出他无比纠结的心态，也许他对太多架构师说过这样的话，可能现在都忘了，但是这件事再次给了我触动，言语之间能感受到客户寄托出的一种期望，希望中国企业能成长为ORACLE、IBM这样的角色。
要实现一个数据库，首先不能不谈起数据库引擎。数据库引擎和数据库产品的关系，就像汽车发动机和汽车的关系，有了发动机，剩下的只是装配工作。知名的数据库引擎有“ISAM、MyISAM、InnoDB、PostgreSQL、BerkeleyDB等”，另外也有些产品模糊在“数据库引擎、数据库server、数据库管理系统”之间的，如近几年的redis，还有JDK6.0起自带一个java编写的只有2m大的关系数据库Derby（由IBM捐献），另外值得一提的还有SQLite，一个很轻量级嵌入式的数据库（3万c代码，250k大小），但是功能齐全，实现了ACID和SQL标准，目前广泛应用于苹果的Mac操作系统和Android移动操作系统中，缺点是多用户高并发承受能力较弱。
世界上大部分的数据库产品都是围绕部分数据库引擎扩充出来的，比如大家熟悉的Mysql，它的数据库引擎叫MyISAM，MyISAM是在ISAM发展而来，ISAM也是一个知名的数据库引擎，最初被IBM开发，它读的性能大于写，但是索引功能和事务处理缺乏，MyISAM相对于ISAM做了很多改进，优化了表锁和并发操作，但是由于继承的原因，仍然倾向于多读少写操作。ISAM系列引擎的大致设计原理：采用B树设计，分成表元数据、表数据、表索引3部分存储，读的快是因为维持大量的索引结构指向数据存储位置，但是由于删除更新容易导致大量数据碎片和空间浪费，常常需要执行“OPTIMIZE TABLE”，从而又导致索引常常需要重新计算。Mysql5.5以后默认采用InnoDB引擎，还可以使用BerkeleyDB，InnoDB和BerkeleyDB包括了对事务处理和外键的支持，这是ISAM系列引擎所没有的特性，另外InnoDB的锁设计的要精明一点，锁到少数行的数据块上，而不是整表锁。
关于ISAM系列的发展有很多，IBM开发了VSAM代替ISAM，VSAM被IBM一个数据库产品所使用 ，就是大名鼎鼎的DB2。虽然MySql的数据库引擎换成了InnoDB，但是MySql的作者迈克尔（Michael Widenius）从MySql旧版本发展了另一个分支，并以自己的小女儿名字命名为MariaDB（玛丽亚），MariaDB的数据库引擎叫做Aria，但实际上还是MyISAM，只是增加了些key缓存改进（Segmented Key Cache），MariaDB数据库得到了google等企业的大力支持，普通的观点认为oralce收购Mysql的最终目的是想其慢慢死亡，而不是想着如何把它发展更好。
PostgreSQL和BerkeleyDB都是来源于加州伯克利分校，一个面向关系数据，一个面向k/v数据，虽然知名和流行程度不如Mysql，但是也各有优势，PostgreSQL的关系数据库功能实现的比较完整，包括了很多高级特性，并且采用BSD/MIT开源协议，因此比较适合用来封装成数据库产品，这种协议允许任何人使用修改代码，但是要保留版权声明，BerkeleyDB提供了一个高并发访问的k/v数据库引擎，但不是一个数据库server，不提供网络访问，不支持sql，但可以支持函数式操作，数据库产品HyperTable和MemcacheDB内部都使用了BerkeleyDB。
综上所述，我们可以看出：
- 大部分数据库产品都是都是近亲结婚，由少数数据库引擎（如ISAM、PostgreSQL、BerkeleyDB等）发展而来。（但是oracle和sqlserver的数据库引擎是内置的，鲜有人知）
- 你会惊奇的发现，MyISAM、BerkeleyDB、InnoDB等大部分数据库引擎的vendor都是oracle，oracle公司一直处心积虑的收购着市场上有竞争力的数据库引擎，用来捍卫自己的垄断地位，
- 几乎所有的数据库引擎都是GPL协议，擅自闭源用于商业将承担法律责任。
因此，要写一个数据库，首先要从实现数据库引擎入手，掌握数据库引擎技术有重要意义，因为无论是“关系数据库还是K/V数据库，SQL数据库还是NOSQL数据库，分布式数据库还是并行数据库，列数据库还是对象数据库...”，存储引擎部分都有着相似的实现原理，掌握了数据库引擎技术后，只要公司愿意投资，就可以长足拓展到任何数据库领域，一切只是工作量问题，数据库引擎一经研发成功，就值得长期放养，哪怕是5年10年。同时对个人职业意义来说，对一个玩了一辈子软件技术的架构师，没有写过数据库是一种遗憾，就跟喜欢女优的工程师没有见过真人一样。
二、CoolHash是个什么样的数据库
1、CoolHash是一个数据库引擎
CoolHash只做数据库最基础核心的引擎部分，支持大部分数据类型的“插入、获取、更新、删除、批量插入、批量获取、批量更新、批量删除、高效查询（精确查、模糊查、按树节点查、按key查、按value查）、分页，排序、and操作、or操作、事务处理、key指针插入和查询、缓存持久互转”等操作和远程操作。
其他的“监控、管理、安全、备份、命令行操作、运维工具”等外围特性都剥离出去不做，开发者可以根据自己需求扩充这些功能，CoolHash也不做自动扩容，CoolHash认为分布式集群特性也可以在外围通过“分库分表”或者“分布式扩容”等中间件技术去做，目前国内很多企业都具备基于开源软件做外围中间件的能力，这样，CoolHash只维持一个高性能又轻量级的最小存储引擎。
CoolHash高度产品化，易用性强，容易嵌入使用和复制传播（200k大小），采用apache2.0开源协议，使用java实现(jdk1.7)，对外提供java接口，同时支持windows和linux（unix-like），由于依赖底层操作系统，windows和linux的实现稍有不同。
2、CoolHash是一个k/v数据库
实现数据库存储结构索引有多种方法，有比较平衡减少深入的b树、b+树系列，结合内存再合并的LSM-tree系列（bigTable），借鉴字典索引技术的Trie树（前缀树、三叉树）等，不过对于key/value结构，感觉最合适的还是Hash，不过java里的Hash算法是实现在内存组件里，无法持久化，只能快速读写，但是无法模糊查询，传统的Hash不是一个“cool”的Hash，需要进行改进。
CoolHash改进后的Hash算法是一个完整的key树结构，我们知道传统Hash的key和key之间没有关系，互相独立，但是在CoolHash里，key可以表示为“user.001.name”的用“.”分开的树层次结构，如“user.001.age”和“user.001.name”都属于“user.001.*”分支，既可独立获取，也可以从父节点查询，还可以“user.*.name”方式只查询所有子节点。
提出key指针的概念：CoolHash的key可以是一个指针，指向其他树的key，这样能将两棵key树连起来，这样的设计能避免大量join操作，如果两棵key树没有直接关系，需要动态join将会非常耗时，但有了key指针可以很好的描述数
