|
知识路径: > 数据库技术 > 数据库技术基础 > 数据库模型 > 典型数据库:RDB(关系数据库)、OODB(面向对象数据库)、ORDB(对象关系数据库)、XML数据库、NoSQL(非关系数据库) > 非关系型数据库NoSQL > 相关理论基础 > 存储分布 >
|
相关知识点:3个
|
|
|
|
LSM-Tree(Log Structured Merge Trees,日志结构合并树)与前面介绍的存储结构有所不同,前面的存储结构在描述如何序列化逻辑数据结构,而LSM-Tree描述的则是为了满足高效、高性能、安全地读写的要求,如何有效地利用内存和磁盘存储。LSM-Tree的观点是由Patrick O'Neil在1996年率先提出的。LSM-Tree算法思想主要用于解决日志记录索引的问题,这种应用的特点是数据量大、写速率高(2000条/秒),又要建立有效的索引来查找日志中的特定条目。Patrick O'Neil的做法是,在内存里维护一个相同的B树,当内存中的B树达到阈值时,批量进行滚动合并。
|
|
|
而LSM-Tree的典型例子就是Google的Bigtable。下面将结合Bigtable具体解释LSM-Tree的工作原理。
|
|
|
当初Google设计Bigtable的原因有两个,一是Google需要存储的数据种类繁多,二是海量的服务请求。Google的需求是:数据存储可靠性、高速数据检索与读取、存储海量的记录、可以保持记录的多个版本。Bigtable中的合并/转储引擎结构图如下图所示。
|
|
|
|
|
用户的操作首先写入到MemTable中,当内存中的MemTable达到一定的大小,需要将MemTable转储到持久化存储中生成SSTable文件。这里需要注意,除了最早写入的SSTable存放了最终结果以外,其他的SSTable和MemTable存放的都是用户的更新操作,比如对指定行的某个列加一操作,删除某一行等。每次读取或者扫描操作都需要对所有的SSTable及MemTable按照时间从老到新进行一次多路归并,从而获取最终结果。
|
|
|
如果要确保数据不能丢失,为了应对服务器遇到不可抵抗外力因素造成宕机的情况,LSM有两次持久化过程:一次是log,以append形式对所有的update操作先进行日志记录,一旦出现意外情况,即可以恢复log中的内容到MemTable;第二次是swap,在MemTable达到阈值的时候直接转储到磁盘上形成新的SSTable。
|
|
|