Optimize in-memory index memory consumption#2338
Optimize in-memory index memory consumption#2338MichaelEischer wants to merge 2 commits intorestic:masterfrom
Conversation
Codecov Report
@@ Coverage Diff @@
## master #2338 +/- ##
==========================================
- Coverage 50.95% 46.93% -4.02%
==========================================
Files 178 178
Lines 14548 14562 +14
==========================================
- Hits 7413 6835 -578
- Misses 6069 6704 +635
+ Partials 1066 1023 -43
Continue to review full report at Codecov.
|
As go is able to fully inline and optimize function calls the code just becomes shorter and less duplicated.
Optimize for the default case where each blob is stored in exactly one blob. Duplicate blobs can only appear if a backup manages to upload a pack file but no corresponding index. In addition, the prune command will remove these duplicated blobs. Therefore, only a small fraction of blobs will ever be present in multiple packs. Previously the blob-handle-to-pack-id-map stored a slice pointing to a list of pack entries. The slice part which allows storing multiple entries is, however, rarely needed. This patch replaces it with a pointer to a single pack entry descriptor and a separate map to handle "overflows", that is multiple pack entries for a single blob handle. The simpler option of directly storing the entry descriptor in the map would require more memory in the common case: A map contains a lot of unused buckets which also consume memory. On amd64 a pointer to an entry is 8 bytes, a slice is 24 bytes in size, and a pack entry requires 48 bytes. Maps in Go have a max. load factor L of 6.5/8 which after growing will result in a load factor L of 3.25/8. With N being the number of map slots this yields the following memory usage: Previous: N*24 + N*L*48 Pointer: N*8 + N*L*48 Inline: N*48 The Pointer variant obviously needs less memory than Previous. Inline needs more memory than the Pointer variant if Inline - Pointer > 0 <=> N * (48 - 8 - L*48) > 0 <=> L < 5/6 As 5/6 > max. load factor 6.5/8 the Pointer variant always requires less memory. Note that shrinking a pack entry to 40 bytes would make the Inline variant preferable for L > 2/3. The Pointer variant still needs to allocate 48 bytes as the Go memory allocator has no pool for 40byte objects and therefore the next biggest, that is 48 bytes, will be used. L > 2/3 would cover approximately one third of the usual load factor range, such that the Pointer variant would still be preferable on average.
6be0d42 to
2327960
Compare
|
Thanks @MichaelEischer for this proposal! I agree that we need a solution to the memory consumption problem and you correctly have identified the index data structure as the core point to improve 👍 About your solution I'm not confident that 10-15% improvement is enough. I like the idea of not storing duplicate information of blobs being in the index more than once (and this situation should anyway be cleaned by the next But I think there are even better solutions as the PackID for packs containing many blobs is still multiple times saved in memory and there is a notable overhead of all the maps which I think can be removed without loosing too much performance. Please have a look at Maybe some of the restic maintainers can give directions where to work on... |
|
The @aawsome : Yes, I know that 10-15% improvement is not that much. The PackIDs can definitely be stored separately which should improve memory usage by quite a lot. However, as the pull request is already several months old I can't remember why I've ignored that optimization. |
|
Closing as this pull request is superseded by either https://github.com/aawsome/restic/tree/refactor-index or https://github.com/MichaelEischer/restic/tree/opt-hash-idx |
|
@MichaelEischer are there PRs for those to follow? |
What is the purpose of this change? What does it change?
Slightly reduce the memory usage of the in-memory index that is used by most restic commands. The memory usage should be 10-15% lower than before. This is achieved by optimizing for the usual situation where each blob is contained in a single pack file.
The pull request still needs tests which trigger the code paths with multiple packs. I'm not sure whether there are currently any tests that explicitly generate blobs which are stored in multiple packs.
Was the change discussed in an issue or in the forum before?
The problem of high memory usage shows up in several issues #2284 , #1988 , #1723 . However, the approach of this pull request was not yet discussed in an issue. The underlying scalability issue is not tackled by this pull request.
Checklist
changelog/unreleased/that describes the changes for our users (template here)gofmton the code in all commits