当前位置:网站首页>浅谈skiplist在LevelDB的应用
浅谈skiplist在LevelDB的应用
2022-04-23 14:11:00 【Mrpre】
什么是跳表
具体参考 http://zhangtielei.com/posts/blog-redis-skiplist.html
Leveldb 为什么用跳表
首先 skiplist作为memtable
的数据结构,如果光为了存储kv,那么任何数据结构都能被使用,像Redis的dict。但是 LevelDB 有个特性,就是put 2个相同的key,那么2份相同的key会同时存在于 memtable
中,而不是通常人们理解的使用新的value把老的value替换掉。这就意味着,get时需要保证取到的是新的value而不是旧的。 此时,简单tree是无法保证有序的。
- 注意: LevelDB 的delete 也不会删除memtable中kv的,而是和put一样,插入个节点,标记为是"delete"。
跳表如何保证有序
首先,简单跳表当然只能处理key为数字的情况,但是用户put的key,必然是随机二进制,例如 “mykey”。"mykey"就不能作为跳表的key了吗,并不然。因为你可以设置跳表的“比较函数”用来代替数字的比较。
例如,Level中规定:
mykey > mykeyb
mykey < myke
mykey == mykey
其次考虑如何保证有序。LevelDB中,为每个用户操作的key都赋予了一个seq,是全局递增的。 简单来描述,存入 跳表中的 key,是 “key+seq”,有了seq,那么“比较函数”除了比较上述用户的key以外,还需要比较seq,用户不同时刻输入的key虽然一样,但是seq不一样,自然有了大小之分。
mykey$2 > mykey$1
int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
// Order by:
// increasing user key (according to user-supplied comparator)
// decreasing sequence number
// decreasing type (though sequence# should be enough to disambiguate)
int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
if (r == 0) {
const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
if (anum > bnum) {
r = -1;
} else if (anum < bnum) {
r = +1;
}
}
return r;
}
查找如何保证查到最新的value
假设用户put了2次"key",但是value不同,那么第二次put的"key",因为他的seq比第一次put的"key"的seq大,自然,在跳表中位置在第一次的"key"之后。假设seq 分别是1 和 2,那么跳表中存的key为 “key$1” “key$2”。
此时,用户get了这个key,这个操作的key的seq必然大于等于2,假设是100(例如中间put了其他的key,倒是seq增加了)。
LevelDB,此时在跳表中会查询"key$100"。由于 查询的key是 “key$100”,正常的跳表必然是找不到的结果的,因为只有跳表中只有"key$1" 和 “key$2”。
我们看下面查询函数如何处理的。
iter.Seek(memkey.data())
执行查找,只有当 跳表中一个kv都不存在时,iter.Valid()
才是NULL,其他情况,iter.Valid()
都成立。 iter.key()
保存了前一个比待搜索的"key$100"小的跳表节点。这就出现了comparator_.comparator.user_comparator()->Compare
这一幕。
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
Slice memkey = key.memtable_key();
Table::Iterator iter(&table_);
iter.Seek(memkey.data());
if (iter.Valid()) {
// entry format is:
// klength varint32
// userkey char[klength]
// tag uint64
// vlength varint32
// value char[vlength]
// Check that it belongs to same user key. We do not check the
// sequence number since the Seek() call above should have skipped
// all entries with overly large sequence numbers.
const char* entry = iter.key();
uint32_t key_length;
const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
if (comparator_.comparator.user_comparator()->Compare(
Slice(key_ptr, key_length - 8),
key.user_key()) == 0) {
// Correct user key
const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
switch (static_cast<ValueType>(tag & 0xff)) {
case kTypeValue: {
Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
value->assign(v.data(), v.size());
return true;
}
case kTypeDeletion:
*s = Status::NotFound(Slice());
return true;
}
}
}
return false;
}
其实整体逻辑很简单,就是找一个大于大于当前seq的相同的"key"。搜索出来的"iter.key()",要么是xx$zz
就是要么就是key$yy
,前者,说明我们搜索的key压根不存在,因为比我们key距离最近的居然是其他的key;若是后者,说明key$yy
这个seq为yy的是最近插入/删除的key。
有没有可能 出现跳表的顺序是这样的
“key$1” > “ke$1” > “key$2” > “ke$2”,如果是这样,我们搜索"key$100"时,前一个值有可能是"ke$2",从而导致查找失败。实际当然是不可能的,"比较函数"保证了这一点。相同的"key"必然是按照seq排序的。
总结
这就是为什么我们常说LevelDB的数据是有序的。试想,如果像Redis一样,把kv存储在字典里面,那么自然没有顺序一说。这也是为什么LevelDB把删除也作为一个跳表的Node,一切操作皆顺序。
版权声明
本文为[Mrpre]所创,转载请带上原文链接,感谢
https://wonderful.blog.csdn.net/article/details/119778933
边栏推荐
猜你喜欢
Tongxin UOS uninstall php7 2.24, install php7 4.27 ; Uninstall and then install PHP 7.2.34
OpenStack命令操作
A table splitting implementation scheme of MySQL and InnoDB, MyISAM and MRG_ Introduction to MyISAM and other engine application scenarios
剑指offer刷题(1)--面向华为
处理 mkdir:无法创建目录“aaa“:只读文件系统
使用Executors类快速创建线程池
KVM learning resources
利用json-server在本地创建服务器请求
man man随记和crontab的@reboot用法
政务云迁移实践 北明数科使用HyperMotion云迁移产品为某政府单位实施上云迁移项目,15天内完成近百套主机迁移
随机推荐
krpano全景之vtour文件夹和tour
MySQL数据库讲解(九)
SED 学以致用
Quickly understand the three ways of thread implementation
VMware 15pro mounts the hard disk of the real computer in the deepin system
dp-[NOIP2000]方格取数
修改Firebase Emulators的默认侦听IP
金融行业云迁移实践 平安金融云整合HyperMotion云迁移解决方案,为金融行业客户提供迁移服务
Recyclerview advanced use (I) - simple implementation of sideslip deletion
VMware installation 64 bit XP Chinese tutorial
xx项目架构随记
redis数据库讲解二(redis高可用、持久化、性能管理)
Some experience of using dialogfragment and anti stepping pit experience (getactivity and getdialog are empty, cancelable is invalid, etc.)
时间复杂度计算举例
MYSQL一种分表实现方案及InnoDB、MyISAM、MRG_MYISAM等各种引擎应用场景介绍
json date时间日期格式化
Returns the subscript after array sorting
Mysql的安装过程(已经安装成功的步骤说明)
Redis数据库讲解(一)
MySQL同步Could not find first log file name in binary log index file错误