tag:blogger.com,1999:blog-9149523927864751087.post5722754723900052783..comments2024-03-26T09:43:01.052-07:00Comments on Small Datum: Throttling writes: LSM vs B-TreeMark Callaghanhttp://www.blogger.com/profile/09590445221922043181noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-9149523927864751087.post-26063277812670240652019-11-30T17:23:53.803-08:002019-11-30T17:23:53.803-08:00It seems like the write throttling in RocksDB is k...It seems like the write throttling in RocksDB is kind of ad-hoc. Here is what I would consider a principled way to do write throttling:<br /><br />Suppose that the write amplification is W. (This covers the general case: for example for an LSM that doubles the size of each run and does merging of equal-sized runs to make larger runs, and whenever there are two runs of the same size, they get merged, then W is log n. For the LSM that has the size factor go up by a factor of 10 and you merge each time, then W is 10 log_{10} N. We parameterize by W.)<br /><br />Now every time the application writes K bytes into the LSM, we do KW worth of writes of rebalancing. It turns out for all these LSM variants you can find a schedule that does it. For the simple power-of-two LSM, you simply merge K bytes in each level.<br /><br />You might want to support a higher burst rate, feeling that paying log N on every write is too much. I'm not sure how much value there really is to supporting a higher burst rate. Anyway, to support a higher burst rate, you pick a size S that you are willing to get behind. For example, you might set S to 1GB, and you are allowed to write 1GB without doing all the work.<br /><br />Now S gives you a straightforward tuning parameter: Bigger S means you need to allocate more storage and tolerate longer bursts.Bradley C. Kuszmaulhttps://www.blogger.com/profile/16428429628432728830noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-31428048266262797152019-11-30T09:42:51.112-08:002019-11-30T09:42:51.112-08:00I like it, but it is also like the merge operator ...I like it, but it is also like the merge operator in RocksDB. A 2-level LSM is a great fit when data:RAM ratios won't be too big (maybe <= 5:1). Sophia might have been a 2 level LSM, and I know of a successful in-house implementation.Mark Callaghanhttps://www.blogger.com/profile/09590445221922043181noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-2159707187197170302019-11-30T09:36:52.497-08:002019-11-30T09:36:52.497-08:00"Strong throttling" is too vague. This p..."Strong throttling" is too vague. This post explains it:<br />https://github.com/facebook/rocksdb/wiki/Write-Stalls<br />Mark Callaghanhttps://www.blogger.com/profile/09590445221922043181noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-65192313600887998952019-11-27T00:09:15.292-08:002019-11-27T00:09:15.292-08:00I sometimes explain Innodb change buffer as "...I sometimes explain Innodb change buffer as "it's kind of like a 2 level LSM". How right or wrong do you think such a characterisation is?hingohttps://www.blogger.com/profile/09201666166374161923noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-19030949092204713602019-11-26T11:16:00.352-08:002019-11-26T11:16:00.352-08:00What is strong throttling?What is strong throttling?Bradley C. Kuszmaulhttps://www.blogger.com/profile/16428429628432728830noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-37980099295871820622019-11-26T08:30:00.799-08:002019-11-26T08:30:00.799-08:00RocksDB has strong throttling enabled by default. ...RocksDB has strong throttling enabled by default. That creates a few bad experiences for some users who encounter write stalls. Other users quietly benefit, perhaps unaware, by getting less variance on reads. I assume that RocksDB can do better and make throttling more smooth. If nothing else, this would lead to a few interesting research papers.<br /><br />AFAIK the SQLite4 LSM has a solution for this. SQLite doesn't allow background threads so the foreground threads help with compaction. But I need to revisit their design docs.Mark Callaghanhttps://www.blogger.com/profile/09590445221922043181noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-41633762588400139522019-11-26T07:37:48.042-08:002019-11-26T07:37:48.042-08:00How much of write variance in LSM's is due to ...How much of write variance in LSM's is due to overcommitted throughput? For every insert into an LSM, one must perform about log N inserts at higher levels of the LSM, where N is the size of the data set. I have a feeling (unsupported by any evidence) that many LSM implementations simply blast as much as they can into L0, and don't worry about the write debt that they have accumulated. How much of the variance would be solved if for every insert one really did those log N operations at the other layers of the LSM: that is pay the debt as you go?<br /><br />That still leaves GC stalls and TRIM stalls.Bradley C. Kuszmaulhttps://www.blogger.com/profile/16428429628432728830noreply@blogger.com