feat: Avoid loading all notes in memory

[douglaz]

Stream data from DB in descending denomination order then only uses the required notes. Also calculates and uses a summary of the notes when some metrics like total amount are required.

Although this started as solution to https://github.com/fedimint/fedimint/issues/82 and may improve the speed of select_notes, the focus is mostly on reducing memory usage.

[codecov[bot]]

Codecov Report

Patch coverage: 84.26% and project coverage change: +0.52 :tada:

Comparison is base (3c15cba) 59.22% compared to head (8bdf528) 59.75%.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #2183 +/- ## ========================================== + Coverage 59.22% 59.75% +0.52% ========================================== Files 152 153 +1 Lines 31759 32213 +454 ========================================== + Hits 18810 19248 +438 - Misses 12949 12965 +16 ``` | [Impacted Files](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint) | Coverage Δ | | |---|---|---| | [fedimint-cli/src/lib.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY2xpL3NyYy9saWIucnM=) | `5.65% <0.00%> (+0.04%)` | :arrow_up: | | [gateway/ln-gateway/src/actor.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-Z2F0ZXdheS9sbi1nYXRld2F5L3NyYy9hY3Rvci5ycw==) | `46.19% <0.00%> (+1.35%)` | :arrow_up: | | [modules/fedimint-mint-client/src/lib.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-bW9kdWxlcy9mZWRpbWludC1taW50LWNsaWVudC9zcmMvbGliLnJz) | `0.51% <0.00%> (-0.02%)` | :arrow_down: | | [fedimint-core/src/db/mod.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY29yZS9zcmMvZGIvbW9kLnJz) | `84.97% <55.20%> (-2.63%)` | :arrow_down: | | [fedimint-rocksdb/src/lib.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtcm9ja3NkYi9zcmMvbGliLnJz) | `81.46% <90.96%> (+9.96%)` | :arrow_up: | | [fedimint-client-legacy/src/mint/mod.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY2xpZW50LWxlZ2FjeS9zcmMvbWludC9tb2QucnM=) | `88.07% <93.13%> (+2.06%)` | :arrow_up: | | [fedimint-client-legacy/src/lib.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY2xpZW50LWxlZ2FjeS9zcmMvbGliLnJz) | `78.71% <100.00%> (+0.56%)` | :arrow_up: | | [fedimint-core/src/db/mem\_impl.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY29yZS9zcmMvZGIvbWVtX2ltcGwucnM=) | `90.40% <100.00%> (+1.01%)` | :arrow_up: | | [fedimint-core/src/db/notifications.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY29yZS9zcmMvZGIvbm90aWZpY2F0aW9ucy5ycw==) | `95.39% <100.00%> (+0.25%)` | :arrow_up: | | [fedimint-core/src/tiered.rs](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint#diff-ZmVkaW1pbnQtY29yZS9zcmMvdGllcmVkLnJz) | `91.66% <100.00%> (+0.30%)` | :arrow_up: | | ... and [2 more](https://codecov.io/gh/fedimint/fedimint/pull/2183?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint) | | ... and [22 files with indirect coverage changes](https://codecov.io/gh/fedimint/fedimint/pull/2183/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint) Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=fedimint)

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

[dpc]

Oooohhh... I was confused. So the algorithm is going from largest to smallest ...

But doesn't have the opposite problem? If you need to make a odd-value payment ... you're going to need to fetch almost all notes anyway, no? Because you need that 1-value note, that will come last, no matter what you do...

And then 3 out or 4 times you need all but 2 smallest tiers...

These exponential odds seem to conspire against us!

[dpc]

It seems to me that instead of streaming notes, if performance is the goal, it would be best to just put an in-memory write-through cache in front of that notes in database thing, and always have it memory after initial load. :shrug:

[douglaz]

I had plenty of comments (one of them being the actual streaming of notes not working like streaming and fetching all notes anyway), but putting them aside, on the higher level...

What are we optimize for exactly here, and should we get some benchmarks?

Average/max memory usage and average I/O operations. Benchmarks would be nice, but I guess tricky to get?

I assume that if we are going to stream the notes, then there's going to be some extra overhead of "give me more".

This may or may not be not true. But even if it's true, note that the new code won't add more overhead for a rocksdb database. It will just read less of the existing iterator.

When fetching all notes at once, I'd assume sqlite does everything once, returns it and that's about it. With an iterator (depending on how it is actually implement it) it could be: "give me one; here it goes; give me another one; here it goes; and another one please; there you go...". Each back and forth by necessity must have some overhead. Maybe negligible, maybe amortized, but still some.

This is a good point. Some notes: 1) Both the new code and the old code will sort the data on sqlite (But you could argue there is a possible optimization where no sorting could be done) 2) Both the old code and the new code won't really stream on sqlite (I didn't change the fetchall) 3) Given the point above you can see I treated sqlite as a second citizen database. The whole idea was focused on rocksdb-like databases (where data is naturally sorted by key).

So this implementation doesn't really make anything better for databases like sqlite, but it also doesn't make it worse performance-wise.

With fetching all, we obviously waste (briefly, but still) some memory (allocation), and we the db needs to overfetch some data.

But with iterator we might actually be doing many more IO operations scattered over longer time. Total load on the system might be higher, especially if typically we need to fetch .. donno... 75% of all notes anyway (given that big notes are ... well... big, so there need to be fewer of them to compose a certain amount, one would expect).

Look at the implementation of fetch_all, it's iterators/streams all way down. So it won't require more IO operations.

If you have 1, 2, 4, 8 notes, you have 15 msats total, but if you make payments in 4-7 range you usually need to fetch all but one note anyway. So I expect, that even while having a decent balance, and making smallish payments, still a good chunk of notes will need to be fetched?

So I think it's fair to ask - is it worth it? The number of notes is not going to be sky high. I suspect 50-150 range, because:

pub const DEFAULT_MAX_NOTES_PER_DENOMINATION: u16 = 3;

and we power-of-2 tiers by default, so we can't be going all that far w.r.t number of tier.

If the number of notes is and will always be small then it's fair to say: don't bother.

But is this really the case? So there is not such thing as a "big wallet"?

[douglaz]

It seems to me that instead of streaming notes, if performance is the goal, it would be best to just put an in-memory write-through cache in front of that notes in database thing, and always have it memory after initial load. shrug

Although the new code have the same or better performance (as far as it can be determined by simple inspection), I can't say it's the goal. See the comment above. But I agree, putting everything in memory will probably be faster if you don't bother about memory consumption.

[m1sterc001guy]

Given the point above you can see I treated sqlite as a second citizen database. The whole idea was focused on rocksdb-like databases (where data is naturally sorted by key).

The data in Sqlite is also sorted by key. We create a index on the key and the hex representation of the key when the database is created.

Both the old code and the new code won't really stream on sqlite (I didn't change the fetchall)

Looks like the main limitation is converting from sqlite's row structure to a (key, value) pair. As you pointed out fetch_all is already using streams.

Sqlite definitely needs some love as its not tested much right now. With the new client I hope Sqlite will be easier to support so any improvement in that direction is appreciated :)

[jkitman]

@douglaz Currently we use a greedy note selection algorithm, but in the future we may want to choose notes that have a large enough anonymity set. How would this approach change?

[douglaz]

@douglaz Currently we use a greedy note selection algorithm, but in the future we may want to choose notes that have a large enough anonymity set. How would this approach change?

Just to be clear, this PR opens up possibilities, it doesn't restrict you in any way. More specifically: 1) It formalizes that notes can be streamed up from DB sorted by denomination amount. This was already the case but it was actually broken due to small implementation details. 2) It formalizes a TieredSummary when you just need to know how many notes of each denomination you have. This structure was mostly there (without this fancy name), but now the code calculates it without loading the full notes on memory. A further optimization would be, as suggested by @elsirion elsewhere, to skip or delay decoding the full SpendableNote on this and other cases. 3) Uses 1) to implement the greedy selection algorithm by descending denomination amount, reading only a subset of the notes in many cases (reducing IO) and keeping the minimal number of notes on memory (reducing memory usage)

Now if you want to implement a algorithm focused on common notes you can use the idea of 1) and 3) but perhaps reading in ascending denomination order. Then you have at least two options: A) If you have an up to date TieredSummary, you iterate over the stream keeping exactly what you need, stopping as soon as you are done B) Without a TieredSummary, the accumulator keeps all of read lower denomination notes, stopping as soon as you are done

And of course you can do: C) Same as B), but always reading until the end, without stopping earlier

Note that the current code on master implements C focusing on high denomination notes. This PR still keeps that possible but, besides implementing 3), it also makes it easier to implement A) and B)

(Other than all that, if you have a TieredSummary on hand, there are other possibilities involving more complex DB queries, but I won't detail it now)

[jkitman]

@douglaz Thanks for the detailed explanation, glad we have that case covered.

[douglaz]

Rebased

[douglaz]

Addressed code review

[douglaz]

Rebased

[douglaz]

Addressed code review