Tair是Key/Value结构数据存储系统,由淘宝网自主开发并开源。
Tair有四种引擎:mdb, rdb, kdb和ldb。分别基于四种开源的key/value数据库:memcached, Redis, Kyoto Cabinet和leveldb。
Tair可以让你更方便地使用这些KV数据库。
比如Redis没有提供sharding操作,如果有多个Redis Server,你需要自己写代码实现sharding,Tair帮你封装了这些。
redis和memecahche平时用的不少,这里一起学习一下Kyoto Cabinet和leveldb。
KC是一个数据库管理的 lib。数据库是一个简单的包含记录的数据文件,每个记录是一个键值对(key/value),key和value都是变长的字节序列。key和value既可以是二进制的,也可以是文本字符串。数据库中的key必须唯一。数据库既没有表的概念,也不存在数据类型。所有的记录被组织为hash表或B+树。
在数据库中,可以储存key-value记录,也可以根据key来获取和删除记录。还可以遍历访问所有的key。这些方法类似于UNIX标准中的DBM库(及后来的NDBM和GDBM)。因为KC的高性能,可以作为DBM的替代品。
Hash 数据库 的每个操作的时间复杂度是 O(1),因此理论上,性能是常量而与数据库的规模无关。在实践中,性能由内存或存储设备的速度决定。如果数据库的大小小于内存大小,性能表现为内存的速度,比STL中的std::map要快。当然数据库大小可以大于内存大小,最大上限是8EB(1024×1024×1024GB)。即使在这样的情况下,每个操作也只需要一两个存储设备的seek操作。
B+ tree 数据库的每个操作的时间复杂度是 O(log N)。因此理论上,性能是数据库规模的对数。尽管B+ tree 数据库的随机访问性能要慢于 hash数据库,但B+ tree数据库支持对 key 顺序的连续访问,这可以实现对字符串的前向匹配查找和整数的范围查找。连续访问的性能远快于随机访问。
API是基于面向对象设计的,hash数据库和B+ tree数据库都有从同一个超类继承而来的同样的方法。除了他们,还有7种数据库也继承了同样的超类。
prototype hash 数据库采用标准容器 std::unordered_map 实现
prototype tree 数据库采用标准容器 std::map 实现
stash 数据库是采用naive hash map的原始实现来节省内存
cache hash 数据库是采用 LRU删除算法的双向链接 hash map 原始实现
cache tree 数据库是基于cache hash 数据库并提供B+ tree的机制
directory hash 数据库是采用文件系统的目录机制实现,每个记录存储为一个目录下的文件directory tree 数据库基于directory hash数据库并提供B+ tree的机制。
所有的数据库都有相关的事物(transaction)和游标(cursor)的实用方法。软件也包含了命令行接口的程序。
KC的运行速度非常快。例如,保存一百万记录到hash数据库中只需要0.9秒,保存到B+ tree数据库只需要1.1秒。而且数据库本身还非常小。例如,hash数据库的每个记录头只有16字节,B+ tree数据库是4字节。更进一步,KC的伸缩性非常大,数据库大小可以增长到8EB(9.22e18 bytes)。
KC是C++语言编写的,并提供C++、C、Java、Python、Ruby、Perl 和 Lua 的API。
LevelDB的数据是存储在磁盘上的,采用LSM-Tree的结构实现。LSM-Tree将磁盘的随机写转化为顺序写,从而大大提高了写速度。为了做到这一点LSM-Tree的思路是将索引树结构拆成一大一小两颗树,较小的一个常驻内存,较大的一个持久化到磁盘,他们共同维护一个有序的key空间。写入操作会首先操作内存中的树,随着内存中树的不断变大,会触发与磁盘中树的归并操作,而归并操作本身仅有顺序写.
key和value都是任意长度的字节数组;entry(即一条K-V记录)默认是按照key的字典顺序存储的,当然开发者也可以重载这个排序函数;提供的基本操作接口:Put()、Delete()、Get()、Batch();支持批量操作以原子操作进行;可以创建数据全景的snapshot(快照),并允许在快照中查找数据;可以通过前向(或后向)迭代器遍历数据(迭代器会隐含的创建一个snapshot);自动使用Snappy压缩数据;可移植
官网代码github.com/google/leveldb
Tair中的每个数据都包含版本号,版本号在每次更新后都会递增。这个特性有助于防止由于数据的并发更新导致的问题。
比如,系统有一个value为“a,b,c”,A和B同时get到这个value。A执行操作,在后面添加一个d,value为 “a,b,c,d”。B执行操作添加一个e,value为”a,b,c,e”。如果不加控制,无论A和B谁先更新成功,它的更新都会被后到的更新覆盖。
Tair无法解决这个问题,但是引入了version机制避免这样的问题。还是拿刚才的例子,A和B取到数据,假设版本号为10,A先更新,更新成功 后,value为”a,b,c,d”,与此同时,版本号会变为11。当B更新时,由于其基于的版本号是10,服务器会拒绝更新,从而避免A的更新被覆盖。 B可以选择get新版本的value,然后在其基础上修改,也可以选择强行更新。
Tair从服务器端支持原子的计数器操作,这使得Tair成为一个简单易用的分布式计数器。
Tair有以下优点:
统一的API。无论底层使用何种引擎,上层的API是一样的。
Tair将集群操作封装起来,解放了开发者。淘宝内部在使用Tair时,一般都是双机房双集群容错,利用invalid server保证两个集群间的一致性,这些对于开发者都是透明的。
Tair将value视为一个item数组,可以对value中的部分item进行操作。比如有个key的value为[1,2,3,4,5],我们可以只获取前两个item,返回[1,2],也可以删除第一个item,还支持将数据删除,并返回被删除的数据,通过这个接口可以实现一个原子的分布式 FIFO的队列。