Skip to content

kv: replace memdb with a more memory efficient version#11807

Merged
sre-bot merged 12 commits intopingcap:masterfrom
bobotu:membuf
Aug 29, 2019
Merged

kv: replace memdb with a more memory efficient version#11807
sre-bot merged 12 commits intopingcap:masterfrom
bobotu:membuf

Conversation

@bobotu
Copy link
Contributor

@bobotu bobotu commented Aug 21, 2019

What problem does this PR solve?

The existing memdb from goleveldb use a contiguous memory to store data. It will put pressure on system memory when enlarging the underlying slice. After supporting large transaction, this problem will be more obvious.

What is changed and how it works?

Implementing a new skiplist with a block-based memory allocator, when enlarging the memdb simply allocate a new block instead of allocating a large amount of memory and copy all of the existing data into the new memory location.

The block size starts at an initial block size then doubled when each new block allocated until it reaches 128M.

Because there are some internal data structure optimization, the performance of Get and Put is slightly improved.

Here is the result of benchmarks in kv package:

opCnt = 100000

master

BenchmarkIsPoint-16                     300000000                4.84 ns/op            0 B/op          0 allocs/op
BenchmarkMemDbBufferSequential-16             20          61710345 ns/op        11979968 B/op          3 allocs/op
BenchmarkMemDbBufferRandom-16                 10         116388720 ns/op        13374355 B/op          7 allocs/op
BenchmarkMemDbIter-16                        300           5030566 ns/op             208 B/op          3 allocs/op
BenchmarkMemDbCreation-16                3000000               426 ns/op            4096 B/op          1 allocs/op

new

BenchmarkIsPoint-16                     300000000                4.81 ns/op            0 B/op          0 allocs/op
BenchmarkMemDbBufferSequential-16             30          60371850 ns/op         8947658 B/op          1 allocs/op
BenchmarkMemDbBufferRandom-16                 20         101129510 ns/op         6710522 B/op          1 allocs/op
BenchmarkMemDbIter-16                       1000           1220734 ns/op             128 B/op          1 allocs/op      
BenchmarkMemDbCreation-16                5000000               394 ns/op            4096 B/op          1 allocs/op

opCnt = 10000000

master

BenchmarkIsPoint-16                     300000000                4.82 ns/op            0 B/op          0 allocs/op
BenchmarkMemDbBufferSequential-16              1        7888385900 ns/op        3561011328 B/op       96 allocs/op
BenchmarkMemDbBufferRandom-16                  1        46474700000 ns/op       3561046784 B/op       98 allocs/op
BenchmarkMemDbIter-16                          2         504151600 ns/op             208 B/op          3 allocs/op
BenchmarkMemDbCreation-16                3000000               417 ns/op            4096 B/op          1 allocs/op

new

BenchmarkIsPoint-16                     300000000                4.82 ns/op            0 B/op          0 allocs/op
BenchmarkMemDbBufferSequential-16              1        7038679100 ns/op        536864032 B/op        39 allocs/op
BenchmarkMemDbBufferRandom-16                  1        36407376900 ns/op       536864032 B/op        39 allocs/op
BenchmarkMemDbIter-16                         10         122093460 ns/op             128 B/op          1 allocs/op
BenchmarkMemDbCreation-16                5000000               400 ns/op            4096 B/op          1 allocs/op

Check List

Tests

  • Unit test

Side effects

  • Increased code complexity

ngaut
ngaut reviewed Aug 21, 2019
View reviewed changes
ngaut
ngaut reviewed Aug 21, 2019
View reviewed changes
ngaut
ngaut reviewed Aug 21, 2019
View reviewed changes
@jackysp jackysp added the sig/transaction SIG:Transaction label Aug 21, 2019
@codecov
Copy link

codecov bot commented Aug 21, 2019 •
edited
Loading

Codecov Report

Merging #11807 into master will not change coverage.
The diff coverage is n/a.

@@             Coverage Diff             @@
##             master     #11807   +/-   ##
===========================================
  Coverage   81.2942%   81.2942%           
===========================================
  Files           441        441           
  Lines         94805      94805           
===========================================
  Hits          77071      77071           
  Misses        12257      12257           
  Partials       5477       5477

@jackysp
Copy link
Contributor

jackysp commented Aug 21, 2019

/run-all-tests

coocood
coocood reviewed Aug 21, 2019
View reviewed changes
kv/memdb/arena.go Outdated
}

func newArenaAddr(blockIdx int, blockOffset uint32) arenaAddr {
return arenaAddr(uint64(blockIdx+1)<<32 | uint64(blockOffset))
Copy link
Member

@coocood coocood Aug 21, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can we not +1 here?

Copy link
Contributor Author

@bobotu bobotu Aug 21, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

blockIdx == 0 && blockOffset == 0 means null.
Maybe we can place a nil pointer at blocks[0] to make blockIdx starts at 1?

coocood
coocood reviewed Aug 22, 2019
View reviewed changes
@coocood
Copy link
Member

coocood commented Aug 22, 2019

LGTM

coocood
coocood reviewed Aug 22, 2019
View reviewed changes
coocood
coocood reviewed Aug 22, 2019
View reviewed changes
tiancaiamao
tiancaiamao reviewed Aug 23, 2019
View reviewed changes
tiancaiamao
tiancaiamao reviewed Aug 23, 2019
View reviewed changes
@ngaut
Copy link
Member

ngaut commented Aug 26, 2019

/run-all-tests

@tiancaiamao
Copy link
Contributor

tiancaiamao commented Aug 28, 2019

LGTM

@tiancaiamao tiancaiamao added the status/LGT2 Indicates that a PR has LGTM 2. label Aug 28, 2019
@ngaut
Copy link
Member

ngaut commented Aug 28, 2019

/run-all-tests

@coocood coocood removed the status/LGT2 Indicates that a PR has LGTM 2. label Aug 29, 2019
@coocood coocood added status/LGT3 The PR has already had 3 LGTM. status/can-merge Indicates a PR has been approved by a committer. labels Aug 29, 2019
@sre-bot
Copy link
Contributor

sre-bot commented Aug 29, 2019

/run-all-tests

@sre-bot sre-bot merged commit a81f8e3 into pingcap:master Aug 29, 2019
@bobotu bobotu deleted the membuf branch August 29, 2019 03:42
@ekalinin ekalinin mentioned this pull request Sep 16, 2019
Closed
@bobotu bobotu mentioned this pull request Sep 25, 2019
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@coocood coocood coocood left review comments

@tiancaiamao tiancaiamao tiancaiamao left review comments

@ngaut ngaut ngaut approved these changes

Assignees

No one assigned

Labels

sig/transaction SIG:Transaction status/can-merge Indicates a PR has been approved by a committer. status/LGT3 The PR has already had 3 LGTM.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

@bobotu @jackysp @coocood @ngaut @tiancaiamao @sre-bot