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

Release in-memory log space based on entries size #71

Open
pav-kv opened this issue Jun 2, 2023 · 8 comments · May be fixed by #96
Open

Release in-memory log space based on entries size #71

pav-kv opened this issue Jun 2, 2023 · 8 comments · May be fixed by #96
Assignees
@Aditya-Sood
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@pav-kv
Copy link
Contributor

pav-kv commented Jun 2, 2023 •
edited

When entries exit the unstable log structure

raft/log_unstable.go

Line 156 in 3e6cb62

u.entries = u.entries[num:]

it shrinks itself based on the entries slice length and cap:

raft/log_unstable.go

Lines 162 to 179 in 3e6cb62

// shrinkEntriesArray discards the underlying array used by the entries slice
// if most of it isn't being used. This avoids holding references to a bunch of
// potentially large entries that aren't needed anymore. Simply clearing the
// entries wouldn't be safe because clients might still be using them.
func (u *unstable) shrinkEntriesArray() {
// We replace the array if we're using less than half of the space in
// it. This number is fairly arbitrary, chosen as an attempt to balance
// memory usage vs number of allocations. It could probably be improved
// with some focused tuning.
const lenMultiple = 2
if len(u.entries) == 0 {
u.entries = nil
} else if len(u.entries)*lenMultiple < cap(u.entries) {
newEntries := make([]pb.Entry, len(u.entries))
copy(newEntries, u.entries)
u.entries = newEntries
}
}

Firstly, the len(u.entries)*lenMultiple < cap(u.entries) does not necessarily do a right thing. After shifting the slice start in u.entries = u.entries[num:], the first num entries "disappear" from len and cap of this slice: https://go.dev/play/p/ao1xaL0Edla.

So it's possible that len >= cap/2 all the time, even though only a small portion of the backing slice is used. We should take the cap of the entire backing slice into account instead.

Secondly, this heuristic only takes len/cap of the slice into consideration, but not the size of the entries referenced by it. It could be beneficial to, in addition, shrink the slice if the sum size of the "garbage" entries is more than a half. This would keep the overall memory consumption more controlled. Doing so would require maintaining a running sum of entry sizes in the unstable struct (which we do anyway in other places for rate limiting purposes).

The same heuristic could be applied in MemoryStorage.Compact method to smooth out the allocation/copying cost of log truncations. Frequent truncations may incur a quadratic cost here, while the heuristic allows capping it at O(N).
@pav-kv pav-kv added enhancement New feature or request good first issue Good for newcomers labels Jun 2, 2023
@pav-kv
Copy link
Contributor Author

pav-kv commented Jun 2, 2023

Alternatively, prove that the current strategy in unstable can't result in holding more memory than, say, 2x of a configured max.

@pav-kv
Copy link
Contributor Author

pav-kv commented Jun 2, 2023 •
edited

But it doesn't look like we're safe as is. Say, the max size is 64 MB. Consider the following sequence of appends / truncations (numbers are entry sizes in MB):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 8 8 8 8 8 8 16 16 32
<-------------------------------> ....................................
                                  <-------------> ....................
                                                  <---------> ........
                                                              <---> ..
                                                                    <>

First, 17 entries of size 2MB are appended, total is 34 MB (below the limit). The slice len == 17, cap == 32.

Then, a truncate 2MB, and a sequence of 8 (append 4MB, truncate 2 x 2MB) follows. During this sequence, len * 2 >= cap holds, so we're not reallocating the array. In the end slice len == 8, cap == 16.

Then, a sequence of 4 (append 8MB, truncate 2 x 4MB) follows. Same thing.

Eventually, we fill up the cap of the array, by adding a final 32MB entry.

The total memory usage of this slice by the time we reallocate is ~ 32MB * 5. More generally, an example can be constructed with O(B log B) bytes usage, for a configured max size B. We would like to reduce this to O(B), something like 2 * B.

@CaojiamingAlan
Copy link
Contributor

I am taking a look at this issue.

However, from what I've learned, I don't think there is a way to get the length of entire backing array of a slice from the slice itself. That means we will also have to maintain a backingArrayLength in the unstable struct, and update manually it everywhere we assign a value to entries.

e.g. if we assign entries = nil then we set backingArrayLength = 0, and if we set u.entries = append(u.entries, ents...), then we will have to check if the array is reallocated; if it is, then backingArrayLength = cap(u.entries), else we leave it unchanged.

We need to do the same thing to calculate the accurate sum size of the "garbage" entries.

I wonder if I am correct and if this approach is expected.

BTW, there's a typo: there are 6 * 8MB entries in the figure. I think there should be only 4 of them.

@CaojiamingAlan
Copy link
Contributor

I didn't see #69. I think this issue would be easy to solve if we get #69 done.

@Aditya-Sood
Copy link

hi @pavelkalinnikov @CaojiamingAlan
is this issue still open for contribution?

@pav-kv
Copy link
Contributor Author

pav-kv commented Aug 11, 2023 •
edited

I wonder if I am correct and if this approach is expected.

@CaojiamingAlan Yes, I think you're correct, some kind of backingArrayLength / size tracking is needed to workaround. The backingArrayLength doesn't have to be baked into unstable type, you could think of the backing array as a separate "deque" kind of data structure and implement/test it separately to not overload unstable with the details.

is this issue still open for contribution?

@Aditya-Sood Still open, would you like to take a stab at it? @CaojiamingAlan Are you working on this?

@Aditya-Sood
Copy link

@pavelkalinnikov yes I'd like to try

if @CaojiamingAlan is unable to reply by Sunday I'll get started

@Aditya-Sood
Copy link

hi @pavelkalinnikov, I'll get started on this
could you assign the issue to me?

@Aditya-Sood Aditya-Sood linked a pull request Aug 18, 2023 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Aditya-Sood Aditya-Sood

Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Optimise memory deallocation for stable log entries Aditya-Sood/etcd-io-raft
3 participants
@pav-kv @Aditya-Sood @CaojiamingAlan