学大数据必懂系列之LSM
2020-06-21 19:43:36
学大数据必懂系列之LSM-Tree
LSM树（Log-Structured-Merge-Tree）是一种专为提升磁盘写入速度而设计的数据结构。其核心思想在于将大量的磁盘随机写操作转换为批量顺序写，从而显著提高写入性能，尽管这一优化以牺牲部分读性能为代价。
一、LSM-Tree的设计思想
LSM-Tree是一种多层结构、有序数据、针对磁盘存储的数据结构，广泛应用于各种Key/Value数据库中。其设计核心在于充分利用磁盘批量顺序写的高效性，同时接受读效率的部分降低以换取写效率的大幅提升。LSM-Tree由两个或更多树状组件数据结构组成，包括驻留在内存中的C0树和驻留在磁盘中的C1至Ck树。
二、LSM-Tree的工作流程
数据写入：数据首先被写入到内存中的C0树。为了防止数据丢失，写内存的同时，数据会以完全有序的形式暂时持久化到磁盘的预写日志（WAL）中。
持久化：当C0树的大小达到一定阈值后，其全部或部分数据会被刷入磁盘中的C1树。这一过程中还涉及容错恢复、合并检查点以及旧的C0树子页的清理等。
合并操作：由于每次持久化到硬盘的操作是独立线程完成的，并生成单独的文件，因此C1树可能包含多个文件。当文件数增多时，每次查询都可能涉及大量文件的打开，导致I/O消耗增加。为了控制读放大的情况，LSM-Tree会进行小文件合并。合并操作会从左至右遍历内存中的叶子节点与磁盘中树的叶子节点进行合并，当合并的数据量达到磁盘存储页的大小时，会将合并的数据持久化到磁盘，并更新父亲节点对叶子节点的指针。
三、LSM-Tree性能的衡量因素
读放大（RA）：指过多读取请求。当数据读取的频率远远超过了数据大小时，会影响读性能。为了减轻读放大，LSM-Tree采用布隆过滤器来避免读取不包括查询键值的SSTable文件。
空间放大（SA）：指磁盘空间使用过多。当磁盘使用大于数据实际大小时，就会出现高SA。
写放大（WA）：指过度压缩相同的数据。当写入存储的字节数多于实际写入数据库的字节数时，就会出现高WA。
四、LSM-Tree在HBase中的应用
HBase是一个分布式、可扩展的大数据存储系统，它基于LSM-Tree结构进行数据存储和管理。在HBase中，LSM-Tree的应用主要体现在以下几个方面：
写入流程：
客户端在数据写入时，首先将数据写入到WAL（Write Ahead Log）中，以追加的方式写入到WAL文件的尾部。WAL保存在每个RegionServer中，用于恢复未提交到磁盘的数据。
数据一旦写入到WAL之后，会被复制到MemStore中。MemStore是LSM-Tree中的C0树的实际实现。
数据被放置到MemStore中之后，客户端接收到确认信息。
当MemStore达到阈值时，它会被转存或提交数据到HFile中。HFile表示从MemStore接收到的一小段数据，并保存在HDFS中。
合并排序操作：HBase会定期对这些HFile进行合并排序操作，使其符合标准HDFS块的配置大小，从而避免小文件问题。
综上所述，LSM-Tree通过其独特的设计思想和工作流程，在大数据存储系统中实现了高效的写入性能。尽管它牺牲了一部分读性能，但在许多应用场景中，这种权衡是值得的。特别是在需要频繁写入数据的大数据环境中，LSM-Tree的应用能够显著提升系统的整体性能。
热门标签
