ingest/cdp: derive ledger entry state for consumers

[sreuland]

What problem does your idea address?

current state of LedgerEntry's on network per LedgerSequence is not included in the current CDP export model. At present it provides just the LedgerCloseMeta for each LedgerSequence, which provides meta information only related to ledger entries that changed as a result of transactions within one ledger sequence.

The absence of ledger entry state for network at a given ledger sequence from the CDP exported model that consumers receive means downstream ingesting applications which need ledger entry states must solve how to acquire or derive this in addition to using CDP.

If ledger entry states were included as optional data from CDP consumer sdk, it would streamline downstream ingesting applications which need ledger entry states to avoid complexity of custom derivation or external dependency on RPC, encouraging wider adoption of CDP for more use cases.

What would you like to see?

Currently CDP consumer sdk is comprised of ApplyLedgerMetadata function for consumers to receive pre-computed LedgerCloseMeta's from a datastore.

The idea here is to expand the consumer sdk with new functions to perform on-the-fly ledger state derivation internally using combination of checkpoint buckets from HA servers and pre-computed LedgerCloseMeta's from CDP datastores and publish the ledger entry states to a local RocksDB:

RocksDB schema

key=hash(serialized LedgerKey)
value=serialized LedgerEntry

CDP sdk changes

type PublisherConfig struct {
	... existing fields
        HistoryArchiveURLs  []string,
        NetworkPassphrase string
}

type VerifedState struct {
        // thread sync internals here
	...
}

func (s *VerifedState) WaitForVerified() error { 
         // thread sync internals here
         ... 
}

func DeriveLedgerState(ledgerSequence uint32,
	publisherConfig PublisherConfig,
	ctx context.Context,
        ledgerStateDbPath String) error 

func DeriveLedgerStateUnbounded(publisherConfig PublisherConfig,
	ctx context.Context,
        ledgerStateDbPath String,
	stateVerifier *VerifedState) error 

The sequence for getting ledger entries at close of a specific ledger sequence:

• client invokes DeriveLedgerState on a thread, it blocks until ledger entries are finished for requested ledgerSequence:
  • internally it initializes ledgerStateDbPath to empty
  • internally, HA and CDP are used, the ledger entries are loaded into ledgerStateDbPath
• client reads entries from ledgerStateDbPath

The sequence for unbounded, continuously updated ledger entries from a network, aka 'current state':

• client invokes DeriveLedgerStateUnbounded on a thread, it blocks forever:
  • internally it initializes ledgerStateDbPath to empty
  • internally, HA and CDP are used, the ledger entries are loaded into ledgerStateDbPath
  • internally, initiate unbounded consumer to CDP to receive latest LedgerCloseMeta's from network
  • internally, verify state - determine when latest LedgerCloseMeta from CDP is sufficiently beyond CurrentLedger of HAS root, meaning current derived state is based on ledgers which are close enough to current network ledger, unlocks VerifedState. If it detects too far back, it (re)locksVerifedState
  • internally, DeriveLedgerStateUnbounded can stop and return error if severe error, and/or unable to verify state.
• client always waits on VerifyState.WaitForVerified first, when it's unlocked, client can proceed to read entries from ledgerStateDbPath

What alternatives are there?

if downstream CDP consumers need access to ledger entry states for any given ledger sequence, there are two current day options:

• Derive ledger entry states by fetching checkpoint bucket which is nearest the desired ledger sequence from remote History Archive servers, parse the bucket ledger entries as a baseline, and then apply, sequentially, incremental pre-computed LedgerCloseMeta's from CDP up to the desired sequence.
• Alternatively to derivation, could use an RPC instance and the getLedgerEntries endpoint

[leighmcculloch]

Is the idea of this that a product that needs historical ledger state could get that from CDP?

I'm interested in this concept because of:

• Serve recent historical state stellar-rpc#375

[sreuland]

yes, historical is one use case this proposal would address, obtaining a 'snapshot' of ledger states for a past sequence number, but doing it with CDP datastores and pre-computed ledger metadata, rather than requiring access to a 'captive' core pipe.

[tamirms]

We have the CheckpointChangeReader in the ingestion library which is essentially an iterator that lets you enumerate through all ledger entries that exist at a specific checkpoint ledger. The CheckpointChangeReader is used by horizon and stellar-rpc to bootstrap their respective databases when ingesting from scratch.

I think this should be sufficient for those who want to get all ledger entries that exist at a given point in time. The one limitation of CheckpointChangeReader is that you can only use it on ledger sequences which are checkpoint ledgers. However, we could enhance the CheckpointChangeReader implementation to allow it to work on any ledger using the following algorithm:

Given input ledger N, find the nearest checkpoint ledger C which is less than or equal to N.

If N == C we can use the history archive snapshot to enumerate the ledger entries as we do currently in CheckpointChangeReader .

Otherwise, we can obtain all ledgers in the range [C+1, N]. The number of ledgers in this range is guaranteed to be less than 64, so it's a relatively small number. We can extract all the ledger entry changes from these ledgers and compact them. After doing that we will have list of all ledger entry transitions which take us from ledger C to N.

Now we can enumerate through the ledger entries which are live at C using the history archive snapshot. And if we encounter a ledger entry that is in the ledger entry transition set we computed above, we can emit the final state of the ledger entry from the transitions instead of the state of the ledger entry from the history archive snapshot.

This workflow will allow us to enumerate through all ledger entries which exist at any ledger sequence regardless if it's a checkpoint ledger or not. The additional memory required to to store the compacted changes from ledgers C to N should be pretty small.

I think this would be a better API then the DeriveLedgerState() / DeriveLedgerStateUnbounded() one you have proposed because it is less prescriptive (this will allow a developer to ingest ledger entries into any database whereas the DeriveLedgerState() proposal requires that the developer use rocks db).

[sreuland]

Could you elaborate on why the client usage of CheckpointChangeReader is non-trivial?

I meant CheckpointChangeReader usage as being a part of whole ingestion algorithm required for computing ledger states at a target sequence for a given historical sequence or continuously in unbounded fashion for current state which the net implementation effort of that would be non-trivial.

Internal to that whole algorithm is the usage of CheckpointChangeReader to establish the starting state of entries in combination with replaying a subset of ensuing ledger metadata retrieved from a CDP datastore for a range starting from next ledger after checkpoint ledger sequence and up to the user's target sequence or unbounded to achieve continuous current state.

It's up to the application developer to determine how they would want to store the ledger entry.

The proposal with DeriveLedgerState() is to automate that gap with an opinionated solution and provide it as out-of-box vs. build-your-own choice to applications that want ledger states and already consume or have access to CDP datastores. Am not suggesting to refactor existing algorithm implementations that compute ledger states such as in RPC(or Horizon) to use DeriveLedgerState().

[tamirms]

If we ignore the unbounded case for now and focus only on:

I meant CheckpointChangeReader usage as being a part of whole ingestion algorithm required for computing ledger states at a target sequence for a given historical sequence

Internal to that whole algorithm is the usage of CheckpointChangeReader to establish the starting state of entries in combination with replaying a subset of ensuing ledger metadata retrieved from a CDP datastore for a range starting from next ledger after checkpoint ledger sequence and up to the user's target sequence

In this comment, I describe modifications we could make to the CheckpointChangeReader so that it could work on any ledger sequence instead of only checkpoint ledgers (after implementing these modifications we should probably rename CheckpointChangeReader to LedgerEntryIterator or LedgerEntryReader to communicate that the it is no longer restricted to just checkpoint ledgers). So, I believe that addresses your concern about the complexity of using the CheckpointChangeReader for this specific case? If you think it is still difficult to use the enhanced CheckpointChangeReader (aka LedgerEntryIterator / LedgerEntryReader), could you describe the pain points that still remain?

[sreuland]

If you think it is still difficult to use the enhanced CheckpointChangeReader (aka LedgerEntryIterator / LedgerEntryReader), could you describe the pain points that still remain?

i think we are converging on same solution, refactor CheckpointChangeReader to LedgerEntryReader sounds fine rather than a new wrapper function around CheckpointChangeReader. It would take a new parameter for a LedgerBackend which would enable it to work in the 'datastore as meta source', passing in a BSB instance.

The one aspect remaining, which may be significant for clients to implement is the k-v store, with just a reader, the clients still have to juggle the stream of ledger entries on their own and convert that to a ledgerkey->ledgerentry store. Assuming a common use case most apps will have is random access reads on ledger keys.

Maybe achieving this persistence is considered beyond scope of the ingest sdk? if so, It seems likely that clients will inevitably re-invent similar solutions at this layer. One follow-on idea, could be to provide a reference implementation of deriving a ledgerkey->ledgervalue store from the new LedgerEntryReader in a new package lilkeexp\ledgeryentrystore. Alternatively, ecosystem repos may provide similar once LedgerEntryReader is available.

[tamirms]

i think we are converging on same solution, refactor CheckpointChangeReader to LedgerEntryReader sounds fine rather than a new wrapper function around CheckpointChangeReader.

👍

After thinking about this some more, I'm actually inclined towards introducing a new type, LedgerEntryReader / LedgerEntryIterator, which uses a CheckpointChangeReader and a ledger backend internally to enumerate all ledger entries that exist at a specific ledger (be it a checkpoint ledger or not) using the algorithm described in #5612 (comment) .

The CheckpointChangeReader can still be useful for those who know they are only looking at ledger entries that exist at a checkpoint ledger. In that scenario the CheckpointChangeReader is preferable because you don't need to create a ledger backend instance and pass it into the LedgerEntryReader / LedgerEntryIterator constructor.

---

The one aspect remaining, which may be significant for clients to implement is the k-v store, with just a reader, the clients still have to juggle the stream of ledger entries on their own and convert that to a ledgerkey->ledgerentry store.

I think these are two separate concerns (streaming ledger entries and storing ledger entries). Assuming a ledger entry store exists, the glue between the ledger entry reader and the ledger entry store is pretty straight forward and can be written in just a few lines of code:

reader := NewLedgerEntryReader(...)

for {
  change, err := reader.Read()
  if err == io.EOF {
    break
  } else if err != nil {
    handleErr(err)
    return
  }
  storeLedgerEntry(change.Post)
}

The module for storing ledger entries does not need to know about the module for streaming all ledger entries. Similarly, the module for streaming all ledger entries does not need to know about the module for storing ledger entries.

One follow-on idea, could be to provide a reference implementation of deriving a ledgerkey->ledgervalue store from the new LedgerEntryReader in a new package lilkeexp\ledgeryentrystore.

I definitely agree that the code for storing ledger entries should live separately and not depend on the ledger entry reader code. But, I'm not sure we should be providing a ledger entry store implementation unless we're going to be using it somewhere.

The implementation of a ledger entry store is linked to the specific query patterns you want to support. For example, horizon requires doing relational queries (e.g. find an account and all of its trustlines). On the other hand, bucketlist db is optimized for stellar-core's workflows which requires maintaining all ledger entries in a merkle tree that can be updated efficiently. Bucketlist db supports efficient key-value lookups but cannot do the relational queries that horizon requires.

So I think it would be better for each application to figure out which query patterns are important to support and then implement a ledger entry store with those goals in mind. That implementation can then be shared with others who have the same query pattern requirements.

There was some discussion of creating a bucketlist db library extracted out of stellar-core's code. I think it would make sense to do so. The bucketlist db library can be an example of a published ledger entry store implementation and any other applications who require the same query patterns supported by bucketlist db will be able to use that library.

[sreuland]

After thinking about this some more, I'm actually inclined towards introducing a new type, LedgerEntryReader

yes, agreed, won't introduce a breaking change and avoids conflating CheckpointChangeReader

So I think it would be better for each application to figure out which query patterns are important to support and then implement a ledger entry store with those goals in mind. That implementation can then be shared with others who have the same query pattern requirements.

yes, maintaining that distinction will keep the sdk clean, more aligned to purpose of providing fluent tools to build features.

There was some discussion of creating a bucketlist db library extracted out of stellar-core's code. I think it would make sense to do so. The bucketlist db library can be an example of a published ledger entry store implementation and any other applications who require the same query patterns supported by bucketlist db will be able to use that library.

This was the intended scope of query use case envisioned in this proposal, to realize a k-v store which is persistent, supports concurrency/thread-safety, and acts as a lookup against full ledger keys, maps entire ledger key to ledger data entry aka a bucket list db.

We could create a new docs writeup under Build->Apps for LedgerEntryStores that publishes example on how to build such a store from the new LedgerEntryReader