Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

DropPrefix breaks levels, resulting in hard crashes and data loss #1380

Closed
damz opened this issue Jun 21, 2020 · 2 comments · Fixed by #1381
Closed

DropPrefix breaks levels, resulting in hard crashes and data loss #1380

damz opened this issue Jun 21, 2020 · 2 comments · Fixed by #1381
Assignees
@jarifibrahim
Labels
kind/bug Something is broken. priority/P0 Critical issue that requires immediate attention. status/accepted We accept to investigate or work on it.

Comments

@damz
Copy link
Contributor

damz commented Jun 21, 2020 •
edited
Loading

What version of Go are you using (go version)?

$ go version
go version go1.14.4 linux/amd64

What operating system are you using?

Linux

What version of Badger are you using?

master

Steps to reproduce the issue

This is actually pretty tricky to reproduce in a synthetic way.

You need a database with a sufficient amount of data so that on one level you have a layout similar to this:

  • Table containing the badgerMoveKey prefix (either actual move keys, or something else), and is not full
  • [...] Some number of other tables
  • Table with the prefix you want to drop

In this case, the dropPrefix will generate a same-layer compaction request where bot has two non-consecutive tables:

https://github.com/dgraph-io/badger/blob/d37ce36911ae349fbedba342f693184aa434cc30/levels.go#L301-L330

If it happens that compactTables() generates tables without the same exact boundaries (for example because there were expired keys / deleted keys) then the result will be a layer with overlapping tables.

The assumption that bot has consecutive tables was broken in #1331

This results in data loss, and/or various assertions depending on what compactions are going to happen after that. In our case, we trigger the new assertion added in #1365 and various other assertions.

How to fix?

dropPrefix should generate a separate compaction request for the move key prefix, instead of trying to generate a single compaction request for everything.
@jarifibrahim jarifibrahim added kind/bug Something is broken. priority/P0 Critical issue that requires immediate attention. status/accepted We accept to investigate or work on it. labels Jun 21, 2020
damz added a commit to damz/badger that referenced this issue Jun 22, 2020
@damz
Rework DB.DropPrefix
4c4867d 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant
  that bottom tables need to be consecutive (issue hypermodeinc#1380)
- It performs the same level compactions in increasing order
  of levels (starting from L0) which leads to old versions
  of keys for the prefix re-surfacing to active transactions
- When you have to drop multiple prefixes, the API forces
  you to drop one prefix at a time and go through the whole
  expensive table rewriting multiple times.
@damz damz mentioned this issue Jun 22, 2020
Merged
damz added a commit to damz/badger that referenced this issue Jun 22, 2020
@damz
Rework DB.DropPrefix
8075bd6 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant
  that bottom tables need to be consecutive (issue hypermodeinc#1380)
- It performs the same level compactions in increasing order
  of levels (starting from L0) which leads to old versions
  of keys for the prefix re-surfacing to active transactions
- When you have to drop multiple prefixes, the API forces
  you to drop one prefix at a time and go through the whole
  expensive table rewriting multiple times.
@jarifibrahim jarifibrahim self-assigned this Jun 23, 2020
@jarifibrahim
Copy link
Contributor

dropprefix

The diagram above explains how the current implementation of drop prefix in #1331 can create invalid levels.

@damz
Copy link
Contributor Author

damz commented Jun 26, 2020

That's exactly that 👍

jarifibrahim pushed a commit that referenced this issue Jun 27, 2020
@damz
Rework DB.DropPrefix (#1381)
e013bfd 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue #1380). See
  #1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes #1381

Co-authored-by: Ibrahim Jarif <[email protected]>
@jarifibrahim jarifibrahim mentioned this issue Jun 30, 2020
Closed
jarifibrahim pushed a commit that referenced this issue Jul 6, 2020
@damz
Rework DB.DropPrefix (#1381)
e5fd05a 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue #1380). See
  #1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes #1381

Co-authored-by: Ibrahim Jarif <[email protected]>
(cherry picked from commit e013bfd)
jarifibrahim pushed a commit that referenced this issue Sep 9, 2020
@damz
Rework DB.DropPrefix (#1381)
436a1bb 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue #1380). See
  #1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes #1381

Co-authored-by: Ibrahim Jarif <[email protected]>
(cherry picked from commit e013bfd)
@jarifibrahim jarifibrahim mentioned this issue Sep 9, 2020
Merged
jarifibrahim pushed a commit that referenced this issue Sep 10, 2020
@damz
Rework DB.DropPrefix (#1381) (#1514)
058a414 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue #1380). See
  #1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes #1381

Co-authored-by: Ibrahim Jarif <[email protected]>
(cherry picked from commit e013bfd)

Co-authored-by: Damien Tournoud <[email protected]>
jarifibrahim pushed a commit that referenced this issue Oct 2, 2020
@damz
Rework DB.DropPrefix (#1381)
73098bd 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue #1380). See
  #1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes #1381

Co-authored-by: Ibrahim Jarif <[email protected]>
manishrjain pushed a commit to outcaste-io/outserv that referenced this issue Jul 6, 2022
@damz
Rework DB.DropPrefix (#1381)
fe8546a 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue #1380). See
  hypermodeinc/badger#1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes #1381

Co-authored-by: Ibrahim Jarif <[email protected]>
mYmNeo pushed a commit to mYmNeo/badger that referenced this issue Jan 16, 2023
@damz @mYmNeo
Rework DB.DropPrefix (hypermodeinc#1381) (hypermodeinc#1514)
541d5b4 
Fixes three issues with the current implementation:

- It can generate compaction requests that break the invariant that bottom
  tables need to be consecutive (issue hypermodeinc#1380). See
  hypermodeinc#1380 (comment)
- It performs the same level compactions in increasing order of levels
  (starting from L0) which leads to old versions of keys for the prefix
  re-surfacing to active transactions.
- When you have to drop multiple prefixes, the API forces you to drop one
  prefix at a time and go through the whole expensive table rewriting multiple
  times.

Fixes hypermodeinc#1381

Co-authored-by: Ibrahim Jarif <[email protected]>
(cherry picked from commit e013bfd)

Co-authored-by: Damien Tournoud <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jarifibrahim jarifibrahim

Labels
kind/bug Something is broken. priority/P0 Critical issue that requires immediate attention. status/accepted We accept to investigate or work on it.
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Rework DB.DropPrefix damz/badger
2 participants
@damz @jarifibrahim