Use a standard data encoding

[erikgrinaker]

We currently use Amino, we should use a standard serialization format instead, e.g. Protobuf. However, Protobuf does not support random access and always decodes e.g. whole nodes, which may be too expensive when we're simply traversing the tree. Other encodings may be more appropriate.

[alexanderbez]

@erikgrinaker can you elaborate on random access? What are some alternatives? What is the relationship between encoding and the merkle root? If there is none, we can consider gob with streaming APIs.

[erikgrinaker]

There will be an ADR on this.

can you elaborate on random access?

We may not always want to load the entire node, but only a field or two. For example, when we're checking if a given key exists it's not necessary to also load the value, which can be arbitrarily large. Protobuf does not support reading a single field, it always reads the entire message (or node, in this case).

Of course, the OS may use read-ahead anyway, so it may not matter - we'll have to look into it.

What are some alternatives?

As far as I know, IAVL currently uses Amino only for encoding of scalar values, which are laid out linearly. We may want to use a similar approach instead of a message-oriented one. In principle, any length-prefixed scalar encoding would do.

What is the relationship between encoding and the merkle root

I don't believe it matters, except for possibly the encoding of the integer node version. We'll have to look into it.

we can consider gob with streaming APIs

I feel like Gob is too tied to Go, I'd prefer something broader so that it's at least possible to access the data in other languages.

[alexanderbez]

I see. Well, if the encoding isn't tied to the merkle-ization of the tree, then being language specific doesn't really matter (WRT to gob). Looking forward to reading the ADR 👍

[erikgrinaker]

Well, this turned out to be a bit of a red herring, since we obviously have to load the entire serialized value from the KV store - Protobuf will do just fine.

Sorry about the noise, I'd been thinking about on-disk B-tree layouts all week.

[erikgrinaker]

So the Amino-encoding in IAVL really just wraps binary.PutVarint and related varint methods in the Go standard library, and uses varint-prefixed byte slices. It would be trivial to remove Amino (the library) and retain the same encoding using the Go standard library.

I'm not convinced that moving to Protobuf (which would be mostly the same, varints and varint-prefixed byte slices) is worth the breakage, at least not unless we're making other changes at the same time.