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

LSMKV: Store Map in always sorted manner #1832

Closed
5 tasks done
etiennedi opened this issue Feb 24, 2022 · 1 comment
Closed
5 tasks done

LSMKV: Store Map in always sorted manner #1832

etiennedi opened this issue Feb 24, 2022 · 1 comment
Labels
autoclosed Closed by the bot. We still want this, but it didn't quite make the latest prioritization round

Comments

@etiennedi
Copy link
Member

etiennedi commented Feb 24, 2022 •
edited

We are seeing during the implementation of #1798 that the current "random order map" implementation for SegmentStrategyMap (and same for Set) cannot handle the load during large inverted index lookups.

For example, using the wiki dataset (26M data points) with 1.7M doc ids matching it takes over 600ms just to remove tombstones which is not acceptable for such a query.

EDIT: originally the idea was to update this both for Map and Set. Due to time restrictions I've only implemented this for Map so far, which is what's used for text/string and therefore for BM25. A follow-up issue will be created to also implement this for Set, so that numerical filters, etc can also benefit from this.

Goals

  • The inner values of a set/map in the memtable must always be sorted (or alternatively must be sorted when the map/set is read and flushed) (Note that the outer keys are already sorted, as the memtable itself is sorted by definition. This only about the keys of a map or set within one "row" of the memtable)
  • a flushed map must be sorted
  • merging two maps during a compaction must keep the sorting (which is cheap to do if they are already sorted)
  • all decoders are changed to use a much simpler and faster decode, similar to the LSM cursors
  • doc ids are written with BigEndian byte order into the maps, this way the store sorting can also be used later on for application-level tasks (merging, etc.)

Breaking Changes

  • The change from little endian to big endian is breaking
  • The different way to store is breaking
  • Index versioning may be used to keep the old way for an old index, but use the new way for an index built with the new version.
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 [ci skip] WIP: sort at runtime, then merge
3441675 
This is meant as a first step to then later be able to change the
storage in a way that it is already sorted and we can remove the runtime
sort step
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 [ci skip] build a sorted map decoder
112f40a 
 This currently still breaks the implementation because of the
 duplicates in the memtable which needs to be fixed before this is able
 to pass tests
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 [skip ci] make map memtable sorted by default
3f6dc24 
 This required splitting it out to a separate map type. There are a few
 workarounds with regards to encoding/decoding in place right now to
 keep all the tests passing and everything working.

 Once the disk segments are sorted, too, these need to be removed
 together with the temporary runtime sorting.

 Still need to skip CI, because the implementaiton does not yet support
 cursors
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 use new map merger/decoder in map cursors
38feb9e 
This should finally make all existing tests green
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 remove redundant encoding/decoding in map cursor and list
f1e460b 
This also highlighted that the name mapDecoder no longer makes sense, as
it acts more like a map merger now.
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 keep order in map compaction
e00a005 
The redundant runtime merges are not yet removed. They will follow
shortly.
@etiennedi etiennedi changed the title LSMKV: Store Map/Set in always sorted manner LSMKV: Store Map in always sorted manner Feb 25, 2022
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 remove temporary map sorting on read
7fa82cb 
It is now no longer required since the segments themselves are stored
sorted.
@etiennedi etiennedi mentioned this issue Feb 25, 2022
Closed
etiennedi added a commit that referenced this issue Feb 25, 2022
@etiennedi
gh-1832 change byte order little endian to bigendian for map docIDs
9fdf3eb 
This still requires version checking as outlined in #1833
@etiennedi etiennedi mentioned this issue Mar 10, 2022
Closed
etiennedi added a commit that referenced this issue Mar 10, 2022
@etiennedi
gh-1852 sort memtable KV pairs on read
d3d4de5 
The memtable for Map is a binary tree so it's always sorted. However,
since this is type 'Map' each "row key" holds a map. This map was
unsorted in the past. In #1832 we introduced a change that made sure
this change would always be sorted ON DISK, i.e. in the segments. It was
very natural to also keep it sorted in the memtable, as we did not have
to do any sorting when flushing. However, the performance tests on
imports that make heavy use of the inverted index had a large
performance degradation after #1832. In a test I did locally the import
time went up by over 30%.

This fix goes back to keeping the KV pairs unsorted and making each
change an append only operation. This means it now needs to be sorted in
just two places (as opposed to on every single insertion):

1. On a read query. Those should be rare on memtable, since memtables
   are mostly meant for writing. The added overhead here (minimal) is
   not a problem since it was also there before #1832
2. When flushing. Flushing is an async operation and the small overhead
   of sorting each row's Map KVs is neglible.

This new implementation has the same import speed as prior to #1832
while keeping all the runtime benefits of having the KV pairs sorted on
disk.

closes #1852
@etiennedi etiennedi mentioned this issue Mar 10, 2022
Merged
@stale
Copy link

stale bot commented Apr 27, 2022

Thank you for your contribution to Weaviate. This issue has not received any activity in a while and has therefore been marked as stale. Stale issues will eventually be autoclosed. This does not mean that we are ruling out to work on this issue, but it most likely has not been prioritized high enough in the last months.
If you believe that this issue should remain open, please leave a short reply. This lets us know that the issue is not abandoned and acts as a reminder for our team to consider prioritizing this again.
Please also consider if you can make a contribution to help with the solution of this issue. If you are willing to contribute, but don't know where to start, please leave a quick message and we'll try to help you.
Thank you, The Weaviate Team

@stale stale bot added the autoclosed Closed by the bot. We still want this, but it didn't quite make the latest prioritization round label Apr 27, 2022
@stale stale bot closed this as completed Jun 12, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
autoclosed Closed by the bot. We still want this, but it didn't quite make the latest prioritization round
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@etiennedi