LSM作为一种设计思想，它把数据拆分为两个部分，一部分放在内存，一部分放在磁盘。内存中的数据检索可以使用红黑树，调表等时间复杂度比较低的结构进行检索。当数据到达一定阈值的时候则会将数据写到磁盘文件中，此时的写入的方式是顺序写，所以LSM写入性能很高。
并发读写问题
内存在写入磁盘过程中，如果有新的数据插入，则会带来并发读写的问题，所以就需要对这部分内存区域进行加锁。加锁的话又会导致写入过程阻塞，所以业界一般是当内存到达某个阈值之后，将这片区域标记为可读，然后新的数据将插入到新的内存区域，而旧的内存区域是只读的，所以可以不加锁的进行同步到磁盘的过程。
小文件问题
众所周知由于内存的容量有限，并且进行了分区，导致每次生成文件必然不会很大，这样就会造成检索效率很慢的问题。LSM是这样解决问题的：查找数据时候从多个磁盘文件中读取数据，然后进行合并，取最新的数据(Merge On Read)。由于写入的数据在内存是有序的，所以磁盘的小文件也是有序的(sstable)。这样可以保证单个文件中的检索是非常快的，但是存在一个问题：如果查找一个值的时候，在多个文件的索引有重叠的话就需要在多个sstable中查找数据(最坏的可能需要检索所有的文件)，所以需要将小文件进行合并，让索引不再有重叠，就可以解决很好的剪枝文件。这也是Hudi点查性能不好的原因，没有保证索引不重叠。
文件合并
虽然文件合并带来的好处很多，但是合并的时机非常重要，如果新增一个就去进行合并全部文件，就会造成磁盘IO一直处于一个很高的水平，这样性能反而不好。所以LSM采用的是多层合并的方法，每一层的容量是上一层的10倍。level0层是内存直接写入的文件，当写满这一层的个数上限之后，再进行合并然后存入下一层，然后当下一层写满之后再继续合并到下一层，直到合并到最大层数则不再合并。这样就只存在level0层的索引是有重合的，其他的层的索引数据都是不重合的，可以很好的进行File Skiping，并且由于这种设计，将文件合并的时机分摊到了多次，缓解了写放大的问题。
总结
LSM在数据写入方面，使用了内存分区标记解决了读写并发问题，并且使用多层合并的机制解决了写放大的问题，提供了非常好的写入性能和小文件合并的机制。
在读方面，可以先从内存读取，找不到再从level0一直往高层找，并且由于level0后的数据都是有序且不重合的，通过二分查找，能够很好的进行File Skiping，再配合布隆过滤器来快速判断元素是否存在与文件中。在最差的情况下，可能要遍历所有的文件，所以LSM适合写多读少的场景。
评论 (0)