Rocksdb: Bug with delete range

Created on 10 Oct 2017 · 10Comments · Source: facebook/rocksdb

Expected behavior

Compaction should not affect keys' visibility.

Actual behavior

1) Open rocksdb with existing data in readonly model, Seek('key') can not get this key.
2) Use ldb compact the whole db.
3) Open rocksdb with the existing data in readonly model again, Seek('key') can get this key.

Steps to reproduce the behavior

In our tests, only when we use delete range this strange bug will be triggered.

We copy these existing data(it's about 162GB in total) and can easily reproduce this bug.

@ajkr If you want more informations like LOG/MANIFEST, please tell me.

Source

zhangjinpeng1987

Most helpful comment

It could've been that two versions of the same user key were output by compaction in adjacent files. Then the first file's key-range doesn't need to be extended even if a range deletion spans the two files, because its largest user key already matches the next file's smallest user key (and the logic that uses file endpoints only really cares about user key).

For the second file, we don't really need to update its begin key either, for the same reason above that the files' endpoints already have overlapping user keys. The way I implemented it (https://github.com/facebook/rocksdb/blob/master/db/range_del_aggregator.cc#L464-L469), though, might overwrite the second file's begin key anyways. E.g., if the second file's first regular key has seqnum zero (which is likely as this is happening in your bottom level), the key forged on line 464 will have same user key, same seqnum, and higher value type than the first regular key. Since higher value type causes an internal key to be considered smaller, the forged key comes earlier and thus overwrites the second file's begin key.

ajkr on 20 Oct 2017

❤1 😄1

All 10 comments

I dump manifest and find overlap in level 4, this should not happen.

...
698000000000FF0000020133373636FF00000000FB038000FF000059CEAE880380FF0000000A6B661600FE' seq:13885251181, type:0]
 732184:8728662['7A7480000000000000FF835F698000000000FF0000020133373636FF00000000FB038000FF000059CEAE970380FF0000000A6B943300FE' seq:13885251800, type:0 .. '7A7480000000000000FF835F698000000000FF0000020135323539FF00000000FB038000FF000059CDA8B70380FF000000077160D800FE' seq:0, type:1]
 732188:8737494['7A7480000000000000FF835F698000000000FF0000020135323539FF00000000FB038000FF000059CDACFD0380FF000000077265C000FE' seq:0, type:1 .. '7A7480000000000000FF835F698000000000FF0000020136353438FF00000000FB038000FF000059CEAF0A0380FF0000000A6D4E7D00FE' seq:13893508569, type:0]
 732193:8739596['7A7480000000000000FF835F698000000000FF0000020136353438FF00000000FB038000FF000059CEAF290380FF0000000A6D8F8B00FE' seq:13894913374, type:0 .. '7A7480000000000000FF835F698000000000FF0000020137383439FF00000000FB038000FF000059CB5B7A0380FF000000000B37C800FE' seq:0, type:1]
 732048:8751006['7A7480000000000000FF835F698000000000FF0000020137383436FF00000000FB038000FF000059CEB2710380FF0000000A79AFAD00FE' seq:13923655971, type:0 .. '7A7480000000000000FF855F698000000000FF0000020136303837FF00000000FB038000FF000059CEB2A00380FF0000000A76F9D700FE' seq:13925270798, type:0]
 732198:8736763['7A7480000000000000FF835F698000000000FF0000020137383439FF00000000FB038000FF000059CB81500380FF0000000050437E00FE' seq:0, type:1 .. '7A7480000000000000FF835F698000000000FF0000020139313335FF00000000FB038000FF000059CEAEBA0380FF0000000A6C0DD000FE' seq:13895140974, type:0]
 732203:8680623['7A7480000000000000FF835F698000000000FF0000020139313335FF00000000FB038000FF000059CEAEC20380FF0000000A6C314F00FE' seq:13895141653, type:0 .. '7A7480000000000000FF835F728000000002FF383B290000000000FA' seq:0, type:1]
 732209:8566834['7A7480000000000000FF835F728000000002FF383B2A0000000000FA' seq:0, type:1 .. '7A7480000000000000FF855F698000000000FF0000010380000000FF59CB749303800000FF00002DBE7C000000FC' seq:0, type:1]
 732213:8647821['7A7480000000000000FF855F698000000000FF0000010380000000FF59CB749303800000FF00002DBE7D000000FC' seq:0, type:1 .. '7A7480000000000000FF855F698000000000FF0000020131353400FF00000000FA038000FF000059CDA8B60380FF00000007708D2000FE' seq:0, type:1]
 732218:8736430['7A7480000000000000FF855F698000000000FF0000020131353400FF00000000FA038000FF000059CE42820380FF00000009496BF300FE' seq:0, type:1 .. '7A7480000000000000FF855F698000000000FF0000020132383036FF00000000FB038000FF000059CEB0290380FF0000000A6D796400FE' seq:13903294680, type:0]
 732223:8730073['7A7480000000000000FF855F698000000000FF0000020132383036FF00000000FB038000FF000059CEB02D0380FF0000000A6D8B4400FE' seq:13903450144, type:0 .. '7A7480000000000000FF855F698000000000FF0000020134343635FF00000000FB038000FF000059CEABFF0380FF0000000A5E997900FE' seq:13872751038, type:0]
 732228:8734093['7A7480000000000000FF855F698000000000FF0000020134343635FF00000000FB038000FF000059CEAC030380FF0000000A5EAC6100FE' seq:13872897400, type:0 .. '7A7480000000000000FF855F698000000000FF0000020135383936FF00000000FB038000FF000059CEABAA0380FF0000000A5D5CC300FE' seq:13869932780, type:1]
 732232:8744879['7A7480000000000000FF855F698000000000FF0000020135383936FF00000000FB038000FF000059CEABAB0380FF0000000A5D5F9F00FE' seq:13869986508, type:0 .. '7A7480000000000000FF855F698000000000FF0000020137323035FF00000000FB038000FF000059CEACD30380FF0000000A61E23000FE' seq:13880362119, type:0]
 732049:8749652['7A7480000000000000FF855F698000000000FF0000020136303837FF00000000FB038000FF000059CEB2AC0380FF0000000A77263000FE' seq:13925681864, type:0 .. '7A7480000000000000FF875F698000000000FF0000020134313236FF00000000FB038000FF000059CEB22C0380FF0000000A74738100FE' seq:13921502691, type:0]
...

We can see that 732048's largest key is larger than 732198's smallest key.

zhangjinpeng1987 on 10 Oct 2017

LOG.tar.gz
manifest.tar.gz

zhangjinpeng1987 on 11 Oct 2017

Apparently there is something wrong with the smallest key of 729853, which is one of JOB 7103's output file. This is the oldest suspect place by time I can find.

{"Level": 4, "FileNumber": 729850, "FileSize": 8563794, "SmallestIKey": 
"'7A7480000000000000FF8D5F728000000000FF5CDB8E0000000000FA' seq:0, type:1", "LargestIKey": 
"'7A7480000000000000FF8F5F698000000000FF0000010380000000FF59CB540503800000FF0000000446000000FC' seq:13854437548, type:1"}

{"Level": 4, "FileNumber": 729853, "FileSize": 8564301, "SmallestIKey": 
"'007480000000000000FF8F5F698000000000FF0000010380000000FF59CD1D5E03800000FF0005C5810B000000FC' seq:0, type:15", "LargestIKey": 
"'7A7480000000000000FF8F5F698000000000FF0000010380000000FF
59CE252A03800000FF00092455E6000000FC' seq:0, type:1"}

{"Level": 4, "FileNumber": 729856, "FileSize": 8686523, "SmallestIKey": 
"'7A7480000000000000FF8F5F698000000000FF00000103
80000000FF59CE252A03800000FF00092455E7000000FC' seq:0, type:1", "LargestIKey": 
"'7A7480000000000000FF8F5F698000000000FF0000020131373337FF00000000FB038000FF000059CEAFA80380FF00
00000A71730400FE' seq:13898831727, type:1"}

The smallest key should be "7A74...", not "0074...".
@ajkr

zhangjinpeng1987 on 17 Oct 2017

@siying

zhangjinpeng1987 on 17 Oct 2017

I think the problem is here, lower_bound is just a reference to meta->smallest, actually refer to the internal std::string, but meta->smallest may be changed in AddToBuilder. So the original internal std::string will be destructed,
and the memory belonged to the original internal std::string maybe reuse by other objects, and the content will be changed.

zhangjinpeng1987 on 17 Oct 2017

great find :). sorry for the delay in replying - have been busy with several other things.

ajkr on 17 Oct 2017

😕1

There is still one place i can't understand, why 729850 's largest key 's type is not kTypeRangeDeletion? @ajkr

zhangjinpeng1987 on 18 Oct 2017

looks like it ends in a user key with seqnum 13854437548. The file's largest key only gets overwritten if we extend the file's key-range due to a range deletion spanning past the final user key.

ajkr on 20 Oct 2017

❤1 😄1

@ajkr Thanks for your explanation, i think i get it.

Let's compare the largest key of the first file and the smallest key of the second file:
7A7480000000000000FF8F5F698000000000FF0000010380000000FF59CB540503800000FF0000000446000000FC seq:13854437548, type:1
007480000000000000FF8F5F698000000000FF0000010380000000FF59CD1D5E03800000FF00
05C5810B000000FC seq:0, type:15

The first byte of second file's smallest key has undoubtedly been modified, but the tail seems is correct. So we can assume before call AddToBuilder, the meta->smallestof second file is 7A7480000000000000FF8F5F698000000000FF0000010380000000FF59CD1D5E03800000FF00
05C5810B000000FC, which is larger than the largest key of the first file. Then we can infer a conclusion that there is no delete range overlap with the gap between first file and second file, since the type of first file's largest key is TypeValue.
But there is possibility that a delete range's start key is equal to the second file's smallest key. After https://github.com/facebook/rocksdb/blob/master/db/range_del_aggregator.cc#L464-L469 is called for the first time, lower_bound was modified, the meta->smallest is correct temporarily. But when processing remaining stripe map, if there exist delete range smaller than the wrong lower_bound,meta->smallest will be modified again.