I have reordered the keys so that the height is the prefix and the data type is the suffix

This is neither efficient nor convenient. For example, if there are five different key types using heights as part of the key, we now have to iterate over five times as many entries (which is five times as slow and causes five times as much IO), and we have to filter out all the keys we don't want. It can also have consequences for the IO characteristics of LSM-tree datastores such as LevelDB that try to lay out on-disk data in key order.

Use prefixes, but make sure they are non-overlapping to avoid different key types conflicting with each other (either by using fixed-size prefixes or by using a key segment separator that is guaranteed to not be part of actual segments, which typically involves some sort of escaping scheme for segment encoding).

We may want to consider just using an existing encoding instead of inventing one ourselves and getting it wrong. Here's an example: https://github.com/google/orderedcode

does this still mean order is preserved?

I don't know if varints are generally lexicographically ordered, would have to research it. Little endian integers are not lexicographically ordered for large values at least.

I did think about this. My thought process around using the height as the prefix instead of the suffix, and of course I do lack a profound understanding on exactly how these database engines work (even harder when we are trying to support several), is that we want to order keys to improve performance with range operations. The only range operation we do where we can use an iterator is with pruning (as far as I understand it). With pruning we are removing the entire block for that height so having the different types (commit, partset, block meta) together means we can just iterate through the heights.

I guess alternatively, we could run an iterator for each of the types and make sure we step through them together when pruning. I'm also of the opinion that we shouldn't optimise these things for pruning but I'm not sure how ordering can improve the other operations that the blockstore or statestore does (can it lead to faster reads?).

I would also be for standardising our encoding system across all databases. When I had a glimpse they all had slightly different ways of representing the key.

The only range operation we do where we can use an iterator is with pruning (as far as I understand it). With pruning we are removing the entire block for that height so having the different types (commit, partset, block meta) together means we can just iterate through the heights.

I get your reasoning, but the reason why we're only using iterators when pruning is precisely because we don't have an ordered key encoding, so we can't use iterators for anything (because we would just get things in the wrong order).

There's a bunch of places we should be using iterators but aren't currently. Every time we fetch a range of something, or the first or last item of a sequence, we should most likely be using an iterator. This includes e.g. RPC endpoints (such as /blockchain), base/height metadata for the block store, validator set checkpointing, and many other cases.

In most cases, we are usually only interested in one type of data (for example, in the /blockchain RPC we are only interested in blocks). Having to iterate over and filter out all of the unrelated keys is inefficient and inconvenient. It is more natural to use prefixes, since this allows us to iterate over each type in isolation. Efficiency-wise this is almost always a win. Convenience-wise this is usually a win (but as you say, pruning is a counterexample).

You should also consider how we would store data that doesn't have a height with the suffix scheme -- since integers span the entire byte space, it would be impossible to add a different key of more than 8 bytes and not have it conflict with integers. These random keys would then also turn up when iterating. As a contrived example, the string metadata is 6d65746164617461 as hex, which is equivalent to the integer 7882834684426679393 -- in principle it's impossible to know whether this is height 7882834684426679393 or the metadata key, so we wouldn't know to stop iterating before we reach it.

I'm not sure how ordering can improve the other operations that the blockstore or statestore does (can it lead to faster reads?)

Yes, it's always faster to iterate over 100 keys than it is to fetch each key as a separate operation. This depends on the underlying database, but usually key lookup is O(log n) while iterating is O(1) per step. It also allows the database to optimize disk access by e.g. fetching neighboring keys stored in the same page or prefetching keys.

I would also be for standardising our encoding system across all databases. When I had a glimpse they all had slightly different ways of representing the key.

I agree. In particular, we must take care that keys will not overlap (so that e.g. validator sets suddenly turn up in the middle of block keys).

Btw, we should also keep #2907 in mind (although I don't know if it would make sense to use the same encoding there). We should use a key-encoding that allows key segments to include arbitrary bytes (which needs some sort of escaping scheme for segment separators). For example, if we choose the separator to be / we would have to convert / in segments into \/ and convert \ into \\, and take this into account when parsing the key -- however, this escaping scheme does not preserve order and could not be used. These things are tricky to get right.

There's a bunch of places we should be using iterators but aren't currently.

I had a look at the light client which uses an iterator for the first and last light block, but we don't currently have these methods in the blockstore (they could be useful for something like the RPC or for fast sync). We just keep an in memory record of the base() and height(). Do we want to add these methods to the blockstore?

You should also consider how we would store data that doesn't have a height

Yeah this also crossed my mind. With the blockstore we also map block hashes to heights (where the hash is the key). So I thought it could be possible that a hash finds itself between two heights and could get accidentally removed in the process hence I did actually add a prefix one for height related data types and another for the block hashes.

Having to iterate over and filter out all of the unrelated keys is inefficient and inconvenient. It is more natural to use prefixes,

Okay I think I was designing too specifically for pruning. What I can do is group them back to their data types (which can be a single byte prefix). I can also use binary.BigEndian.PutUint64(buf, height) so that the heights are stored in the "correct" order.

I don't think this will be varint however (I would have to play around a little more to see). My understanding is that having varint reduces the total size of all the keys which allows db's to store more of them in memory. However another part of my brain says that having fixed key sizes would make it easier to iterate through the keys (cause you know where to start reading the next key).

We should use a key-encoding that allows key segments to include arbitrary bytes

but with tendermint's dbs we know in advance what the keys are going to be so I don't think allowing for arbitrary bytes is necessary. To be honest, I haven't looked into the TxIndexer so I'm not sure what's really required for it

I had a look at the light client which uses an iterator for the first and last light block, but we don't currently have these methods in the blockstore (they could be useful for something like the RPC or for fast sync). We just keep an in memory record of the base() and height(). Do we want to add these methods to the blockstore?

We'd have to look into what makes sense in each case. But for the blockstore base and height case, we currently store this metadata explicitly (via e.g. SaveBlockStoreState) and keep updating it, which is unnecessary and brittle - we could instead just check what the actual first and last blocks are directly using an iterator (iterating over one block), and remove all of the block store state stuff.

What I can do is group them back to their data types (which can be a single byte prefix). I can also use binary.BigEndian.PutUint64(buf, height) so that the heights are stored in the "correct" order. I don't think this will be varint however.

No, this isn't varint, it's just the big endian layout. It is ordered, but just takes up a lot of space. The orderedcode project I mentioned earlier compresses integers and preserves order.

However another part of my brain says that having fixed key sizes would make it easier to iterate through the keys (cause you know where to start reading the next key).

That's true, fixed-size segments are easier because you know where they start and end, so when using variable-length segments there needs to be some (order-preserving!) way of knowing where the segment ends.

but with tendermint's dbs we know in advance what the keys are going to be so I don't think allowing for arbitrary bytes is necessary. To be honest, I haven't looked into the TxIndexer so I'm not sure what's really required for it

With the txindexer the key will include arbitrary byte slices produced by the application (specifically tag.Key and tag.Value), and we have no idea what those will contain.

As you can probably tell, this is the sort of problem that initially appears simple, but gets complicated real fast. Which is why I think we should consider just adopting some existing encoding rather than reinventing one.

As you can probably tell, this is the sort of problem that initially appears simple, but gets complicated real fast. Which is why I think we should consider just adopting some existing encoding rather than reinventing one.

I agree. I skimmed through the orderedcode library. This seems sufficient for what we're looking for right? Would we want to consider other encoding libraries.

Outside of this, the other actionable would be as you said to replace the "base" and "height" stuff in Blockstore with methods that use the iterator. I had a look at the other db's and they seem to be fine in this regard

I agree. I skimmed through the orderedcode library. This seems sufficient for what we're looking for right? Would we want to consider other encoding libraries.

I don't know, I've only looked at it for like 3 minutes, but it seems reasonable.

Something to consider is whether the encoding will ever be exposed to other systems. In that case, it would make sense to use an encoding that has support in many languages, is well-documented, and/or is trivial to implement. This might happen e.g. with the txindexer (I don't know much about it or what the use-cases are), so it might be a good idea to look into that first. As long as all use of the encoding is internal, I'd say something like orderedcode makes sense.

Outside of this, the other actionable would be as you said to replace the "base" and "height" stuff in Blockstore with methods that use the iterator. I had a look at the other db's and they seem to be fine in this regard

There's probably a ton of stuff that can be improved by using iterators, but we'd have to review the codebase to find everything. I'd just change the encoding for now, and submit separate PRs for any other improvements -- either as a concerted effort, or just opportunistically as we find them.

Something to consider is whether the encoding will ever be exposed to other systems.

In a way isn't it already exposed. There's nothing stopping me from running a separate process that queries blockstore.db right (I just have to make sure I encode the key in the same way)? This could be an option that some take for example if they want to implement their own custom querier for the txs in a blockchain

In a way isn't it already exposed. There's nothing stopping me from running a separate process that queries blockstore.db right (I just have to make sure I encode the key in the same way)? This could be an option that some take for example if they want to implement their own custom querier for the txs in a blockchain

Yeah, but I'd consider this an unofficial interface, and as such people are on their own if they want to interact with it. The official interface would be RPC.

However, with e.g. txindexer I don't know if we officially support the use-case of exporting this data into some external datastore (e.g. PostgreSQL) for the explicit purpose of having some other application consume that data.

I would, at a guess, say no. Do you think it would be a service that would be worth offering?

However, with e.g. txindexer I don't know if we officially support the use-case of exporting this data into some external datastore (e.g. PostgreSQL) for the explicit purpose of having some other application consume that data.

I think this is totally plausible and I've seen proposals of various sorts (from vulanizeDB I think?) that aim to consume indexed data and pipe it to some external set of services.

Note, in the SDK we use unique key prefixes for store keys with a / as a separator, however we don't escape or ensure all prefixes are the same length 😮

Yeah, this has bitten people before: tendermint/tm-db#6

This pull request has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

I can include the prefix within orderedcode. After fiddling around a little, it seems to be more efficient to use int64 instead of uint64