(small) CAP draft: bucket initial entries

[Graydon Hoare]

Hi,

We've been investigating performance characteristics of the bucket list and various operations at the database recently and have identified a technically-quite-small design issue that's nonetheless causing quite significant performance problems. The way to fix it is sufficiently straightforward that I figured I'd just put together a CAP outlining the problem and a simple solution. IMO this is just a bugfix, but it does have protocol-level impact so needs to get everyone agreed on what-to-do before making a change. Hopefully not too contentious.

Draft attached, please let me know what you think!

Thanks,

-Graydon

[Graydon Hoare]

As a quick followup to this: I've posted preliminary sketch of the code for this in a PR here: https://github.com/stellar/stellar-core/pull/1950

Comments welcome!

-Graydon

[David Mazieres]

'Graydon Hoare' via Stellar Developers <stell...@googlegroups.com>
writes:

> As a quick followup to this: I've posted preliminary sketch of the code for
> this in a PR here: https://github.com/stellar/stellar-core/pull/1950

Is there any reason the INITENTRY can't be liveentry? Why not this:

enum BucketEntryType
{
LIVEENTRY = 0, // Before protocol 11: created-or-updated;
// At-and-after protocol 11: only updated.
DEADENTRY = 1,
INITENTRY = 2, // At-and-after protocol 11: only created.
};

union BucketEntry switch (BucketEntryType type)
{
case LIVEENTRY:
case INITENTRY: // New with protocol 11.
LedgerEntry liveEntry;

case DEADENTRY:
LedgerKey deadEntry;
};

Also, probably not in scope here, but we should be thinking about
facilitating SPV wallets as we reformulate the bucket list format...

David

[Graydon Hoare]

On Thursday, February 7, 2019 at 8:36:27 AM UTC-8, David wrote:

union BucketEntry switch (BucketEntryType type)
{
case LIVEENTRY:
case INITENTRY:             // New with protocol 11.
    LedgerEntry liveEntry;

I was not aware that XDR permitted multiply-tagged cases like that. If so, then sure, that is equivalent and smaller so I'm happy to use it.

 

Also, probably not in scope here, but we should be thinking about
facilitating SPV wallets as we reformulate the bucket list format...

I think this is beyond scope for this change, but (very roughly) I can speculate/discuss this a bit:

  - Stellar strongly differentiates accounts from transactions, so this analogy depends on what your putative SPV wallet is trying to verify.

  - Verification of either transactions or accounts is going to work off the ledger chain, which already has an embedded skip-list structure to find (in a logarithmic-in-time number of downloads) a trusted historical ledger header from a given present consensus ledger.

  - If you want to verify the presence of a transaction in the chain, these can be fetched from history for any given ledger and compared against the TransactionResultSet (that includes txn hashes) in that ledger header. 

  - If you want to verify the state of a given account at some point in time, these can be fetched by downloading progressively older buckets in the bucket list of a given ledger until you find one with an entry for that account. If you're investigating an account that was changed recently, this should happen in one of the newer (small) buckets.

The only verification that's potentially slow in this model is verifying the state of an account at-present that was last changed a long time ago; depending on how long-ago the account was changed, this could involve as much as downloading the oldest (biggest) level of the present bucket list. We could theoretically restructure buckets to have some sort of maximum size and trie-like substructure to permit directly fetching & investigating partial buckets, but this would be a fairly involved project (note: bucket entries are sorted presently, without concern to whether a bit-string prefix of their keys is uniformly distributed as a trie would want; these are similar but different situations requiring somewhat careful rearrangement) and it's not clear to me that this particular type of verification is a pressing need relative to other performance issues.

(I should also say here: I'm not totally opposed to working through such a change eventually; it could potentially support a variety of improvements to the bucketlist, such as parallel downloads, parallel merges, and/or checkpoint/restart of big merges. As with the SPV case though, these are all quantitative motives, which are not going to be very amenable to quantitative analysis until after we've fixed the current issue and flushed the obsolete tombstones that comprise 99% of current bucket volume out of the existing buckets.)

-Graydon

[Nicolas Barry]

Question on the change to the "shadowing" code:

If I am not mistaken, it seems that the current draft proposes keeping entries that are shadowed if they are DEAD/INIT, if done like this, we *are* changing the merging behavior even on old pre-protocol 11 buckets as currently we remove the DEAD entries that are shadowed by something else.

Because of that, I think we need to solve something I thought we didn't have to cover (sad trombone)...

When merging, we need to figure out how to compute the version of the merge algorithm to use.
There is a tricky edge case when the protocol version changes from old to new behavior as nodes will "resume merge" at different times, depending on when they join the network:
Some nodes will start merging before the version change, others will start merging after the version change (imagine a node being down for a couple ledgers around a protocol upgrade, when restarted it will replay using messages from the network).
Which version to use and how are nodes going to be able to know this information? Currently we only know about the "last known ledger".

I think what we really want to do is use the "merge" behavior from when the merge was first conjured.

--
You received this message because you are subscribed to the Google Groups "Stellar Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to stellar-dev...@googlegroups.com.
To post to this group, send email to stell...@googlegroups.com.
Visit this group at https://groups.google.com/group/stellar-dev.
To view this discussion on the web visit https://groups.google.com/d/msgid/stellar-dev/9d9d9396-69e8-4541-84ef-37d50047e590%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.