微信号:infraexp

介绍:互联网底层基础技术相关,内容涉及疑难问题的剖析,通用系统、工具原理详解,以及一些最新的项目进展和功能介绍

Bada数据结构简介

2015-05-13 17:31 基础架构快报

简介

Bada是360基础架构团队自主研发的分布式Key-Value数据库系统,但也支持hash/list/zset(sorted set)等数据结构,具备对复杂数据结构的高效操作,并支持这些数据结构的跨机房同步等功能。

数据模型

  • hash: name key value

    支持hset,hget, hmset, hmget,hsize等相关操作

  • list: name value

    支持lpush, lpop, rpush, rpop, rsize等相关操作

  • zset: name key score

    支持zset, zscore, zrange, zrank, zsize等相关操作

使用场景

  • 在不支持hash数据结构的kv系统中,有些常常需要讲一些结构化的数据序列化后存储为一个字符串的值,比如用户的昵称、年龄、性别、积分等,这时候在需要修改其中某一项时,通常需要将所有值取出反序列化后,修改某一项的值,再序列化存储回去。这样不仅增大了开销,也不适用于一些可能并发操作的场合。而Bada的Hash结构可以使你像在关系数据库中update一个属性一样只修改某一项属性值。

  • list数据结构可以看成一个双向链表,list会记录链表的长度,可以通过push,pop操作从链表的头部或者尾部添加删除元素,这使得list既可以用作栈,也可以用作队列。

  • zset排序集合,对于集合中的每个元素给定一权重参数score,使集合中的元素能够按照score进行排序。比如一个存储全班同学成绩的Sorted Sets,其集合value可以是同学的学号,而score 就可以是其考试得分,这样在数据插入集合的时候,就已经进行了排序。

实现原理

数据分区

hash/list/zset这些复杂数据结构呈现明显的数据聚集现象,对于相同name的所有元素往往存在范围查询操作,所以Bada目前使用name进行hash分区,相同name的元素存储于同一节点。

数据存储

Bada底层采用leveldb进行数据存储,而leveldb只支持普通的kv数据结构,如何在leveldb的基础上实现上面提到的复杂数据结构呢?

hash

如下图所示,在存储hash数据结构时,我们将name和key组合成 leveldb存储的新key,这样原来的数据模型就从name + key + value转化为新的key + value,对于hset、hget等操作只需要进行一次name和key的编码和解码便可转化为leveldb的kv操作,但是如果只这样存储,当我们要获取hash数据结构的元素大小时,该怎么做呢?那么只有遍历一次了,时间复杂度为o(n),这显然很慢!所以我们进行hset操作时会额外维护一个name + size的记录,每次hset新的元素是会增加size的值,这样如需获取元素多少时便可在o(1)时间复杂度内完成。


list

对于list数据结构,在内部我们用[10 - 9223372036854775807]区间上的值来表示当前push的元素的位置,第一次push时元素位置为区间中间值,之后每次lpush,rpush时位置值分别减一和加一;如下图所示,我们维护一个元数据记录,其存储下次lpush和rpush的位置以及当前list的元素大小,数据则存储与一个name + 当前的位置值将作为key的记录中。


zset

如下图所示,zset数据结构对于单个元素的操作和获取集合大小的操作同hash类似,所以需存储两份和hash数据结构类似的数据(score作为leveldb的value存储),但zset的范围操作如zrange,以及zrank等操作需要获取根据score的值进行排过序的结果,所以需要另外存储一份以name + score + key为leveldb的key,value为空的记录,这样对于涉及到排序结果的操作便可以以这份数据为基础进行查询。


结尾

后续我们将增加set集合数据结构,欢迎大家提出宝贵意见,我们将根据您的意见不断完善相关操作。


 
基础架构快报 更多文章 PHP程序段错误分析 记一次 MongoDB driver BUG 的跟踪 PHP 死锁问题分析 web常见问题排查 PHP升级导致系统负载过高问题分析
猜您喜欢 支付宝全民免费wifi计划 安全成为最大担忧 【视频】►话费积分换现金 假链接真骗钱 DevOps Pitfalls to Avoid (Devops 经验) 【视频】醇粹测试第一期 探究Java中的克隆