LSM树存储模型，lsm树模型

LSM树存储模型，lsm树模型

----《大规模分布式存储系统：原理解析与架构实战》读书笔记

之前研究了Bitcask存储模型，今天来看看LSM存储模型，两者虽然同属于基于键值的日志型存储模型。但是Bitcask使用哈希表建立索引，而LSM使用跳跃表建立索引。这一差别导致了两个存储系统的构造出现明显的分化。为此，我还先去捣腾了一番跳跃表的实现.今天算是进入了正题。

LSM的结构

LSM的基本思想是将修改的数据保存在内存，达到一定数量后在将修改的数据批量写入磁盘，在写入的过程中与之前已经存在的数据做合并。同B树存储模型一样，LSM存储模型也支持增、删、读、改以及顺序扫描操作。LSM模型利用批量写入解决了随机写入的问题，虽然牺牲了部分读的性能，但是大大提高了写的性能。

MemTable

LSM本身由MemTable,Immutable MemTable,SSTable等多个部分组成，其中MemTable在内存，用于记录最近修改的数据，一般用跳跃表来组织。当MemTable达到一定大小后，将其冻结起来变成Immutable MemTable，然后开辟一个新的MemTable用来记录新的记录。而Immutable MemTable则等待转存到磁盘。

Immutable MemTable

所谓Immutable MemTable，即是只能读不能写的内存表。内存部分已经有了MemTable，为什么还要使用Immutable MemTable？个人认为其原因是为了不阻塞写操作。因为转存的过程中必然要保证内存表的记录不变，否则如果新插入的记录夹在两条已经转存到磁盘的记录中间，处理上会很麻烦，转存期间势必要锁住全表，这样一来就会阻塞写操作。所以不如将原有的MemTable变成只读Immutable MemTable,在开辟一个新的MemTable用于写入，即简单，又不影响写操作。

SSTable

SSTable是本意是指有序的键值对集合( a set of sorted key-value pairs )。是一个简单有用的集合，正如它的名字一样，它存储的就是一系列的键值对。当文件较大的时候，还可以为其建立一个键-值的位置的索引，指明每个键在SSTable文件中的偏移距离。这样可以加速在SSTable中的查询。(当然这一点是可选的，同时让我想去了Bitcask模型中hint文件，通过记录 键-值的位置 ,来加速索引构建)

使用MemTable和SSTable这两个组件，可以构建一个最简单的LSM存储模型。这个模型与Bitcask模型相比，不存在启动时间长的问题，但是这个模型的读性能非常的差，因为一但在MemTable找不到相应的键，则需要在根据SSTable文件生成的时间，从最近到较早在SSTable中寻找，如果都不存在的话，则会遍历完所有的SSTable文件。
如果SSTable文件个数很多或者没有建立SSTable的文件内索引的话，读性能则会大大下降。

除了在对SSTable内部建立索引外，还可以使用Bloom Fileter,提高Key不在SSTable的判定速度。同样，定期合并旧的SSTable文件，在减少存储的空间的同时，也能提高读取的速度。下面这幅图很好的描述了在LSM的大部分结构和操作

LevelDB如何优化读性能

Leveldb是一个轻量级的，快速的以存储为目的的key-value存储引擎。其使用的正是LSM存储模型。我们可以看看LevelDB是如何来优化读性能的。在LevelDB中，存在一种元信息文件MANIFEST，用于记录leveldb的元信息，比如DB使用的Comparator名，以及各SSTable文件的管理信息：如Level层数、文件名、最小key和最大key等等。相比而言，元信息文件而SSTable文件的数目成正比，一般来说不会太多，是可以载入内存的，因此Level可以通过查询元信息，从而判断哪些文件中存在我们需要的Key对应的记录，减少SSTable文件读取次数。此外，LevelDB的合并操作Compaction是分层次进行的，每一层都有多个SSTable文件，每次合并后除了Level0和内存的MemTable，Immutable MemTable中会有重复的键值外，LevelN(N>=1)的各层内部的SSTable文件不会再有重复的键值。同时，如果在Level N 层读到了数据，那么就不需要再往后读Level N+1,Level N+2等层的数据了.因为Level N层的数据总是比Level N+1等层的数据更“新鲜”。

实现一个简单的LSM存储模型

根据上面讲述的原理，实现了一个简单的LSM模型(https://github.com/Winnerhust/Code-of-Book/blob/master/Large-Scale-Distributed-Storage-System/lsm_tree.py)。这个模型也内存表为一个跳跃表，SSTable就是简单的有序键值对集合，没有SSTable内部使用索引,没有使用Bloom过滤器。其实能就是将我之前的Bitcask模型进行了简单的改造：

• 将原来的哈希表换成了跳跃表；
• 原来读取记录完全依赖哈希表，现在如果在跳跃表中没有的话，就去读取文件SSTable文件中的数据，根据文件编号从大到小进行，编号越大，表示数据越新；
• 去掉了加载数据的功能(LSM不需要)；

简单起见，没有完成对范围扫描的支持，不过内存表和SSTable都是有序的，因此这个也不是很难。

参考：
详解SSTable结构和LSMTree索引

---

欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏。
如果阅读本文过程中有任何问题，请联系作者，转载请注明出处！

与传统的存储设备相比，云存储不仅仅是一个硬件，而是一个网络设备、存储设备、服务器、应用软件、公用访问接口、接入网、和客户端程序等多个部分组成的复杂系统。各部分以存储设备为核心，通过应用软件来对外提供数据存储和业务访问服务。
　　云存储系统的结构模型由 4层组成。
一、存储层
　　存储层是云存储最基础的部分。存储设备可以是FC光纤通道存储设备，可以是NAS和 iSCSI等IP存储设备，也可以是 SCSI或SAS等 DAS存储设备。云存储中的存储设备往往数量庞大且分布多不同地域，彼此之间通过广域网、互联网或者 FC光纤通道网络连接在一起。
　　存储设备之上是一个统一存储设备管理系统，可以实现存储设备的逻辑虚拟化管理、多链路冗余管理，以及硬件设备的状态监控和故障维护。
二、基础管理层
　　基础管理层是云存储最核心的部分，也是云存储中最难以实现的部分。基础管理层通过集群、分布式文件系统和网格计算等技术，实现云存储中多个存储设备之间的协同工作，使多个的存储设备可以对外提供同一种服务，并提供更大更强更好的数据访问性能。
　　CDN内容分发系统、数据加密技术保证云存储中的数据不会被未授权的用户所访问，同时，通过各种数据备份和容灾技术和措施可以保证云存储中的数据不会丢失，保证云存储自身的安全和稳定。
三、应用接口层
　　应用接口层是云存储最灵活多变的部分。不同的云存储运营单位可以根据实际业务类型，开发不同的应用服务接口，提供不同的应用服务。比如视频监控应用平台、IPTV和视频点播应用平台、网络硬盘引用平台，远程数据备份应用平台等。
四、访问层
　　任何一个授权用户都可以通过标准的公用应用接口来登录云存储系统，享受云存储服务。云存储运营单位不同，云存储提供的访问类型和访问手段也不同。
希望可以帮到你！


参考资料：百度百科

 

14．[题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度{int hc,hs; if (bt==null) return (0);elseif (!bt->firstchild) return (1+height(bt->nextsibling);//子女空，查兄弟的深度else // 结点既有第一子女又有兄弟，高度取子女高度+1和兄弟子树高度的大者{hc=height(bt->firstchild)； //第一子女树高hs=height(bt->nextsibling)；//兄弟树if(hc+1>hs)return(hc+1); elsereturn (hs); }}//结束heightint height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度{if(t==null) return(0);else{int front=1,rear=1; //front,rear是队头队尾元素的指针int last=1,h=0; //last指向树中同层结点中最后一个结点，h是树的高度Q[rear]=t; //Q是以树中结点为元素的队while(front<=last){t=Q[front++]; //队头出列while(t!=null) //层次遍历{if (t->firstchild) Q[++rear]=t->firstchild; //第一子女入队t=t->nextsibling; //同层兄弟指针后移}if(front>last) //本层结束，深度加1（初始深度为0）h++;last=rear;} //last再移到指向当前层最右一个结}//while(front<=last)}//else }//Height