rpc: Optimize serialization disk space of dumptxoutset

aureleoules commented at 0:57 am on September 8, 2022: member

This is an attempt to implement #25675.

I was able to reduce the serialized utxo set from 5GB to 4.1GB on mainnet.

Closes #25675.

DrahtBot added the label RPC/REST/ZMQ on Sep 8, 2022

aureleoules marked this as a draft on Sep 8, 2022

aureleoules force-pushed on Sep 8, 2022

aureleoules marked this as ready for review on Sep 8, 2022

aureleoules force-pushed on Sep 8, 2022

DrahtBot commented at 5:13 pm on September 8, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	jamesob, pablomartin4btc, jaonoctus, Sjors
Stale ACK	TheCharlatan

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29307 (util: check for errors after close and read in AutoFile by vasild)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

amovfx commented at 1:23 am on September 9, 2022: none

I don’t have the skill set to approve this code but I can test and verify. I ran this on testnet and can confirm a smaller output file.

without: { "coins_written": 27908372, "base_hash": "0000000000000008f07ed39d6d03c19ee7346bc15b6a516cdda8402b6244b828", "base_height": 2345886, "path": "/Users/{$User}/Library/Application Support/Bitcoin/testnet3/./txoutset.txt", "txoutset_hash": "026617308d218e57fb43f02baa644134f5000594a1eea06b02cc9d02959d4d9b", "nchaintx": 63601314 } Size of 3 473 536

With this optimization: { "coins_written": 27908372, "base_hash": "0000000000000008f07ed39d6d03c19ee7346bc15b6a516cdda8402b6244b828", "base_height": 2345886, "path": "/Users/${User}/Library/Application Support/Bitcoin/testnet3/txoutset.optimized.txt", "txoutset_hash": "026617308d218e57fb43f02baa644134f5000594a1eea06b02cc9d02959d4d9b", "nchaintx": 63601314 } Size of 2 457 728

Looks like a win to me.

luke-jr commented at 11:36 pm on September 10, 2022: member

Not sure it’s worth it to save 20%. Presumably generic compressors could do better anyway?

aureleoules commented at 7:26 am on September 12, 2022: member

Not sure it’s worth it to save 20%. Presumably generic compressors could do better anyway?

Yes I agree but at least with this implementation the utxo set is still readable as is and doesn’t need decompression.

TheCharlatan commented at 1:53 pm on March 2, 2023: contributor

The main downside of this implementation is that the entire UTXO set must be loaded in RAM (in mapCoins) before being written to disk. So running dumptxoutset will consome a lot of RAM on mainnet since the utxo set is large. Not sure how to improve this.

The keys in leveldb are guaranteed to be lexicographically sorted. You just need to cache the last txid and flush the txid and outpoint tuples once the next one is reached in the database iterator. I pushed a dirty proof of concept here and it produced the same output file as your current implementation.

Otherwise Concept ACK. For a file that might be lugged over a network or other data carrier this space improvement is nice. Users can still apply their own compression on top of it. I also like that this provides additional structure to the data.

RCasatta commented at 4:17 pm on March 16, 2023: none

Yeah as I specified in the issue and as @TheCharlatan wrote more ram shouldn’t be needed because txid are iterated sorted from leveldb.

I was also wondering why the bitcoin-cli savetxoutset API (same goes for savemempool) requires to specify a filename instead of writing to stdout that would offer better composition while maintaining the possibility to write to file with >utxo.bin

aureleoules force-pushed on Apr 26, 2023

in src/rpc/blockchain.cpp:2688 in 04887de4f4 outdated

2686         if (iter % 5000 == 0) node.rpc_interruption_point();
2687         ++iter;
2688         if (pcursor->GetKey(key) && pcursor->GetValue(coin)) {
2689-            afile << key;
2690-            afile << coin;
2691+            std::cout << key.ToString() << "\n";

TheCharlatan commented at 0:33 am on April 27, 2023:

This needs to be dropped.

in src/rpc/blockchain.cpp:2690 in 04887de4f4 outdated

2688         if (pcursor->GetKey(key) && pcursor->GetValue(coin)) {
2689-            afile << key;
2690-            afile << coin;
2691+            std::cout << key.ToString() << "\n";
2692+            if (key.hash == last_hash) {
2693+                coins.push_back(std::make_pair(key.n, coin));

TheCharlatan commented at 6:58 pm on April 28, 2023:

Using explicit make_pair can be avoided by directly calling emplace_back instead (same for further below).

TheCharlatan commented at 8:26 am on April 29, 2023: contributor

Re #26045 (comment)

I was also wondering why the bitcoin-cli savetxoutset API (same goes for savemempool) requires to specify a filename instead of writing to stdout that would offer better composition while maintaining the possibility to write to file with >utxo.bin

Writing to stdout would mean that the data would have to be carried over the rpc connection, right?

in src/rpc/blockchain.cpp:2692 in 04887de4f4 outdated

2690-            afile << coin;
2691+            std::cout << key.ToString() << "\n";
2692+            if (key.hash == last_hash) {
2693+                coins.push_back(std::make_pair(key.n, coin));
2694+            } else {
2695+                afile << last_hash;

TheCharlatan commented at 10:12 pm on April 29, 2023:

The file writing would be more DRY if it were declared as a lambda and then called here and below, e.g. like:

0 auto write_coins_to_file = [&](AutoFile& afile, const uint256& last_hash, const std::vector<std::pair<uint32_t, Coin>>& coins) {
1    afile << last_hash;
2    afile << static_cast<uint16_t>(coins.size());
3    for (auto [vout, coin] : coins) {
4        afile << vout;
5        afile << coin;
6    }
7};

TheCharlatan changes_requested

TheCharlatan commented at 11:11 pm on April 29, 2023: contributor

Thank you for picking this up again.

These are just patches for fixing up my initial code, I also put the entire diff here. The rest looks good to me, I tested dumptxoutset extensively on mainnet. The runtime performance of this branch is very similar to the base.

The following can be ignored in the context of this PR, but I still want to take note:

During review I noticed that the execution time of the command greatly relies on getting the utxo stats (getting the stats and writing to the file each take about 450s on my m.2 machine). I don’t follow why these stats need to be collected by iterating through the entire set again, is there no better way to prepend the meta data? A count of the written entries as well as a hash of them can be provided by the same iteration loop that is used to write the file. Further, the m_coins_count in the SnapshotMetadata is populated with tip->nChainTx, which I am not sure always corresponds to the actual number of coins written, but is used to read that exact number of coins from the file when loading the snapshot.

RCasatta commented at 1:33 pm on April 30, 2023: none

Writing to stdout would mean that the data would have to be carried over the rpc connection, right?

Yes, would that be a problem?

sipa commented at 1:37 pm on April 30, 2023: member

There is no way we can currently send gigabytes of data as an RPC response; both the server and client likely buffer the result and would OOM.

aureleoules force-pushed on Apr 30, 2023

aureleoules commented at 2:43 pm on April 30, 2023: member

Thanks for the patch @TheCharlatan, I applied it.

TheCharlatan commented at 4:24 pm on April 30, 2023: contributor

I ran some more numbers, dumping a mainnet snapshot on height 787535:

Filename	Size (bytes)
this_branch.dat	4'697'836'541
this_branch.tar.xz	3'899'452'268
master.dat	5'718'308'597
master.tar.xz	3'925'608'176

So even in the compressed form the encoding saves some megabytes.

TheCharlatan commented at 7:27 am on May 1, 2023: contributor

ACK 7acfc2a221237877aa3522266cac6c326ae7fe8e

Since we are changing the format of dumptxoutset anyway here in a non backwards compatible fashion, I’d like to suggest moving the metadata to the end of the file. This would take care of the double iteration described in #26045#pullrequestreview-1403015467. In my eyes, this does not significantly hurt the integrity of the file. If an exception occurs during writing, only the temporary file remains. Other common file formats also embed metadata at the end.

brenoepics approved

DrahtBot added the label Needs rebase on Jul 6, 2023

aureleoules force-pushed on Sep 24, 2023

DrahtBot removed the label Needs rebase on Sep 24, 2023

aureleoules commented at 9:35 am on September 24, 2023: member

Rebased

jamesob commented at 11:22 am on September 24, 2023: member

Concept ACK

Sjors commented at 4:28 pm on September 28, 2023: member

I cherry-picked 4250824efbe721a8b36f1b05c4280d144318872c on master @ 6619d6a8dca5a4d8e664a76526ac6bef3eb17831 to generate snapshots for signet and mainnet. The txoutset_hash is unchanged.

I then cherry-picked 4250824efbe721a8b36f1b05c4280d144318872c on #28516 (which leads to a small conflict) to load the snapshots.

Signet:

0{
1  "coins_written": 1278002,
2  "base_hash": "0000003ca3c99aff040f2563c2ad8f8ec88bd0fd6b8f0895cfaf1ef90353a62c",
3  "base_height": 160000,
4  "txoutset_hash": "5225141cb62dee63ab3be95f9b03d60801f264010b1816d4bd00618b2736e7be",
5  "nchaintx": 2289496
6}

The snapshot is actually slightly bigger:

091425233 utxo-signet-160000.dat
192892387 utxo-signet-160000-smaller.dat

Mainnet:

0{
1  "coins_written": 111535121,
2  "base_hash": "00000000000000000002a7c4c1e48d76c5a37902165a270156b7a8d72728a054",
3  "base_height": 800000,
4  "txoutset_hash": "7d69b87512db3d13b9758ea32b93ce468d18cf7456fb5d250c9e1bed9339e4d2",
5  "nchaintx": 868965226
6}

The snapshot made by this PR is a gigabyte smaller.

07323553927 utxo-800000.dat
16234254939 utxo-800000-smaller.dat

I succeeded in loading the signet snapshot and finishing background sync IBD. I also managed to load the mainnet snapshot, waited for it to reach the tip. I didn’t wait for the for full background sync.

Haven’t reviewed the code yet.

Given the slight conflict with the main assume-utxo PR - and that we don’t want to make @jamesob life ever harder - I suggest rebasing on top of it and marking this draft until that’s merged.

As an aside (this just tests the main PR), loading the block 800,000 snapshot and saving its chainstate to disk takes 10 minutes on my machine (AMD Ryzen 9 7950X, SSD drive for the main datadir, -dbcache set to 16GiB). During that time the background IBD reaches november 2011.

Once it starts using the snapshot, it reaches the almost-tip in 12 minutes (-blocksdir points to a spinning disk, downloaded from 1 Gbit internet, cache peaks at 3584 MiB). It then saves the new chainstate, resizes the caches which trigger a flush, but less than 2 minutes later we’re at the real tip! And then the background sync takes over.

Cool stuff.

DrahtBot added the label Needs rebase on Oct 2, 2023

aureleoules force-pushed on Oct 2, 2023

DrahtBot removed the label Needs rebase on Oct 3, 2023

DrahtBot added the label CI failed on Oct 3, 2023

Sjors commented at 9:17 am on October 3, 2023: member

#27596 was just merged, so this PR will be easier to test if you rebase.

DrahtBot removed the label CI failed on Oct 4, 2023

DrahtBot added the label Needs rebase on Oct 23, 2023

in src/rpc/blockchain.cpp:2697 in 9a1717e790 outdated

2701+            } else {
2702+                write_coins_to_file(afile, last_hash, coins);
2703+                last_hash = key.hash;
2704+                coins.clear();
2705+                coins.emplace_back(key.n, coin);
2706+            }

pablomartin4btc commented at 3:08 pm on October 25, 2023:

0            if (key.hash != last_hash) {
1                write_coins_to_file(afile, last_hash, coins);
2                last_hash = key.hash;
3                coins.clear();
4            }
5            coins.emplace_back(key.n, coin);

aureleoules commented at 10:19 am on December 18, 2023:

Fixed thanks

pablomartin4btc commented at 3:08 pm on October 25, 2023: member

Concept ACK

jaonoctus approved

jaonoctus commented at 6:33 am on December 18, 2023: none

Concept ACK

Tested on testnet and regtest, works as expected

Sjors commented at 9:50 am on December 18, 2023: member

@aureleoules wen rebase? :-)

aureleoules force-pushed on Dec 18, 2023

aureleoules commented at 10:20 am on December 18, 2023: member

@aureleoules wen rebase? :-)

🫡

aureleoules marked this as a draft on Dec 18, 2023

aureleoules force-pushed on Dec 18, 2023

DrahtBot added the label CI failed on Dec 18, 2023

DrahtBot removed the label Needs rebase on Dec 18, 2023

aureleoules commented at 11:01 am on December 18, 2023: member

Rebased

I had to slightly change the tests in feature_assumeutxo.py because I changed the encoding format of the dump. I added 2 bytes to the offset because of the new size (2 bytes) field.

aureleoules marked this as ready for review on Dec 18, 2023

DrahtBot removed the label CI failed on Dec 18, 2023

Sjors commented at 1:11 pm on December 22, 2023: member

Did some testing with f5d2014e96240aab9540aaba0a792710aa7725e7.

Using contrib/devtools/utxo_snapshot.sh on signet I get the same txoutset_hash. The resulting is also identical to what I generated in earlier, see #26045 (comment). I was then able to load the loadshot and sync the chain (to the tip in about a minute, wonderful) and complete the background sync.

I also generated a mainnet snapshot which was also identical to what I found in the last test, so I have not tried loading again.

Will review the code later.

DrahtBot added the label CI failed on Jan 14, 2024

DrahtBot added the label Needs rebase on Feb 5, 2024

rpc: Optimize serialization disk space of dumptxoutset

Co-authored-by: TheCharlatan <seb.kung@gmail.com>

4e194640a7

aureleoules force-pushed on Feb 5, 2024

aureleoules commented at 4:13 pm on February 5, 2024: member

Rebased. I had to change the offset again in feature_assumeutxo.py.

DrahtBot removed the label Needs rebase on Feb 5, 2024

DrahtBot removed the label CI failed on Feb 5, 2024

in test/functional/feature_assumeutxo.py:79 in 4e194640a7

75@@ -76,6 +76,7 @@ def test_invalid_snapshot_scenarios(self, valid_snapshot_path):
76         bad_snapshot_path = valid_snapshot_path + '.mod'
77 
78         def expected_error(log_msg="", rpc_details=""):
79+            print(log_msg)

Sjors commented at 10:43 am on February 22, 2024:

Don’t forget to drop this.

fjahr commented at 4:34 pm on March 10, 2024:

Should be addressed in #29612

in src/rpc/blockchain.cpp:2680 in 4e194640a7

2676-    unsigned int iter{0};
2677+    std::vector<std::pair<uint32_t, Coin>> coins;
2678+
2679+    auto write_coins_to_file = [&](AutoFile& afile, const uint256& last_hash, const std::vector<std::pair<uint32_t, Coin>>& coins) {
2680+        afile << last_hash;
2681+        afile << static_cast<uint16_t>(coins.size());

Sjors commented at 10:04 am on February 23, 2024:

4e194640a74ff784212e615c8e88c375cdfed039: In primitives/transaction.h we serialize std::vector<CTxOut> vout with a simple s << tx.vout; without any reference to the size of the vector. Not sure if any magic is happening there under the hood that I missed.

Also, uint16_t implies a limit of 65,536 outputs per transaction. I don’t think that’s a consensus rule?

fjahr commented at 11:17 pm on March 4, 2024:

Yeah, I think the magic happens here: https://github.com/bitcoin/bitcoin/blob/master/src/serialize.h#L674

However, we can’t use that because we are not looking at a full transaction but rather the outpoints that are still left in the UTXO set. But we basically mimic that behavior here.

fjahr commented at 11:38 pm on March 4, 2024:

On the 65,536: I guess the blocksize solves this for us for now I think it makes sense to use VARINT/CompactSize here

Sjors commented at 10:08 am on March 7, 2024:

A transaction with 65,537 OP_RETURN outputs should fit in a block.

If I start with P2TR outputs with this calculator, that’s 2,818,159 vbyte. https://bitcoinops.org/en/tools/calc-size/

And then subtract 32 bytes per output: 2,818,159 - 65537 * 32 = 720,975 vbyte

cc @murchandamus can you add OP_RETURN to the dropdown? :-)

In any case it seems unsafe to rely on the block size here.

fjahr commented at 4:54 pm on March 10, 2024:

Hm, but OP_RETURNs are not included in the UTXO set and we are serializing the UTXO set here, so I think this could still not happen like this. But I think you are right there are non-standard cases imaginable that make this possible, like just sending to OP_TRUE for example. So we should still make this robust.

Anyway, I am using CompactSize now in #29612 :)

in src/validation.cpp:5410 in 4e194640a7

5427+            coins_file >> txid;
5428+            uint16_t size{0};
5429+            coins_file >> size;
5430+
5431+            if(size > coins_left) {
5432+                LogPrintf("[snapshot] mismatch in coins count in snapshot metadata and actual snapshot data\n");

Sjors commented at 10:31 am on February 23, 2024:

In the context of my remark above about maybe not serializing size: in that case this check would have to happen after the batch of coins is loaded, which seems fine.

fjahr commented at 4:35 pm on March 10, 2024:

@Sjors I couldn’t follow this comment here. If this is still relevant, could you please clarify in #29612? Thanks!

Sjors commented at 10:12 am on March 11, 2024:

Nothing to do here, since we do have serialize size, as you explained: #26045 (review)

in src/validation.cpp:5419 in 4e194640a7

5437+            for (int i = 0; i < size; i++) {
5438+                COutPoint outpoint;
5439+                Coin coin;
5440+                coins_file >> outpoint.n;
5441+                coins_file >> coin;
5442+                outpoint.hash = txid;

Sjors commented at 10:36 am on February 23, 2024:

4e194640a74ff784212e615c8e88c375cdfed039 nit: maybe move this above where you set outpoint.n

fjahr commented at 4:33 pm on March 10, 2024:

Should be addressed in #29612

in src/validation.cpp:5468 in 4e194640a7

5511+                        FlushSnapshotToDisk(coins_cache, /*snapshot_loaded=*/false);
5512+                    }
5513+                }
5514             }
5515+        } catch (const std::ios_base::failure&) {
5516+            LogPrintf("[snapshot] bad snapshot format or truncated snapshot after deserializing %d coins\n",

Sjors commented at 10:38 am on February 23, 2024:

Unrelated, but why doesn’t this use coins_processed?

fjahr commented at 4:33 pm on March 10, 2024:

Should be addressed in #29612

in src/validation.cpp:5483 in 4e194640a7

5479@@ -5468,6 +5480,7 @@ bool ChainstateManager::PopulateAndValidateSnapshot(
5480 
5481     bool out_of_coins{false};
5482     try {
5483+        COutPoint outpoint;

Sjors commented at 10:46 am on February 23, 2024:

I think this should be:

0Txid txid;
1coins_file >> txid;

The current code might accidentally work because a COutPoint is a Txid followed by a single number (albeit uint32_t instead of uint16_t).

fjahr commented at 4:34 pm on March 10, 2024:

Should be addressed in #29612

Sjors commented at 10:54 am on February 23, 2024: member

Concept ACK. Found a few issues during code review, see inline. @TheCharlatan wrote:

The keys in leveldb are guaranteed to be lexicographically sorted. You just need to cache the last txid and flush the txid and outpoint tuples once the next one is reached in the database iterator.

I would be good to document in the code that we rely on this behavior (maybe in the header file, so someone who wants to replace leveldb is reminded). @luke-jr & @aureleoules wrote:

Not sure it’s worth it to save 20%. Presumably generic compressors could do better anyway?

Yes I agree but at least with this implementation the utxo set is still readable as is and doesn’t need decompression.

We might also at some point want to xor the file - for the same reason as #28207. That would make compression with external tools impossible.

in src/rpc/blockchain.cpp:2673 in 4e194640a7

2667@@ -2668,21 +2668,42 @@ UniValue CreateUTXOSnapshot(
2668 
2669     afile << metadata;
2670 
2671+    std::map<uint256, std::vector<std::pair<uint32_t, Coin>>> mapCoins;
2672+    unsigned int iter{0};
2673     COutPoint key;
2674+    uint256 last_hash;
2675     Coin coin;
2676-    unsigned int iter{0};

fjahr commented at 5:47 pm on March 4, 2024:

This move doesn’t seem necessary.

fjahr commented at 4:34 pm on March 10, 2024:

Should be addressed in #29612

in src/rpc/blockchain.cpp:2681 in 4e194640a7

2677+    std::vector<std::pair<uint32_t, Coin>> coins;
2678+
2679+    auto write_coins_to_file = [&](AutoFile& afile, const uint256& last_hash, const std::vector<std::pair<uint32_t, Coin>>& coins) {
2680+        afile << last_hash;
2681+        afile << static_cast<uint16_t>(coins.size());
2682+        for (auto [vout, coin] : coins) {

fjahr commented at 11:28 pm on March 4, 2024:

I think you should call vout here either n or vout_index, otherwise it might be confusing

fjahr commented at 4:34 pm on March 10, 2024:

Should be addressed in #29612

aureleoules commented at 5:52 pm on March 7, 2024: member

Thanks for the reviews but I don’t have time to address the comments so please mark this pull as Up for grabs.

aureleoules closed this on Mar 7, 2024

fanquake added the label Up for grabs on Mar 7, 2024

Sjors commented at 7:39 pm on March 7, 2024: member

Thanks for the great start @aureleoules! @fjahr can you take this one? Otherwise I can, but not sure how soon.

fjahr commented at 9:27 pm on March 7, 2024: contributor

Thanks for the great start @aureleoules!

@fjahr can you take this one? Otherwise I can, but not sure how soon.

Yeah, I will reopen this shortly.

maflcko removed the label Up for grabs on Mar 11, 2024

rpc: Optimize serialization disk space of dumptxoutset #26045

Code Coverage

Reviews

Conflicts