Friday, November 8, 2019

Jungle - LSM plus copy-on-write B-Tree

This is a review of Jungle which is an LSM variant that uses a copy-on-write (CoW) B-Tree internally. One of the Jungle developers previously invented ForestDB. I am a fan of his work.

At a high level Jungle is an LSM with leveled compaction but thanks to the CoW B-Tree it has different read, write and space amplification tradeoffs. I don't understand Jungle well enough to explain where it is better, but I am happy to share this review and accept corrections. My summary of Jungle is:
  • One sorted run per level
  • The per level file structure uses an index+log approach where the index is a CoW B-Tree, values are appended to the value log and the B-Tree entries point into the log. There is also a bloom filter.
  • Inter-level merge does compaction between adjacent levels. I think this is some-to-some as some data is moved from Ln to Ln+1 in a batch, values are appended to the value log, keys are inserted into the B-Tree and modified B-Tree pages are persisted by appending to the end of the B-Tree files. Because of CoW the path from leaf to root is made dirty when a leaf page is modified.
  • In-place merge does GC within a level to reclaim space from the B-Tree files and value log. The B-Tree is scanned in order to write a new B-Tree and new value log. Space is wasted because updates were appended to the end of the B-Tree file and value log.
Purpose

The index+log approach is used to reduce write amplification from large values. The per-level write-amp from moving a KV pair from Ln to Ln+1 is the sum of the write-amp from adding keys to the B-Tree and from appending to the end of the value log. 

Assuming a batch of KV pairs is inserted then write-amp for the value log is minimal -- close to 1. If 32 1kb values are moved then 32kb is written. I am uncertain about the average and worst case write-amp for the B-Tree even when I only consider write-amp for the leaf pages and ignore the non-leaf pages. For the worst-case assume that each key makes a leaf page dirty.  Then for each KV pair with a small key and 1kb value there is 4kb + 1kb written (4kb for B-Tree, 1kb for value log) and the per-level write-amp is ~5. That is a good worst-case. I frequently see per-level write-amp of ~5 for production workloads with RocksDB so I wonder what the average case will be for Jungle.

There is additional write-amp from doing periodic in-place merges to reclaim space. I won't try to estimate the impact from that.

Comments
  • The CoW B-Tree in Jungle is CoW-S because writes are appended and GC must eventually be done.
  • While ordering values in RocksDB has a cost, more write-amp, it also has a benefit, less cache-amp. RocksDB needs a pointer (index entry) in memory per block to achieve a worst-case of ~1 disk read per point query -- see the RocksDB data block index. With index+log the values are not in key order and this needs a pointer (index entry) in memory per KV pair. Assuming these pointers are ~8 bytes there is a huge difference in memory overhead between 8 bytes / database page and 8 bytes per KV pair assuming KV pairs are not too big. Per the CRUM Conjecture it is hard to be better in all dimensions -- read, write, disk space and memory. 
  • It will be hard to do compression for the value log if only a few values are appended at a time. But if each inter-level merge adds many 4kb pages worth of data to the value log then this isn't a problem.
  • Range scans are more expensive with index+log because values are not in key order and each value might require a storage IO and the CPU overhead for decompression. This should only be a problem for the largest level of the LSM tree.

Thursday, November 7, 2019

Revisiting Kudu

I read the Kudu paper many years ago. It is worth reading but I never published my review so I re-read the paper this week. My review is limited to the paper and I ignore improvements since then. My focus is on storage so I also ignore most of the distributed system features.

I don't have access to my old review of the paper when I read it years ago. I might have considered it to be an LSM variant. Now I consider it to be an example of an index+log index structure.

Kudu is a scale-out index structure for analytics engines like Impala. The goals for Kudu are fast columnar scans, low latency updates and low performance variance. I assume that Kudu satisfied those goals. The features include:
  • Data is stored in tables and a table has a fixed schema. I am curious about the demand for flexible schemas.
  • It is primary key only. It uses Raft to make sure replicas stay in sync. If global secondary indexes were supported then something like XA across shards would also be needed. That is much harder, but feasible -- see Spanner, CockroachDB and Yugabyte.
  • Supports add/drop column but PK columns can't be dropped. I am not sure whether the PK can be changed.
  • Supports insert, update, delete and range query. It might consider a point query to be a simple range scan. Update and delete must fully specify the PK values for the rows to be changed.
  • Supports range and hash partitioning but that paper section confused me
  • Supports single-row transactions. I assume a batch can be submitted but I am not sure how per-row outcomes are reported to a client.
  • Compaction uses cost-based decisions to merge data where the objective function is to improve read efficiency. I am a big fan of that.

Index+log

I think this is an example of an index+log index structure where the DiskRowSets are log segments. GC is clever and there are two parts to it. First, there is compaction between DeltaMemStore and DiskRowSet. This removes deleted rows and merges long update chains. Second, there is compaction between DiskRowSets. This reduces the number of places that must be checked for a given key range.

In the standard index+log approach only the first type of compaction is done for a log segment. That usually requires all of the index to be in memory because each row from a log segment needs an index probe to determine whether the row is live. For Kudu a search of the DeltaFile determines liveness. It is not clear to me whether DeltaMemFiles are clustered per DiskRowSet to reduce the amount of data that should be in memory when such compaction is done.

I briefly cover the second type of compaction at the end of my blog post. The benefit from merging log segments with index+log is larger sorted runs. Write-optimized index structures impose a CPU and IO read efficiency penalty. Merging log segments like this reduces that penalty.

Storage

Tables are horizontally partitioned into tablets and each tablet consists of a MemRowSet, many DiskRowSets, a DeltaMemStore and many DeltaFiles. Inserts are written into a MemRowSet, when full a MemRowSet is flushed to disk creating a DiskRowSet. A DiskRowSet is limited to ~32MB. Only inserts are directly written into DiskRowSets. Because there is a PK check on insert a row will exist in at most one DiskRowSet.

Deletes and updates are first written into a DeltaMemStore and when full that is flushed to disk to create a DeltaFile. While only inserts are directly written to a DiskRowSet. Eventually a DeltaMemStore will be merged with a DiskRowSet so the effect of update and delete eventually reach a DiskRowSet.

Storage is columnar for the rows in a DiskRowSet. Encoding takes advantage of data types to use less space and block compression is optional. This output is written to a sequence of pages for each column. Then there is a B-Tree index that maps ID to page where ID is the ordinal offset of the row within the DiskRowSet (when a DiskRowSet has 1M rows then the ID is from 1 to 1M assuming it starts at 1). Although I am not sure if that index has an entry per page or per row.

There is also a PK index column that has the encoded PK values (encoded because the key is a string even when the PK has more than one column). It wasn't clear to me whether there was an index built on that or if binary search was used. I assume the value in this case is the ID (ordinal offset) for the row. A paged bloom filter is created for the PK index column.

Range scans will start by searching the PK index column to determine the row IDs that must be retrieved and then for each column that must be returned search the per-column indexes using those IDs.

Friday, November 1, 2019

Fun setting up Ubuntu on Win 10 Home

I feel like I have gone back to Linux from 25 years ago when it was quite a challenge to install, configure storage, setup networking with a modem and then getting X working. My setup is latest Windows 10 Home, new-ish HP Omen laptop, Ubuntu 18.04 and VMWare Player 15.5.0. Some useful advice is here.

I lost a few hours today setting up Ubuntu on a laptop running Win 10 Home. The magic that fixed this for VirtualBox and VMWare was to run the following command in the Command Prompt app, run as an admin. It does not work if you try to run it in PowerShell. Reboot after running this:
bcdedit /set hypervisorlaunchtype off
This was a not fun experience shared by many others trying to use VirtualBox and VMWare. I assume the problem is Win 10 and not the VM apps. As much as I don't like the Mac keyboard, each time I try to switch to Windows I quickly realize it is a bad idea. While WSL and WSL2 sound OK, I really want the full Linux experience and don't want to deal with running an X server separately in Windows to get the UI for Linux apps.

For those running Ubuntu natively on their laptops with great keyboards, I salute you. You have every right to snicker at me.

Shared folders

Shared folders work except for automount. This command fixes that:
vmhgfs-fuse .host:/ /mnt/hgfs -o subtype=vmhgfs-fuse,allow_other

The alternative is to use the VMWare Player UI to disable/reenable shared folders each time I reboot the VM. The best solution is to add something to /etc/fstab and I will do that soon.

Wednesday, October 30, 2019

USL, universal scalability law, is good to know

The USL is worth understanding. USL is short for universal scalability law and was created by Neil Gunther for use in capacity planning. I don't do much capacity planning but the USL is also valuable for explaining performance. Performance problems for the old InnoDB rw-lock (circa 2007) would have been easy to describe via the USL because "wake all" on unlock is an N2 overhead -- see the 𝛽 parameter in the USL.

A longer version of the USL is here. The USL predicts how throughput will change (increase or decrease) with concurrency. One version of the formula where X(i) is throughput with i concurrent clients is below.

                 X(1) * N
     X(N) =  -------------------
             1 + α(N-1) + ꞵN(N-1)

The denominator determines how throughput changes with concurrency. When it is one then there is linear scaleup. The best way to get linear scaleup is to cheat and choose an easy base case but otherwise the denominator is greater than 1 and the USL explains less than linear scaleup. The components in the denominator represent the overhead from contention and coherency. The alpha term represents contention and the beta term represents coherency.

I write above that "wake all" on unlock has an N2 overhead. By this I mean that when N threads are trying to get through a synchronization object one at a time and all waiters wake on unlock then there are O(N2) wakeups -- (N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1. The beta term in the denominator represents the coherency overhead and 
has an N2 term as 𝛽N(N-1) = 𝛽N2-𝛽N.

Amdahl's Law

The long post states that when B=0 and X(1)=1 then the USL is reduced to Amdahl's Law. I will derive the math for that here. The key point is that α=(1-p) where p is the fraction of the workload that is parallel in Amdahl. 

# Amdahl's law where p is the fraction of the workload
# that is parallel, N is same as for USL
                    1
     Speedup = -----------
               (1-p) + p/N

# Start with USL
                      N
     X(N) =  -------------------
             1 + α(N-1) + ꞵN(N-1)

# Update for X(1)=1, ꞵ=0, α=(1-p)
                 N
     X(N) =  ----------
             1 + (1-p)(N-1)

# Algebra for denominator, expand and then reduce
                 N
     X(N) =  ----------
             N - pN + p

# Multiply numerator and denominator by 1/N
                 1
     X(N) =  ----------
             (1 - p) + p/N

# Now it looks like Amdahl where α=(1-p)

Predicted max throughput

The long post states that the max throughput occurs at sqrt((1-α)/ꞵ). That is the value of N for which X(N)' = 0. I won't derive it here but X(N)' is:
                  1 - 
α - ꞵN2
     X(N)' = ---------------------
             (1+α(N-1) + ꞵN(N-1))2

Then X(N)'=0 when the numerator is zero and that happens when N=sqrt((1-α)/ꞵ). That determines a critical point for X(N) which is either a min or max. In this case it is a max. I assume that X(N) is concave without deriving X(N)''.

Tuesday, October 29, 2019

Review of "5 Minute rule - thirty years later"

The 5 Minute rule paper has been updated and it is worth reading. The paper explains how to make cost-based decisions for tiered storage, applies that using price and performance of devices over the past 30 years and then makes predictions based on current trends.

There is a prediction in the paper that will provoke discussion --  the price vs performance advantage for disk vs tape is getting smaller and soon we might need Hadoop for tape. That will be an interesting project.

5 minute rule math

The 5 minute rule math explains what data should be in a cache by considering the price of the cache and the price/performance of the storage device. The math has been used where cache+storage are DRAM+disk, DRAM+SSD and SSD+disk. Now it has be updated for NVM.

The equation is presented as two ratios: technology and economic. Below I explain how to derive it.

Technology ratio            Economic ratio

Pages/MBofCache             Price/StorageDevice
-----------------------  *  -------------------
OpsPerSec/StorageDevice     Price/MBofCache

If you reduce the equation above you end up with Pages/OpsPerSec. The unit for this is seconds and this is inverse of the access rate. When Pages/OpsPerSec = X then the cache should be large enough to fit pages accessed more frequently than every X seconds (1/X accesses per second). The formula above doesn't tell you to buy X MB of cache. It does tell you to buy enough cache to fit all pages accessed more frequently then once per X seconds.

Now I derive the formula as the presentation above can confuse me. The cost of a cache page is:
Price/MBofCache * MBofCache/Pages

The cost of 1 OpsPerSec from a storage device is:
Price/StorageDevice * StorageDevice/OpsPerSec

Each cache page has a cost and a benefit. The benefit is the reduction in OpsPerSec demand for cached data. Assume there are K pages of cache and the access rate for each page is A. Then this cache reduces the OpsPerSec demand by K*A. From this we can determine the value of A for which the cache cost equals the benefit:

K * Price/MBofCache * MBofCache/Pages =
    K * A * Price/StorageDevice * StorageDevice/OpsPerSec

# And then solve for A, K cancels, move ratios to LHS


Price/MBofCache       MBofCache/Pages
------------------- * ----------------------- = A   
Price/StorageDevice   StorageDevice/OpsPerSec

# LHS can be reduced to 1/Pages / 1/OpsPerSec
# which is OpsPerSec / Pages while '5 minute rule'
# above solves for Pages / OpsPerSec, so invert LHS
# to get 1/A

Price/StorageDevice   StorageDevice/OpsPerSec
------------------- * ----------------------- = 1/A
Price/MBofCache       MBofCache/Pages

# Now reorder LHS

StorageDevice/OpsPerSec   Price/StorageDevice   
----------------------- * ------------------- = 1/A
MBofCache/Pages           Price/MBofCache

# Given that X/Y = 1/Y / 1/X when X, Y != 0 then
# first term in LHS can be rewritten to get

Pages/MBofCache           Price/StorageDevice
----------------------- * ------------------- = 1/A
OpsPerSec/StorageDevice   Price/MBofCache

# A is an access rate, OpsPerSec / Pages, and 1/A is
# Pages/OpsPerSec. Thus we have derived the formula.

Technology

The numerator for the technology ratio changes slowly. Assuming file system pages are cached, the page size is now a multiple of 4kb (ignoring compression). There is one case for smaller pages -- NVM on the memory bus might allow for the return of 512b pages. The denominator for the technology ratio is interesting. It has barely changed for disk but changed a lot SSD.

For the economic ratio the cost of DRAM, disk, SSD and NVM is not changing at the same rate. Thus advice changes depending on the technology. In 2007 the advice for DRAM+SSD was to cache objects accessed every 15 minutes and in 2017 it is every 7 minutes so less DRAM is needed. The advice for DRAM+disk is the opposite. DRAM cost dropped more than disk OpsPerSec improved so more DRAM cache is needed.

Cost

The paper has some discussion on cost. The cost can be the retail price from a device vendor or the all-in cost from a public cloud vendor. The retail price can be misleading as that isn't TCO. You need to consider power and more. In either case (retail, public cloud) capacities come in discrete sizes and you might not be able to deploy the optimal values.

Finally, the 5 minute rule doesn't solve for all constraints, nor should it. There  are limits to power, space and throughput that must be considered. Motherboards are limited by memory slots, PCIe slots and throughput to storage. Power might not be unlimited. Constrained optimization is an interesting topic, but not for this post.

Friday, October 25, 2019

Nitpicking papers in the LSM space

Nits:
  • LSM compaction does merge, not merge sort. Compaction inputs are already sorted. Merge sort is O(NlogN) for N records. Naive merge is O(NlogK) for N records and K input streams and in some cases RocksDB can do better than naive merge -- see the reference to optimized binary heap. Compaction merges for RocksDB with leveled compaction have two forms -- L0 to L1 and Ln to Ln+1. For L0 to L1 there might be ~4 streams from the L0 and 1 stream from the L1 and size(L1) is usually >= size(L0). For Ln to Ln+1 there is one stream from each and size(Ln+1) is approximately 10 * size(Ln).
  • LSMs do large random writes, not sequential writes. Writes are sequential from perspective of a single-file but a busy LSM does compaction and memtable flush concurrently. So there are concurrent reads and writes from perspective of device -- each stream of reads and writes is sequential but they are interleaved at the device level.
  • The statement write amplification is approximately 10 * num-levels is some of: the worst case, a hypothesis, an unvalidated performance model. I am a frequent user of unvalidated performance models but they have their limits. There is an amazing paper that measures write-amp in practice and then provides a brilliant explanation. I wish there were more reporting of write-amp from production workloads. LevelDB overstates write-amp because it uses too many levels because the L0 and L1 are small (~10mb).
  • It is great to read about new index structures that don't support range query in pursuit of less write-amp. If a workload doesn't need range query then maybe an LSM isn't the best choice. The other reason to use an LSM with leveled compaction is low space-amp, so I hope that some alternatives consider ways to keep space-amp low while also getting low write-amp.
  • Consider CPU and IO overhead. That is there are IO and CPU components for read and write amplification. IO gets a lot of attention. CPU needs more attention.
  • Benchmarking is hard. See here for an example of a horrible mistake I made which lead to many bogus reports of lousy MySQL performance regressions. I explained some of the problems for LevelDB and RocksDB benchmarks here and here. LevelDB doesn't target high performance, RocksDB is hard to configure, papers rarely provide enough details to support reproduction and even if they did nobody is volunteering their time to reproduce results. I assume that benchmark result accuracy is inversely related to the number of systems that have been tested for a given paper -- expertise is in short supply. My offer for advice still stands. I have read about possible programs that would volunteer grad students to reproduce results. While I think that would be a great education, I wonder if it would advance their academic careers. 

Thursday, October 24, 2019

Tuning space and write amplification to minimize cost

In a previous post I described how to tune for space and write amplification with an LSM or index+log index structure. In this post I explain how to use that to minimize the storage cost for a workload.

This is an optimization problem and the objective function is to minimize the number of storage devices. The model I use was described in a previous post but I summarize it here:
  • Storage device supplies r units of read IO, w units of write endurance and s units of capacity.
  • Workload demands R units of read IO, W units of write endurance and S units of capacity.
  • max(R/r, W/w, S/s) storage devices are required when amplification is ignored
  • max(R*ar/r, W*aw/w, S*as/s) storage devices are required when amplification is not ignored where ar, aw and as are read, write and space amplification
Here I assume that read IO is never the bottleneck and the goal is to minimize max(W*aw/w, S*as/s). That occurs when W*aw/w = S*as/s. I assume that W, w, S and s are constants so the goal is to tune aw and as to solve the equation. Note that W/w and S/s are the number of devices needed for the workload based on endurance and capacity.

I thought I previously published a blog on this topic but I could not find it.

Index+log

For index+log I assume that aw = 100/(100-pfull) and as = 100/pfull where pfull is the percentage of device capacity available to the user. With that I can determine the value of pfull that solves the equation.

W*aw/w = S*as/s
# reorder LHS and RHS
W/w*aw = S/s*as
# replace aw and as
W/w * 100/(100-pfull) = S/s * 100/pfull
# multiply LHS and RHS by pfull and then (100-pfull)
pfull * W/w * 100 = (100-pfull) * S/s * 100
# divide LHS and RHS by 100
pfull * W/w = (100-pfull) * S/s
# expand RHS
pfull * W/w = 100 * S/s - pfull * S/s
# add pfull * S/s to LHS and RHS
pfull * W/w + pfull * S/s = 100 * S/s
# factor LHS
pfull * (W/w + S/s) = 100 * S/s
# done
pfull = 100 * S/s / (W/w + S/s)

From the solution if I need 10 devices based on endurance (W/w = 10) and 30 devices based on capacity (S/s = 30) then using pfull = 100 * 30 / (10+30) = 75% minimizes the number of devices required. With pfull=75 then aw=4 (100/25), as=1.33 (100/75), W/w*aw=40, S/s*as=40 and the workload needs 40 storage devices. Were I to use pfull=50 then aw=2, as=2, W/w*aw=20, S/s*as=60 and the workload needs 60 devices. Were I to use pfull=80 then aw=5, as=1.25, W/w*aw=50, S/s*as=38 (rounded up) and the workload needs 50 devices. So pfull=75 looks like a good choice.

LSM

Space and write amplification are inversely related for both LSM and index+log but the math is easier for index+log. We can start with the equation to solve, but I won't solve it.

W*aw/w = S*as/s
# reorder LHS and RHS
W/w*aw = S/s*as
# replace aw with 0.8 * fo * L and as with 1 + 1/fo
# where fo is per-level fanout and L is number of levels 
W/w * 0.8 * fo * L = S/s * (1 + 1/fo)
# alas fo (per-level fanout) is a function of L (number of levels) and total fanout
# assume total fanout is t then fo = t ^ 1/L where t is a constant
W/w * 0.8 * t^1/L * L = S/s * (1 + 1/t^1/L)

I stopped at this point because the math isn't easy and L must be an integer >= 1 so an easy way to solve this is to compute the LHS and RHS this for L=1, 2, ..., 10 and choose L that minimizes the difference. For the example above with W/w=10 and S/s=30 then LSM write-amp is always sufficiently larger than space-amp that write-amp determines the number of devices and L=6 or 7 minimizes write-amp and the number of storage devices. Were S/s increased to 200 then L=3 or 4 minimizes the number of storage devices.

CPU-bound sysbench on a large server: Postgres 12 to 19 beta1

This has results from sysbench on a small server with Postgres versions 12 through 19 beta1. Sysbench is run with high concurrency (40 conne...