April 2025

Completed LF2.2 (all tables) with 12.4GiB heads in 9.0 hours.

I reworked the database::iterator template today, to make the usage more idiomatic. I then updated the linkage template for non-byte-aligned link domains. Now I'm integrating that into the hashmap head, which will allow the sieve to be 33 bits and the point link to be 31. This moves a wasted bit from the link to the sieve, doubling the sieve capacity.

Well, turns out I was misreading my sizing spreadsheet. We can't pick up an extra sieve bit from the point link, as there is no link capacity for it. But at least the templates are now generalized :/.

Working off some more backlog. Used the preceding work on bit-alignment (vs byte) of link and sieve to mask links, no longer setting all bits in the word for the terminal value. Then applied this guard to merge a couple of 1-bit values that were being stored as a 1-byte, into adjacent restricted pk values. This saves one byte per row in the strong_tx and point (previously implemented) tables (~3.5GiB total). This compression can also be applied to a couple of other tables.

This link masking surfaced a simple but important issue with the sieve, as it gets applied naturally to the header table, as it the keys are 23 bits and the header is word aligned (32 bits). This leaves 9 non-aligned bits for the sieve. Because this results in a 7 bit screen and a 2 bit selector, the number of screens is limited to 2^2, and saturates pretty quickly. The 16 screen point filter never saturates, so I never saw the issue, and it was subtle enough to not be caught in test. When the sieve becomes "full" (last screen applied) the first bit of the sieve value must be zeroed. This corresponds to explicit mask of that sentinel bit in the mask table. If it is not masked it's possible for a full (not yet saturated) sieve to produce the empty sentinel, resulting in false negatives (which is bad). That's now resolved, and there is no impact to previous perf measurements.

Also just made the secondary hash function (used by the sieve), independent of the primary in the case of non-point hashing (so like tx/block hashes and links). That was already complete for point hashing. This primarily advantages the header table, as it has a [[9][23]] bit split for [[sieve][link]], where the sieve is pointless if the hashes are not independent. Also made sure that both hashes stick to the lowest order bytes where possible, to avoid block hash zeros, and overlap minimally when the key space is limited.

All checked in, which takes care of these, along with some bonus table compression:

I've got a conflicting appointment tomorrow, won't be able to make the meeting.

I'll be here.

Hmm, I was here, but didn't start the meeting. :/

Managed to get the compact filters tables and the duplicates table stubbed in, and reconfigured tables and defaults for load factor 2.2. Will convert txs and validated_bk to array map tables tomorrow. That’s a slight header side tradeoff for a smaller table body (no links) and no hashmap conflict lists to search, just array dereference each element. This works out well with block-sized tables (~1M) but not with tx or put sized (~1.0 -2.6B). MB vs. GB header differences.

6.15 hrs on 64GiB

I was thinking today about the bloom filtering estimation I did previously. I wasn't entirely happy with the estimates that I was getting from Grok, so I finally decided to just make an equivalent bloom implementation that could serve as a drop-in replacement for sieve. I just completed that, with a full test quite, and am now running the scenario with the same size filters on the tables, and reporting false positive rates for the point table. This will give me a block-by-block comparison. Tuning is potentially a variable. I know that for Sieve LF=1.5, m=32 ... k=4 is optimal. Grok says that for Bloom LF=1.5, m=32 ... k=5 is optimal. The advantage of Bloom is that it doesn't store k values, so it can use all 32 bits for filtering (vs. 28 for Sieve in this example). I'll run Bloom at k=4 and k=6 just to make sure 5 is its optimum.

At LF1.5, m=32, k=5 .... bloom emits 3,604,705 false positives, vs. 14,179,984 for sieve, or 1:4. Good news for performance :).

With that we managed to squeeze mini validation to 8.72 hrs (previous record was 9.15).

At LF2.2, the bloom total FP rate is 0.33% and sieve is 0.43%.

At LF1.5, the bloom total FP rate is 0.137% and sieve is 0.141%.

I think that the plots will show that sieve is better at lower LF and bloom is better at higher.

The absolute numbers here are tiny fractions of total searches (~2.6 billion total). These would be better presented in terms of instantaneous rate but super slow moving this much data around in a spreadsheet.

Core effort to speed up "assume valid" (from 40h 54min to 18h 14min in one benchmark): https://delvingbitcoin.org/t/ibd-booster-speeding-up-ibd-with-pre-generated-hints-poc/1562

Completed the integration of the duplicate table into the block confirmation query, so that duplicate points of the block are populated to the prevout table for each block during validation - with the duplicate table being populated during tx archive. So the confirmation workload is now properly distributed for maximal parallelism and data locality. Nearly all of the confirmation cost is therefore absorbed by the fully parallel archive (block download) step, with a total confirmation cost of under an hour on the mini and maybe 15 mins on the maxi.

Also spent all of the slack time running syncs and table scans with various bloom and sieve configurations. In doing so I squeezed out some more performance by preserving entropy in bucket selection and filtering, reducing body searches (now down to 0.1% average over the point table).

New maxi record of 4.29 hrs full validate/confirm with the additional duplicates table integration.

I had a very small loss of entropy from this (pseudocode):

uint32 buckets = some constant
uint64_t entropy = hash_combine(to_int<8>(point.hash), point.index)
uint32 bucket = ((uint32)entropy) % buckets

which should have been this

uint32 buckets = some constant
uint64_t entropy = hash_combine(to_int<8>(point.hash), point.index)
uint32 bucket = (uint32)(entropy % buckets)

As a result both filters (bloom and sieve) are performing better. However sieve has improved disproportionately. This is likely because its performance is strongly tied to the Poisson distribution, which has improved slightly. I'm still running tests to see where the optimal configs come out. But overall I've been able to drop false positives on the 2.2LF table from around 10M to around 2.5M. That's pretty close to what it was previously with the 1.5LF table, which is a big improvement.

After a LOT of performance testing and tuning I've settled on the bloom filter and method of sizing [k=log2(m)], as well as the means of point hash combining for the bucket selector and filter entropy (fnv1a). Final tests on the mini show 48 minutes with the point duplicate search enabled, and 36.8 minutes with it disabled (which is a few seconds faster than the fastest milestone run ever on any machine). Since the hash combining has a higher computational cost, and is always in effect, I wanted to make sure there was no impact from it, and it appears to be inconsequential.

These are for a LF 2.2 table, so Bloom always finishes ahead.

I still find it crazy that we are at 36.8 minutes on a $350 machine to do what Core is trying to do in 18.2 hrs and currently does in 40.9 hrs (according to their own benchmarks), using a distribution of validation "hints" (in conjunction with "assume valid"). On this machine we currently fully validate in 8.7 hrs.

In other words... it takes us less than a minute to do what it does in an hour.

Well maybe that machine is now $714. 😅

Point filtering is buttoned up and checked in. That's almost a wrap for full validation. Two more things to complete there: (1) restore the confirmation chaser reorg logic, and (2) implement taproot in system (this was mostly implemented before taproot release but deprioritized). Times shouldn't change to much, though there will be a slight increase for full validation. Current milestone ("assume valid") sync times are 37 mins (mini) and 50 mins (maxi). Despite having significantly more memory and CPU power, max has a slower bus (PCIe3), and therefore RAM and SSD - and also does not have shani. These numbers increase to 48 mins (mini) and 56 mins (maxi) when point duplicate tracing is enabled (for later validation optimization). Current full validation sync times are 8.72 hrs (mini-32gb), 6.16 hrs (maxi-64gb), and 4.37 hrs (maxi-256gb). Times for full validation are driven by the combination of RAM, SSD and bus performance, as well as overall CPU power.

These are based on Internet-based sync on my measured 2.3gGbps (40 Mbps upload) cable Internet (2.0Gbps purchased). The mini is the $350 Windows 10 Temu box with 8 dual 3.8GHz shani cores, maxi is an 8 year old Windows 10 Dell with 32 dual 2.1GHz non-shani cores. On these machines Core takes about 14 (mini) and 24 (maxi) hours to perform assume valid sync, and about an extra hour when fully validating.

I was just finishing up the compact filters integration (bip157/158) with some performance runs, and to measure the variable table size. I flipped on the performance profiler and was shocked to see that like 95% of the entire milestone run was being consumed by siphash and chain::script::to_data(bool) (both within golomb_coding). These were both the result of using the boost-based iostream with the associated reader and writer. I removed this from performance critical network and database operations about a year ago, but until now I haven't seen quite so clearly how expensive it was. After swapping in the fast iostream and read/writer, these aspects barely register (less than 2% of the run). Crazy.

The redesign of filters split the filter head and filter body computations into the validate and confirm chasers. When validating we have the data necessary to populate the filter body, which is the block and its populated previous outputs. These are hugely expensive to obtain, so we don't ever want to have to do it twice. If we aren't validating, but are filtering, then we just bypass the validation aspects in the chaser. Filter body creation is entirely independent of the filter header creation, and has the same ordering constraint as validation. The result is written to an arraymap. This means there is no hashmap, just an array header which positions the link to the body element in the array element corresponding to the block surrogate key. Since blocks are keyed sequentially (by insert) there is no chance of a conflict, even if we happened to write the same block twice. That would just lead to two bodies and the last writer winning in the array head. This technique was developed to avoid using hashmaps for the prevout cache table. Filter header creation hash the same ordering constraint as block confirmation. The previous filter header must exist to create the next. And of course the body must have been created (during validation). So confirmation reads out the body and the parent block filter header, computes the current header and writes it to the filter header arraymap. This table is also an arraymap because it's also block-aligned, and the indexing needs to be independent of the body table because of their independent creations along with the table append-only rule. But the heads for these are very small, so independent tables with no hashmap lookup is very efficient. Given that filer header creation must read from both the filter header and body tables, avoiding hashmaps in favor of arraymaps is a big savings. So that's all done and checked in now. Sizing and perf numbers coming next.

I should point out that writing the same block (by natural key) twice just creates two different instances, with their own links, one of which could get confirmed and end up typically being referenced for filter queries. This is extremely rare but possible and fine. I was referring to the other even more unlikely (probably impossible for the node to produce) but also fine (for the database) scenario of a filter for the same block instance (same surrogate key) being written to one or both of the arraymaps.

As with validation, the filter body computation is fully parallelized by block, and as with confirmation, the header computation is sequential but trivial. These slid very cleanly into the existing chasers.

Running alongside the conference call the compact filter milestone sync complete in 1.8hrs.

1.75 hrs on a clean run.

Here's a significant new stat... full validation on the maxi is 4.37 hours and with the addition of compact filters is 4.52 hours. So compact filters adds only 9 minutes to full validation.

5.6 hours for full validation with full Electrum address index (110GB) and compact filters (10GB) generation (and as always, full tx index and spender index).

Resolved a leak in chain::operation deserialization which only manifested in failed serializations. Further optimized stream-based serializations by internally using fast streams (i.e. unless stream explicitly provided). Also moved sieve and bloom filter implementations into the system library, and rationalized with golomb coded sets.

I've just completed the restoration of the confirmation chaser. This changes the simplified loop back into the full reorg capable confirmed chain manager, but with the final confirmation design. The implementation is simpler than it's ever been, mapping closely to the original design document, another good sign. I'll be running some tests to measure performance impact, but from experience and early indications, it's inconsequential.

There has been one, long-standing, mysterious behavior in the node. You may have heard me talk of it in past meetings. It seemed to come and go randomly, unaffected by my attempts to isolate it, and narrowly focused around segwit txs. Specifically, witness data would be missing at script validation time (causing validation failure). It wasn't clear whether the data was supposed to be there or incorrectly expected, or whether it was read and lost, or never read, from either the wire or the store. But sparse reproduction and many possibilities made it very hard to diagnose. So finally I put in diagnostics to trace out the segwit tx count for each block. Given that this count is driven off of witness data, this shows what I'm getting off the wire. Then when the validation failure occurred, I also wrote out the count. That was a couple weeks ago. Last night it happened again. The failing blocks were read from the wire without witness data, and all failed for lack of witness data, and were read from the store without witness data. So either there was an intermittent failure to read the data off the wire, or another mystery. But given that there was just this isolated and contiguous segment of blocks with missing data it finally dawned on me what was happening. There is a peer that is sending non-segwit serializations despite negotiation for witness data serializations. This doesn't get caught by the witness commitment check, because it's optional without witness data. The requirement for witness data can only be determined by investigating the script patterns (which is what precipitates the later validation failure). Fortunately most blocks above segwit have witness data, so this additional check is very rarely required - only when segwit is active and only for blocks with no witness data (which is already checked during the commitment validation). Without this the block gets archived and later during validation (and not at all during milestone) the scripts are validated - resulting in an invalidation of the archived block, and subsequent stall. This manifests similarly to a block hash malleability failure.

Okay, I believe that is now fully resolved. Will try for Taproot again tomorrow :).

New record full validation on the mini, 8.43 hrs with 6 sec shutdown :). This includes the additional confirmation organization behavior, the above witness fix, and a couple minor optimizations.

There appears to have been an unexpected performance gain on the mini. I have not tried validating with a large window on the mini in a very long time. Normally I run 5k for validation on the mini, and 50k or higher for milestone. And always 50k or higher on the maxi. This is for data locality, as it improves query response and reduces paging. However the small window also reduces concurrency and can significantly slow milestone for example. Well I accidentally ran a full validation on the mini with a 50k window AND the 100GB Electrum table population AND I had the validation tables set for milestone, so the was only 1 bucket in validate_bk, which turns this 1.7M entry table into a linked list! Nevertheless, the full validation run completed in well under 8 hours - breaking the record. This should mean that the filters could also be populated at the same time, with little impact, since most of that is just what's already available during validation. I'll have to spend some time isolating whether this was caused by the window size increase. But I think that the slew of changes over time made the narrow window less important. If this holds up, we have full validation, with full ElectrumX index, full Compact Filters index, and the always-on full spender, tx, header, and height indexes - completing in under 8 hours on a $350 machine.

I re-ran the above full validation, with full ElectrumX address index, on the mini (this time without the disk full condition that hit the last one, and with the proper validated_bk sizing for validation). Completed in 7.5 hours! I'm going to give it a go now with the addition of the compact filters index, though not sure I have enough disk space. The store with address index is 800GB and the total drive is 1TB. Since tables over-allocate the additional 10GB might be enough to fill the remaining 34GB while running. If so I'll run it a second time with reduced growth rates. Also going to re-run full validation without address, at the 50k window. That should certainly outperform this new record.

It's early, but looking like full validation on the mini with a 50k window and without the optional address and compact filter indexes will complete at 7.0 hours.

I believe that the main reason I originally reduced the mini window to 5k was that it significantly improved the costly confirmation query due to improved data locality. However this query has been almost entirely eliminated. The larger window improves concurrency by reducing the gaps in the sawtooth pattern by 50/5 or 10x. That's significantly more time spent validating vs. waiting on blocks. The fastest runs are with an unlimited window, which in theory eliminates download gaps altogether. However when validating this can lead to arbitrarily long delays when waiting or an early block. 50k is therefore a good compromise when validating, otherwise unlimited. And it now looks like we no longer need to worry about varying the download window based on RAM/SSD size/speed.

Passed block 700k and still tracking at 6.94 hrs to complete.

Passed block 800k and still tracking under 7 hrs to complete.

Complete full validate on mini to block 850k in 6.90 hrs.

Running now on the mini with full validation, full Electrum address index, and full compact filters. It's slightly lagging the validate/address run (which was 7.5 hrs) which is expected. I'm guessing around 7.9 hrs which would be pretty amazing. On the maxi it's all around 4.5 hrs.

This full everything mini run is about 3/4 complete and tracking almost identically to the same run without compact filters. Looks like it will finish up at 7.5 hrs. I've got a couple simple table optimizations to implement, which might be material. These change the txs table and validated_bk tables to array maps. This slightly increases the head size on these small head tables (1-2MiB) but significantly reduces paging and reduces body size, since they will no longer be hashmaps.

I've also done some work today to rationalize and simplify the header organizer and block organizer, and to better manage the disk full with restart scenario that can result in strong_tx inconsistency with candidate or confirmed indexation. One issue with it remains to be resolved. I also wrote up an issue with simple resolution having to do with potential for conflict between candidate reorganization/regression and confirmation of the candidate chain. Finally, I introduced a regression in confirmation work tracking, which I also posted an issue for. Hoping to have these each resolved tomorrow, as well as the change of the two tables to arraymap. Yesterday I also checked in the first small piece of Taproot.

The big news for the day however is that the mini can now handle a 50k validation window, like the maxi, and can at the same time support both electrum address index construction and compact filters construction. Given the larger window, concurrency is much increased, and as a result we are now at the following 850k block sync rates on the mini with 2.3Gbps Internet: 50 mins milestone, 6.9 hrs full validation, and 7.5 hrs full validation with address index and compact filters, and maxi: 59 mins milestone, 1.9 hrs milestone with address index, 1.8hrs milestone with compact filters, 4.3 hrs full validation, 5.6 hrs full validation with address and compact filters. Notice how much closer mini validation has come to the maxi!!!

The total mini run actually completed at 7.0 hrs - full validation, address, filters. However there was a regression in that build that prevented final confirmation from fully executing. That wouldn't increase the time much, probably no more than 15 mins, but I'll have to run it again. All of the heavy lifting for confirmation is now done in the archive and validate phases, so it's still a very good test of all features running together.

Ran the above kitchen sink config again on the mini, completed in 7.6 hrs. Still optimizing, that should come down a bit.

The above 5.6 hrs maxi record for full validation with Electrum address index and compact filters has been shattered, now 4.76 hrs. Store size 810GiB.

This is a consequence of recent optimizations in writing the set_strong table (confirmation records), and simplification of the organization process. I also resolved the potential data integrity issue with confirmation records - confirmation index becoming inconsistent with strong following a disk full pause/restart. I ended up using a two phase commit between these records. By ensuring they are both allocated before becoming written and accessible there is no risk of an inconsistency (publicly atomic).

I won't be able to make the meeting today.

Generally speaking all of our tables are allocated, written, and then linked. Linkage is either from another table, or from the table head. We manage the creation of these records so that no element is accessible (linked) until it has been allocated and written. Given that head updates are atomic, this is fully thread safe. However I realized the two height indexes are never actually linked, they are just immediately public once allocated. This is problematic given that the write (of the header link) to the element follows the allocation. This can lead to a read conflicting with a write, resulting in an invalid read result.

Wish I could make it!! Enjoy 🙂