LSM

LSM-Tree - LevelDb之LRU缓存引言LRU缓存在各种开源组件中都有应用的场景，经常用于做冷热数据和淘汰策略，应用LRU次要有三点。 第一点是实现非常简单。第二点是代码量自身也不错。最初波及数据结构十分经典。LevelDB对于LRU缓存实现算是比拟经典的案例，这一节来介绍它是如何应用LRU实现缓存的。 LeetCode 中有一道相应LRU缓存算法的题目，感兴趣能够做一做：lru-cache实践依据wiki的LRU缓存构造介绍，能够理解到缓存的根本淘汰策略过程，比方上面这张图的节点淘汰过程： 读取的程序为 A B C D E D F，缓存大小为 4，括号内的数字示意排序，数字越小越靠后，示意 Least recently. 依据箭头的读取程序，读取到E的时候，发现缓存曾经满了，这时会淘汰最早的一个A(0)。 接下来持续读取并且更新排序，倒数第二次中发现D是最大的，而B是最小的，当读取F退出缓存之后，发现缓存曾经是满的，此时发现绝对于A之后插入的数值B拜访次数最小，于是进行淘汰并且替换。 依据起码实用准则LRU 的实现须要两个数据结构： HashTable（哈希表）: 用于实现O(1)的查找。List: 存储 Least recently 排序，用于旧数据的淘汰。LevelDB实现这里间接看LevelDB是如何利用这个数据结构的。 LevelDB的LRUCache设计有4个数据结构，是顺次递进的关系，别离是： LRUHandle（LRU节点，也就是LRUNode）HandleTable（哈希表）LRUCache（要害，缓存接口标准和实现）ShardedLRUCache（用于进步并发效率）整个LevelDB 的数据结构组成如下： 上面是相干接口定义： // 插入一个键值对（key，value）到缓存（cache）中，// 并从缓存总容量中减去该键值对所占额度（charge） // // 返回指向该键值对的句柄（handle），调用者在用完句柄后，// 须要调用 this->Release(handle) 进行开释//// 在键值对不再被应用时，键值对会被传入的 deleter 参数// 开释virtual Handle* Insert(const Slice& key, void* value, size_t charge, void (*deleter)(const Slice& key, void* value)) = 0;// 如果缓存中没有相应键（key），则返回 nullptr//// 否则返回指向对应键值对的句柄（Handle）。调用者用完句柄后，// 要记得调用 this->Release(handle) 进行开释virtual Handle* Lookup(const Slice& key) = 0;// 开释 Insert/Lookup 函数返回的句柄// 要求：该句柄没有被开释过，即不能屡次开释// 要求：该句柄必须是同一个实例返回的virtual void Release(Handle* handle) = 0;// 获取句柄中的值，类型为 void*（示意任意用户自定义类型）// 要求：该句柄没有被开释// 要求：该句柄必须由同一实例所返回virtual void* Value(Handle* handle) = 0;// 如果缓存中蕴含给定键所指向的条目，则删除之。// 须要留神的是，只有在所有持有该条目句柄都开释时，该条目所占空间才会真正被开释virtual void Erase(const Slice& key) = 0;// 返回一个自增的数值 id。当一个缓存实例由多个客户端共享时，// 为了防止多个客户端的键抵触，每个客户端可能想获取一个独有// 的 id，并将其作为键的前缀。相似于给每个客户端一个独自的命名空间。virtual uint64_t NewId() = 0;// 驱赶全副没有被应用的数据条目// 内存吃紧型的利用可能想利用此接口定期开释内存。// 基类中的 Prune 默认实现为空，但强烈建议所有子类自行实现。// 未来的版本可能会减少一个默认实现。virtual void Prune() {}// 返回以后缓存中所有数据条目所占容量总和的一个预估virtual size_t TotalCharge() const = 0;依据LevelDB接口定义，能够整顿出缓存解决了如下的需要： ...

本文系北京大学智能学院在读博士生胡琳所著，目前于 OceanBase 存储组实习，本篇也是 OceanBase 学术系列稿件第二篇。 「胡琳：北京大学智能学院在读博士生，博士期间在北京大学数据管理组从事GPU减速图算法的钻研，在图算法减速畛域获得了肯定的成绩，发表在SIGMOD等出名会议上，将持续在图计算畛域致力摸索。」 OceanBase 等以 LSM tree 为存储架构的数据库的 compaction 是一个比拟耗时的操作，近年来 GPU 越来越多地被用在高性能计算畛域。本文次要探讨 GPU 对基于 LSM tree 的数据库的性能晋升。 心愿浏览完本文，你能够有所播种，有什么疑难也能够在底部留言探讨，与作者一起摸索。 GPU 是一种新硬件，相比拟于 CPU，有较高的读写带宽和更强的并行能力，在很多畛域都有十分好的利用。明天咱们以 LSM-tree 上的 compaction 和 scan 为例，介绍 GPU 如何在减速数据库的操作中发挥作用。 GPU 的倒退历程 图1：GPU 的倒退 GPU 倒退之初，是作为集成单元与其余硬件聚合在一起，也就是咱们所熟知的显卡。1999 年，NVIDIA 公布 Geforce256，正式提出 GPU 概念；2006 年，NVIDIA 公布 GeForce8800，公布 CUDA，一种前面失去宽泛应用的 GPU 编程语言；2011 年，NVIDIA 公布 Tesla 系列，造成计算产品线，GPU 开始更多地利用于科学计算畛域。2011 年至今，GPU 疾速倒退，次要被 NVIDIA 和 AMD 所垄断，一些国产公司也开始研发一些替代品。 当初，GPU 在 CUDA 语言的根底上，提供了对于多种语言如 C++、python 的反对，并且有很多现成的算法库用来进行深度学习，矩阵乘法，通用计算等等。这些很大水平上升高了 GPU 编程的门槛，使得 GPU 的进一步广泛应用成为了可能。 ...