davecgh
commented
2 weeks ago I don't see any issues with anything presented. It's well thought out and, crucially, focuses on recovery from the failure modes.
A couple of notes.
Index file
I could be wrong here, but I suspect that due to the variable size of records (aka may or may not have the full block hash due to a collision) not having entry sizes will potentially bite you since it will make iteration more expensive. It might not be too bad if you jump directly to the flag and use that to offset the iterator. I just recall that when doing similar work for dcrd many years ago, and even more generally when dealing with blocks, not having record sizes tends to make iteration much more painful.
Note that long running nodes have never publicly documented a > 1 block depth reorg in Decred.
It does not at all change your assessment, but for 100% correctness, I have historical data from 7 nodes that have been running uninterrupted since inception and there have been >1 depth reorgs, but very few. Concretely:
----[[ dcr reorg stats for blocks 0 to 886109 (7 data sources) ]]----
current block: d77981a50329abd5c14b3f7292b09d10e9fe797dd2a4c54dd5e62028e93d4fd2 (height: 886109)
reorg depth 1: 7120 (0.8035%)
reorg depth 2: 26 (0.0029%)
reorg depth 3: 3 (0.0003%)
reorg depth >3: 0 (0%)Appendix 2: Use of Syscalls, MMap, and io_uring
I agree with the assessment here, especially when the block index is in memory. I would say that it might be worth considering in the case the alternative design in appendix 1 is used though.
Appendix 5: Alignment of CFilter data in disk
This one is probably a bit of a toss up. SSDs are largely going to ignore whatever you do since their controllers have their own built-in wear leveling algorithms which determine where to put the data anyway. It could potentially help a little on HDDs.
matheusd
Proposal: drop bbolt for chain storage
Rationale: bbolt is the largest cpu and mem consumer during initial sync and that is entirely due to storing headers and cfilters and fetching blocks for difficulty validation. The features provided by bbolt (in particular: transaction atomicity) are not necessary for storage of chain data. That, plus a few other desirable features (listed below) could be better provided by a new chain db implementation.
NOTE: this is NOT about moving the entirety of dcrwallet off bbolt, ONLY the chain data (headers and cfilters).
Downsides of bbolt
The following measurements are from a sample chain sync of a new SPV dcrwallet instance connected to a single remote source known to have good connectivity and being up to date. Sync height was 885252.
Desired New Features
The following would be the new features desired out of a new chain db:
Overall Design
This is a rough first draft of the design for this DB:
The storage strategy for each arena may be different, according to what provides best throughput during IBD and ongoing sync (after IBD completes).
Long Term Arena
Short Term Arena
Long Term Arena File Format
Files
The long term arena is composed of four files. Before the actual data, each file starts with an 8 byte file header:
Headers File
File for storing headers. This file works as raw header storage. Each entry has the following format:
This file MAY have padding at the end, filled with zero bytes.
Due to headers having a fixed size, the last entry can easily be found when iterating backwards (it's the last one at a position modulo the header size that is not all zeros).
Headers are only put into the headers file of the LTA after they have at least 6 confs (see algorithms below). Due to this, the block hash of a header (other than the last one) can be found without requiring a hashing operation by simply looking at the
PrevBlockfield of the next header.CFilters file
File for storing CFilters. Each entry has the following format:
After the last valid entry, this file has a footer with the following data:
This file MAY have padding at the end, filled with zero bytes.
The goal of having a footer is to explicitly mark the end of (what should be) valid data. Note the footer itself is not a valid entry: the total entry size would be larger than the file itself and the height would be larger than the last header. The footer is meant to be easy to find when iterating backwards from the end of the file.
The goal of having the total entry size on both ends of the struct is to allow backwards iteration of the CFilters file: after identifying the start of the footer, the last valid entry can be correctly read by reading the final total entry size and prior entries can be iterated backwards.
This will be useful during DB startup, to validate the last entry of the CFilters file matches the last header.
Index file
File for storing the index of block hashes to block height and CFilter entry location. This can be rebuilt entirely from the headers and CFilters file if needed, so it could be an optional feature.
Each entry contains the following:
Due to being stored already sorted, the height of a block is implicit (so the first entry in the file corresponds to block 1, and so on). Due to the header sizes being fixed, the offset into the header file is implicit.
The "reduced block hash" is similar to the "short block key" in dcrd: it's the first 32 bits of the block hash.
The MSB of the flags field is used to indicate whether the full block hash is present in this entry or not, while bits 0 to 28 is the total CFilter entry size.
The full block hash is only present in instances where there is a collision in the reduced block hash. In this case, the first block where a particular reduced block hash occurs does not have the flag set, while later occurrences have it set. The wallet can reconstruct the index appropriately. On the current mainnet, as of block 885208, only 84 blocks have a collision in their 32 bit reduced block hash key.
This file contains a footer. The last entries of this file are:
The footer is intended as a marker that the last write operation of the index was finished correctly. When reading the index file, if the footer is not correctly present, the file may be assumed as corrupted and should be rebuilt from scratch. Both entries of the footer are invalid: the all zeros entry points to offset location 0 in the CFilters file, while the all ones points to an entry that will be at an offset larger than the CFilters file size.
This file MAY have padding filled with zero bytes after the last two entries. The footer, therefore, ensures the presence of at least 12 zero bytes at the end (but more are possible).
The goal for the index file is to allow the wallet to quickly load the known blockchain into an in-memory index, for fast header and CFilter lookup. The current mainnet chain as of height 885208 would require (at a minimum, disregarding overhead for pointers and other structures) about 10.6 MB of RAM to keep this index in memory.
There is an alternative design we may pursue for the index that does not require keeping any data in memory. The drawback for this design is that it has an increased disk space requirement and requires disk accesses for fetching data from the index. See Appendix 1 at the bottom for more details.
Sidechains File
File for storing blocks that were once part of the main chain but that have been reorged out.
The entries in this file are rarely needed - they are only used in certain scenarios that involve failed writes and multi-wallet usage of the DB.
Each entry in this file has the following format:
This file may be padded with zero bytes at the end.
Note that entries' fields are organized in reverse of what would be ordinarily expected: block hash and header appear at the end of the entry. This is meant to ease reverse iteration of this file, when looking for a block with specific hash or height.
There is no particular structure to this file. However, it is expected that later blocks will appear after earlier blocks. When a reorg greater than depth 1 happens, blocks that were reorged out will appear contiguously, in block sequence order.
Short Term Arena
This arena is meant to store the most recent 6 blocks: the tip block plus its five immediate ancestors. This arena is organized as a single file, meant to be used in a circular buffer fashion: a new tip block will cause one block to be evicted from this arena after it is written to the long term arena, and then the prior storage location for that block will be overwritten with the newly received block (assuming the newly received block is extending the chain as opposed to creating a sidechain).
This file starts with an 8 byte magic header: 0x6463727374613030 ("dcrsta00").
Each entry in the file has the following structure:
The CFilter storage space is pre-selected according to the max possible CFilter size. It is pre-determined in order to ensure each entry has a completely fixed size on-disk. If the max possible sizes of CFilters change due to a consensus rule change, then this would require a db upgrade.
The max number of CFilter inclusion proofs is set to 64 for a similar reason. While the currently deployed consensus rules enforce that the inclusion proof for CFilters has size 0, we opt to increase the max possible size of the inclusion proof in order to ensure future rules upgrades do not require a db upgrade. This would only be required if a very large number of new commitments were added to the header.
The special file checksum is special in the sense that it is not a standard file checksum/hash computed by processing the file in-order. Instead, the checksum is calculated by hashing the data for the block, plus its 5 immediate ancestors in block sequence, excluding their own special file checksum. This is important to note, because the blocks in the short term arena file are NOT stored in height order. The checksum is meant to ensure the last write operation completed successfully: during startup, while loading the blocks in the short term arena, the wallet may verify that the checksum of the tip block matches the expected one based on prior blocks, and if not, then it should discard all blocks in this arena and re-fetch them (or rewind until the checksum matches).
Any number of entries in this file may be completely filled with zeroes (for example, because of a reorg happened or because the file was recreated after a write failure operation).
Algorithms For Blockchain Evolution
Of particular importance is considering write failures before/during/after each step of operation, how that can be detected (i.e. what is the disk state and startup validation procedures) and what action should be taken.
Connecting new blocks
This is the procedure for connecting recently mined, individual blocks. This is the primary write function during steady-state operation of the DB (after IBD has completed) and is the most likely to fail due to lack of disk space (because it is the primary one that may require growing the files).
Assumptions:
Process:
Stage 6 can be roughly understood as the "commit" stage: if the checksum of the most recent block in the STA is correct and the most recent block of the LTA is at a 6 block delta from it, then the prior write operation was successful.
Failures before that stage can be detected by the prior validation check. Failures between stages 1 to 5 can be easily recovered: the write operation can simply be repeated (completely or starting from where it failed).
Failures on step 6 means the most recent block of the STA is damaged (the checksum is mismatched) and should be discarded: in that case, the client code (wallet) will fetch the most recent block after DB startup completes. The faulty entry may be cleaned up by being zeroed.
Adding an Alt Chain Tip
This happens purely in memory. The memory-only sidechain forest is updated to track the new chain tip, but otherwise no file modification is necessary.
Perform a <= 6 depth reorg
This is the procedure for connecting an alternative chain tip to the current tip that DOES cause a reorg. This happens episodically within the Decred chain when a new block is found that extends the current chain tip and it has more work than the current best chain tip.
Assumptions:
Step 3 is necessary so that, even if a failure happens in the software after the entire reorg procedure is carried out, the DB clients (wallet) will be able to fetch the header and CFilter of the reorged-out block in order to carry out their own reorg procedures (e.g. rewinding transactions). It is particularly necessary when a single DB is used for multiple wallets (which may not be online when the DB is updated).
Steps 4 and 5 are split so that, upon restart, it is obvious whether one of them failed and whether the STA is correct or not. Failures during step 4 mean only part of the old block data has been erased, while failures during step 5 mean only part of the new block data has been written. In either case, that entry's checksum (which is the last information written to disk for an entry) will fail to validate.
Doing steps 4 and 5 separately may be seen as superfluous (as the overwrite would erase the data anyway), and doing it in block sequence order (as opposed to file order) may be seen as taking a performance hit, but doing it in this fashion will increase the chances of having as many blocks as possible written correctly to disk, in case of write failures.
Note that long running nodes have never publicly documented a > 1 block depth reorg in Decred, and thus it is expected that no more than depth 1 reorgs will be needed (though this algorithm should support reorgs up to depth 6).
Perform a > 6 depth reorg
This is the hardest reorg to perform in the DB and the one that could most likely cause corruption. Therefore, this process is geared towards correctness as opposed to performance.
Assumptions:
Process:
The first disk operation must be adding the reorged-out blocks to the sidechains file to ensure any clients may fetch that data if it is needed to perform its own reorg procedure.
The rationale for zeroing out files before performing any of the write operations is the same as for regular reorgs: this increases the confidence that write failures will leave the DB in a state that is at least partially consistent in the sense that blocks earlier than one that is detected as broken are known to be correct.
The rationale for zeroing out the headers file first (as opposed to last) is that headers that are missing their CFilters should cause clients (i.e. wallet) to fetch the missing CFilters while extra CFilters without corresponding headers is a faulty state detected and corrected during DB startup (the extra CFilters and index entries may be erased). The first option would cause the client the potentially attempt to fetch CFilters that, at a minimum, are not needed anymore and on a worst case scenario won't be provided by any nodes anymore. The second is easily recoverable from after the extra data is erased - syncing continues as if the wallet is out of sync.
Note that if the process fails before step 8, the blocks that would be reorged-in (the new chain) is not recorded and will have to be downloaded again after startup.
Initial Block Download
During IBD, a very large number of headers and CFilters is fetched at once, in batches. It is therefore ideal to make use of that information to avoid performing redundant writes. In particular, writes to the Short Term Arena are unnecessary, because it is likely that a new batch of headers that will soon be received will overwrite it.
Writes to the LTA files can be batched: a batch of headers, CFilters and block index changes may be written directly, instead of being written block by block (assuming the clients have validated the correctness of the headers).
Additionally, the files can be grown directly in one operation, once the target sync height is known (however, care should be taken to limit the max file growth possible when syncing from untrusted sources).
The IBD batch addition process may be carried out until the tip is within 6 blocks from either the target sync height or the estimated blockchain height (calculated based on the target block production interval). After that, the DB should switch to the standard, steady-state operation mode.
DB Startup
Several validations must be performed during DB startup in order to ensure the data is consistent, and to fix faulty states in case of write failures. The following is a rough process for loading the DB from disk and creating its in-memory structures:
Final Discussion
This proposal is meant to establish whether want to move the wallet to use a new database implementation for its chain data.
If this is deemed as a reasonable goal, then the design in this proposal may be tweaked as necessary and implemented as a new independent package for testing. It can then be integrated into the wallet, with appropriate code to migrate the state of old wallets.
Appendix 1: Alternative Index File Design
Instead of storing the index by height (one entry per block), we may opt to store the index by reduced hash. Assume we use 24 bits of the reduced hash as key. We can create a file with 2^24 entries, each taking 16 bytes for a total of ~268MB. Each entry in this file would correspond to the presence of a block with that reduced hash value.
If the entry is all zeroes, that block does not exist. Otherwise, it may be set to one of two values (appropriately flagged):
The second value type is necessary when 24 bits are not sufficient to disambiguate between different blocks (i.e. more than one block shares the same reduced hash key). As of height 885208, there are 22815 blocks sharing the first 24 bits of their reduced hash key, with the max number of blocks sharing the same prefix being 4.
This design sacrifices disk space and query performance for reduced RAM usage.
Appendix 2: Use of Syscalls, MMap, and io_uring
The natural implementation for this DB would be using standard syscalls for file read/write. The writes are small enough and (apart from IBD) infrequent enough that using memory mapped files, io_uring or any other more advanced IO APIs should not be necessary (specially considering we need to fsync the final writes for durability).
However, it would be ideal if the data layer of the DB could be abstracted enough to support any IO API. This will need to be investigated.
Appendix 3: Use of Chain Data by Multiple Wallets
The same chain data could be used by multiple wallets (though not simultaneously) easily: during DB startup, the LTA and STA files would be locked by the running instance, ensuring only a single wallet instance can use them.
Then, after the wallet has gained exclusive access to these files, it can work as usual. During wallet startup (after DB startup), if it detects its rescan point (which is NOT stored in the chain DB) is earlier than the best chain header, this means some other wallet already updated the chain and the starting wallet should perform appropriate rescan and transaction sync duties.
dcrwalletcould be configured to use a separate (global) dir for chain data, such thatappdataand this newchaindatacould be configured separately.This would help multi-wallet apps (such as Decrediton) by reducing the total amount of space needed for each wallet (about 1GB with the current bbolt implementation on mainnet).
Appendix 4: Concurrent Access by Multiple DB Instances
This is a tricky subject, in particular because it would allow the chain to be updated "externally" from the point of view of a running wallet: wallet A could add a block to the chain that wallet B would have to be notified about.
This would require much larger changes in the wallet, so that it was driven by the chain DB (as a syncer) instead of the existing syncer packages (RPC and SPV).
If this is deemed as a worthy goal, we can discuss further requirements and challenges, but this is currently listed as an additional feature.
Appendix 5: Alignment of CFilter data in disk
Needed? Desired?
Appendix 6: Choice of checksum function
Ideally, this would be a rolling hash function so that on new blocks, the data for the last block is removed while the data for new block is added. This needs to be investigated.