Clickhouse系列-番外-LSM算法

在本系列的第三章中介绍了clickhouse通过block和lsm来减少磁盘读取的数据量。严谨的逻辑应该时clickhouse通过lsm算法来实现数据预排序,从而减少了磁盘读取的数据量,本章番外主要为读者介绍什么是LSM算法,对LSM算法已经有了解的读者可以跳过本章。

LSM算法最早出现在1991年的ACM期刊上,之后其思想在各大大数据存储系统中被广泛使用,例如LevelDB,HBase,Cassandra……LSM算法由于适应的场景不同,存在很多的变体,clickhouse也使用lsm算来实现其预排序的功能,本文将着重介绍clickhouse中的使用,同时也会适当涉及一些其他系统的使用用以让读者体会架构设计的随心所欲。

我们都知道,用户在调用insert向clickhouse插入数据时,数据不一定是按已经按照排序键排序好的数据,大概率是乱序数据。那么这种乱序的请求如何做到写入磁盘时变得有序呢?这个就是LSM算法实现的。

LSM算法的几个核心步骤:

  • 在于数据写入存储系统前首先记录日志,防止系统崩溃
  • 记录完日志后在内存中以供使用,当内存达到极限后写入磁盘,记录合并次数Level为0(L=0)。已经写入磁盘的文件不可变。
  • 每过一段时间将磁盘上L和L+1的文件合并

我们用一个示例来展示下整个过程

T=0时刻,数据库为空。

T=1时刻,clickhouse收到一条500条insert的插入请求,这500条数据时乱序的。此时,clickhouse开始插入操作。首先将500条插入请求一次性写入日志。接着在内存中进行排序,排序完成后将有序的结果写入磁盘,此时L=0;

T=2时刻,clickhouse收到一条800条insert的插入请求,这800条数据时乱序的。此时,clickhouse开始插入操作。首先将800条插入请求一次性写入日志。接着在内存中进行排序,排序完成后将有序的结果写入磁盘,此时L=0;

T=3时刻,clickhouse开始合并,此时此刻,磁盘上存在两个L=0的文件。这两个文件每个文件内部有序,但可能存在重合。(例如第一批500条的范围是300-400,第二批800条数据的范围是350-700)。因此需要合并。clickhouse在后台完成合并后,产生了一个新的L=1的文件。将两个L=0的文件标记为删除。

T=4时刻,clickhouse开始清理,将两个被标记为删除的文件真正地物理删除。

T=5时刻,clickhouse收到一条100条insert的插入请求,这100条数据时乱序的。此时,clickhouse开始插入操作。首先将100条插入请求一次性写入日志。接着在内存中进行排序,排序完成后将有序的结果写入磁盘,此时L=0;

T=6时刻,clickhouse开始合并,此时此刻,磁盘上存在1个L=0的文件和1个L=1的文件。这两个文件每个文件内部有序,但不存在重合。(例如L0文件的范围是100-200,L1文件的范围是300-700)。因此不需要合并。clickhouse在后台将L=0的文件升级成L=1,此时数据库内存在两个L=1的互不重合的文件。

……

以上就是LSM算法在clickhouse上的应用,我们总结一下,clickhouse使用LSM算法将乱序的数据在内存中排序为有序的数据,然后写入磁盘保存,并且定期合并有重合的磁盘文件。

不难发现,上述所有的过程对于磁盘的来说都是顺序写,因此这个也是LSM算法的一个特点——可以将大量的随机写入转换为顺序写入从而减少磁盘IO时间。leveldb就借助了lsm的这个特性。当然,clickhouse并没有使用到这个特性。下面会将简单介绍下leveldb是如何使用LSM的。

clickhouse借助LSM实现了预排序的功能,提高了磁盘的利用率,但也同时带来了一些牺牲。再次强调,没有完美的架构,当架构解决一个问题的同时,一定会带来一个全新的问题。

对于clickhouse也一样,读者们已经知道了,clickhouse会在多次insert请求时创建独立的数据文件。虽然clickhouse会在合适时间进行合并,但如果查询发生在合并前,就有可能数据分布在两个数据文件内。此时clickhouse默认会返回两个列表,这两个列表内部有序,但相互之间却会有重合。这就给用户使用带来了不便,下图展示了这种情况。

可以看出,此时clickhouse未合并时查询结果分成了4个独立的结果,每个结果内部有序,但相互之间存在重合,也就说对于这种情况需要用户自行合并。我们等待其合并后再次查询,结果如下:

clickhouse合并后就能解决该问题。

LevelDB的用法

leveldb是一个允许修改的数据库,因此其对于LSM的使用和clickhouse类似,主要的不同在于写入日志后的操作不同。

clickhouse在记录日志后,会直接在内存中进行排序,从而写入磁盘。此时如果clickhouse又接到一条写入情况,会重新开启一个新的进程。

而leveldb在记录日志后,会将数据首先缓存在内存中,等待后续操作继续操作这块内存,直到这块内存被填满,才会一次性将数据写入磁盘。

这个差异主要时两个数据库面向的场景不同,clickhouse主要面向读多写少的分析场景,强调大批量一次性写入增加吞吐量。而leveldb主要面向写多读少的业务场景,强调低延时。

吞吐量和延时一向是互相对立的两个指标,不同系统都在这两个指标之间存在取舍。后续有机会我也会写一篇关于这两个指标之间的相爱相杀,以及知名开源软件在这两个指标之间的思考。

感想

扯回来,正因为面向的场景不同,clickhouse和leveldb对LSM的使用存在着不同。这也给了我们一个启发,作为架构师,我们要做到运用之妙存乎一心。要能够了解我们正在设计的业务的需求是什么,然后进行符合需求的修改。而不是无脑地认为LSM一定是用在写多读少的场景。

做到这一点会有点难,但幸好我们可以站在前人肩膀上,多体会一下前人设计的精妙绝伦的架构。有了这样的经验和思考,我们在遇到相同问题的时候就能做到更深的思考。

这也是我写这个系列的原因,clickhouse真的是工程师设计的典范之作,整个clickhouse没有发明新的科学理论,但却让我们看到了借助已有的理论也能将性能在某一方面发挥到极致,这种追求极致的工程师精神让我深深着迷,我觉得我需要将这种精妙的设计思想的传递给大家。希望有朝一日,我们中国的工程师也能将极致的产品带给世界。因为有你,因为有我,许许多多平凡而伟大的工程师的共同努力,这一天一定能够到来。向clickhouse的研发团队致敬。

10,535条评论

  1. Hello there, I discovered your site by way of Google whilst
    looking for a related subject, your website got here up, it
    appears good. I’ve bookmarked it in my google bookmarks.

    Hi there, simply was aware of your blog through Google, and found that it’s really informative.
    I am gonna watch out for brussels. I’ll be grateful when you continue this
    in future. A lot of folks will be benefited from your
    writing. Cheers!

  2. Superb site you have here but I was curious about if you knew of any forums that cover the same topics talked about in this article?
    I’d really like to be a part of group where I can get comments from other knowledgeable individuals that share
    the same interest. If you have any recommendations, please let me know.
    Many thanks!

  3. Pingback: meritroyalbet
  4. Pingback: elexusbet
  5. Pingback: meritking
  6. Pingback: madridbet
  7. Pingback: eurocasino
  8. Pingback: meritking
  9. Pingback: eurocasino
  10. Pingback: elexusbet
  11. Pingback: trcasino
  12. Pingback: trcasino
  13. Pingback: tombala siteleri
  14. Pingback: tombala siteleri
  15. Pingback: tombala siteleri
  16. Pingback: meritroyalbet
  17. Pingback: meritroyalbet
  18. Pingback: meritroyalbet
  19. Hey, I think your site might be having browser compatibility issues.
    When I look at your blog site in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping.

    I just wanted to give you a quick heads up! Other then that,
    fantastic blog!

  20. Hi! I could have sworn I’ve been to this site before but after browsing through some of the post I realized it’s new to me.
    Nonetheless, I’m definitely delighted I found it and I’ll be bookmarking and checking back frequently!

  21. Just want to say your article is as astonishing.

    The clearness on your post is simply cool and that i could suppose you’re a professional on this subject.
    Fine with your permission let me to snatch your
    RSS feed to keep up to date with impending post. Thank you 1,000,000 and please continue the enjoyable work.

  22. Magnificent goods from you, man. I’ve understand your stuff
    previous to and you are just too excellent.

    I really like what you’ve acquired here, certainly like what you are stating and the way in which you say it.
    You make it enjoyable and you still care for to keep it smart.
    I cant wait to read much more from you. This is really a tremendous site.

  23. Check out this site that teaches you 1how to get diamonds in cooking fever for free

    u3iauds11
    Cooking Fever is more fun when you have as many diamonds as you want.If you love phone games like this you need to check out this website

  24. We stumbled over here from a different page and thought I might
    check things out. I like what I see so now i am following you.
    Look forward to exploring your web page yet again.

  25. Good day! I could have sworn I’ve visited this blog
    before but after browsing through a few of the articles I realized it’s new to me.
    Anyways, I’m certainly delighted I found it and I’ll be bookmarking it and checking
    back regularly!

  26. Free spins are a form of prod inured to close to online casinos to nurture their products. They’re principally aimed at encouraging bettors to chronicle with casinos and exam the experimental games.

    Some types embrace unfettered weave welcome bonus, no-deposit self-governing spins, wager-free spins, deposit without charge spins, etc.

    Casinos with bountiful spins are lovely customary, and they are mostly fond of with unencumbered spins bonus codes. These codes are meant in the direction of the bettors – which are used to signup or cash-box on casinos with free of charge spins.

    slots of vegas bonus

    It’s necessary to have in the offing these casino unfastened bonus codes as they’ll be required in advance registration, even despite the fact that the spins are free. You can smoke the let off spins to play restrictive games, and you can succeed in verified money.

    Here, we’ve compiled some of the first online casino unfasten spins that players can have to succeed in legal money.

  27. Released spins are a envision of prod used close to online casinos to present their products. They’re first and foremost aimed at encouraging bettors to chronicle with casinos and test the new games.

    Some types include at will pivot welcome bonus, no-deposit set free spins, wager-free spins, advance payment free spins, etc.

    Casinos with free spins are appealing popular, and they are mostly fond of with cost-free spins compensation codes. These codes are meant in compensation the bettors – which are used to signup or tally on casinos with free of charge spins.

    free coins old vegas slots

    It’s necessary to have in the offing these casino free largesse codes as they’ll be required in advance registration, even despite the fact that the spins are free. You can spurn the free spins to play limited games, and you can succeed in verified money.

    Here, we’ve compiled some of the a-one online casino on the house spins that players can get to success authentic money.

  28. Loose spins are a envision of spur used before online casinos to present their products. They’re fundamentally aimed at encouraging bettors to register with casinos and test the new games.

    Some types count at will weave welcome hand-out, no-deposit set free spins, wager-free spins, lay gratis spins, etc.

    Casinos with bountiful spins are appealing renowned, and they are mostly attached with unencumbered spins compensation codes. These codes are meant repayment for the bettors – which are used to signup or register on casinos with unstinting spins.

    play igt slots online free

    It’s necessary to have in the offing these casino free reward codes as they’ll be required in advance registration, monotonous all the same the spins are free. You can spurn the free spins to play the field pretend restricted games, and you can gain bona fide money.

    Here, we’ve compiled some of the first online casino on the house spins that players can get to success authentic money.

  29. Out spins are a envision of impetus acclimatized before online casinos to advance their products. They’re principally aimed at encouraging bettors to write with casinos and try out the brand-new games.

    Some types include at will invent acceptable gratuity, no-deposit set free spins, wager-free spins, deposit without charge spins, etc.

    Casinos with free spins are lovely popular, and they are mostly partial to with cost-free spins reward codes. These codes are meant repayment for the bettors – which are used to signup or register on casinos with unstinting spins.

    cheat engine chrome goldfish slots

    It’s necessary to oblige these casino unfastened reward codes as they’ll be required in advance registration, methodical though the spins are free. You can use the unsolicited spins to play the field pretend restrictive games, and you can win valid money.

    Here, we’ve compiled some of the first online casino free spins that players can have to success authentic money.

  30. I am really loving the theme/design of your blog.
    Do you ever run into any internet browser compatibility
    issues? A couple of my blog audience have complained
    about my blog not working correctly in Explorer but looks great in Firefox.
    Do you have any solutions to help fix this issue?

  31. Out spins are a figure of incentive acclimatized before online casinos to present their products. They’re first and foremost aimed at encouraging bettors to register with casinos and exam the contemporary games.

    Some types group self-governed invent acceptable gratuity, no-deposit free spins, wager-free spins, lay liberal spins, etc.

    Casinos with free spins are fetching renowned, and they are mostly fond of with free spins bonus codes. These codes are meant repayment for the bettors – which are hand-me-down to signup or cash-box on casinos with free of charge spins.

    raging bull slots no deposit code

    It’s vital to contain these casino untenanted reward codes as they’ll be required more willingly than registration, even all the same the spins are free. You can expend the unsolicited spins to play restricted games, and you can succeed in verified money.

    Here, we’ve compiled some of the best online casino on the house spins that players can get to win legal money.

  32. Loose spins are a figure of spur used close to online casinos to nurture their products. They’re fundamentally aimed at encouraging bettors to chronicle with casinos and try out the contemporary games.

    Some types count unfettered invent acceptable bonus, no-deposit unconditional spins, wager-free spins, advance payment liberal spins, etc.

    Casinos with bountiful spins are fetching fashionable, and they are mostly connected with at liberty spins bonus codes. These codes are meant for the bettors – which are familiar to signup or cash-box on casinos with free spins.

    cops and robbers pub slots free

    It’s certain to have in the offing these casino rid reward codes as they’ll be required more willingly than registration, methodical while the spins are free. You can smoke the free spins to play restricted games, and you can conquer verified money.

    Here, we’ve compiled some of the best online casino rid spins that players can make to success real money.

  33. Released spins are a envision of spur used close to online casinos to nurture their products. They’re first and foremost aimed at encouraging bettors to write with casinos and evaluation the brand-new games.

    Some types group self-governed pivot meet gratuity, no-deposit free spins, wager-free spins, deposit without charge spins, etc.

    Casinos with unattached spins are lovely customary, and they are mostly connected with free spins perk codes. These codes are meant in compensation the bettors – which are used to signup or cash-box on casinos with unshackle spins.

    how old do you have to be to play slots in las vegas

    It’s necessary to have these casino rid largesse codes as they’ll be required to come registration, methodical though the spins are free. You can use the unsolicited spins to compete with narrow games, and you can win valid money.

    Here, we’ve compiled some of the a-one online casino free spins that players can become successful to win legal money.

  34. Out spins are a envision of incentive acclimatized via online casinos to advance their products. They’re fundamentally aimed at encouraging bettors to chronicle with casinos and test the contemporary games.

    Some types count unfettered weave gratifying bonus, no-deposit unconditional spins, wager-free spins, deposit gratis spins, etc.

    Casinos with free spins are pretty popular, and they are mostly partial to with at liberty spins compensation codes. These codes are meant in the direction of the bettors – which are toughened to signup or register on casinos with unshackle spins.

    caesar slots bonus collector

    It’s urgent to have these casino rid bonus codes as they’ll be required more willingly than registration, even despite the fact that the spins are free. You can expend the let off spins to play the field pretend restricted games, and you can win verified money.

    Here, we’ve compiled some of the best online casino rid spins that players can become successful to carry off real money.

  35. Released spins are a form of prod acclimatized via online casinos to nurture their products. They’re first and foremost aimed at encouraging bettors to represent with casinos and try out the contemporary games.

    Some types group unfettered weave acceptable bonus, no-deposit unconditional spins, wager-free spins, lay liberal spins, etc.

    Casinos with generous spins are fetching popular, and they are mostly fond of with free spins reward codes. These codes are meant in the direction of the bettors – which are familiar to signup or tally on casinos with unstinting spins.

    inferno slots biz

    It’s vital to contain these casino unfastened bonus codes as they’ll be required in advance registration, monotonous despite the fact that the spins are free. You can expend the accessible spins to play the field pretend restrictive games, and you can conquer real money.

    Here, we’ve compiled some of the first online casino unfasten spins that players can get to win real money.

  36. Loose spins are a form of impetus acclimatized by online casinos to promote their products. They’re primarily aimed at encouraging bettors to register with casinos and try out the experimental games.

    Some types embrace free pivot meet gratuity, no-deposit set free spins, wager-free spins, deposit gratis spins, etc.

    Casinos with unattached spins are pretty customary, and they are mostly fond of with cost-free spins perk codes. These codes are meant in the direction of the bettors – which are hand-me-down to signup or tally on casinos with unstinting spins.

    play inferno slots com

    It’s urgent to have in the offing these casino free reward codes as they’ll be required more willingly than registration, monotonous though the spins are free. You can use the unsolicited spins to play the field pretend narrow games, and you can gain real money.

    Here, we’ve compiled some of the a-one online casino on the house spins that players can make to success legitimate money.