A merge with tombstones

databases hash table sorting external memory in production

A key-value store is built as an LSM tree: records lie on disk as sorted runs, and a background process merges the runs. Each record has a key, a sequence number (the larger, the newer) and a value. Deleting a key is recorded with a tombstone, the value “-”.

You need to merge several runs into one. Each key keeps only its newest version in the result, the one with the largest number among all the runs being merged. A tombstone is a version too: if it is the newest, the key is deleted. But under the runs being merged lie older, deep runs that do not take part in this merge. A tombstone must be kept if the key occurs in at least one deep run: its old version is there, and without the tombstone it would become visible again. If the key is in no deep run, the tombstone has nothing left to cover, and it is thrown out. Print the merged run. The tests include moments of the tree from the article through which this site’s git history went: the keys there are file paths.

Input

The first line holds k and d: how many runs are merged and how many deep runs lie beneath them (1 ≤ k ≤ 10, 0 ≤ d ≤ 10). Then come the k runs being merged: the first line of a run holds the number of records m, then m lines “key number value”, in increasing order of key. The numbers of all records are distinct, and a value is an integer from 1 to 10⁹ or “-”. Then come the d deep runs: the number of keys and the keys themselves, one per line, in increasing order. A key is a string without spaces of up to 100 characters; keys are compared byte by byte. The input has at most 2·10⁵ lines in all.

Output

The first line holds the number of records c in the merged run, then c lines “key value” in increasing order of key.

In the first example README.md is deleted, and its old version lies deeper: the tombstone stays. old.txt is deleted, and it is not deeper: the tombstone goes. In the second example there are no deep runs at all, and the tombstone of b.txt is older than the record in the neighbouring run: the file was created anew.

Examples

Example 1

Input

2 1
3
README.md 9 -
app.js 8 140
old.txt 7 -
3
README.md 5 2100
app.js 4 120
style.css 3 800
2
README.md
index.html

Output

3
README.md -
app.js 140
style.css 800

Example 2

Input

2 0
2
a.txt 6 -
b.txt 5 10
3
a.txt 2 70
b.txt 4 -
c.txt 1 30

Output

2
b.txt 10
c.txt 30

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

What will a search for the key README.md read after the merge if the tombstone is thrown out? The deep run has its old version.

2The idea

A merge is choosing the newest version of each key, and then deciding about tombstones. The newest version comes from a dictionary “key → (number, value)”, where a record is replaced if one with a larger number arrives. A tombstone with the newest number cannot be thrown out while any version of the key lies somewhere below: a search goes from new runs to old and stops at the first one found, and without the tombstone that would be the old version, and the deleted file would come back to life. So gather the keys of the deep runs into a set and keep a tombstone only for keys in it.

3Walkthrough

The runs are sorted, and in real stores they are merged as a stream, with a heap by current key, as in merging k lists, so as not to hold everything in memory. Here all the records fit in a dictionary, and it plus a sort of the keys at the end is enough. The set of keys of the deep runs can be replaced by a binary search in each of them: they are sorted too.

Real stores decide about tombstones more crudely. The simplest rule is to throw out tombstones only when merging into the very bottom level: there is nothing below. More precisely, check whether the key ranges of the deep runs overlap the key. And while a tombstone is not thrown out, it takes space and slows reads: in databases with frequent deletions, “graveyards” of tombstones are a well-known plague. In the third test, from the site’s history, four L0 runs are merged; 30 tombstones remain in the result, because old versions of these files lie deeper.

3+Solution

4Complexity

O(N log N) for N records with the sort at the end; a streaming merge with a heap is O(N log k) with O(k) memory.

5Common mistakes

Throwing out all tombstones. The result looks cleaner, but deleted keys with versions in deep runs come back to life; the first example catches exactly this.
Keeping all tombstones. Nothing comes back to life, but tombstones pile up for ever; here it is a wrong answer.
Newest by run, not by number. The runs go from new to old, but the record number decides; the rule rests on it.
Deleted, then created anew. If the key was written again after the tombstone, the newest version is a value, and the tombstone disappears along with the old versions.

Algorithms behind it

SYS Data structure LSM tree Writes gather in memory and land on disk as sorted runs; background merges keep the number of runs small. a write is O(1) amortised in memory plus O(L·T/B) for rewriting during merges; a read is one run per level 2 problems SRT Algorithm Merge sort Halves, sorts the halves and merges: n log n on any input, stable, fit for external memory. O(n log n) 2 problems