Table Store (aka ORM) Package

[aaronc]

This is linked to meta-issue #7096.

Summary

This issue proposes a new table-store package which allows for automatic secondary index creation. The code for this already exists here: https://github.com/regen-network/cosmos-modules/tree/master/incubator/orm but it is not part of the SDK.

Problem Definition

Oftentimes modules want to create secondary indexes for data being stored. A good example is x/staking (see x/staking/types/keys.go). As can be seen in the x/staking example, it is fairly complex to do this manually.

Proposal

The table-store package would provide a framework for creating effectively database tables with primary and secondary keys.

The current implementation of this is called orm (for object-relational mapping), but a more correct name is likely table-store. Instead of a key-value store, we actually have a relational database table store.

Currently this implementation has support for:

• auto-incrementing uint64 primary keys
• natural primary keys
• uint64 secondary indexes
• []byte secondary indexes
• multi-key secondary indexes

More functionality could be added as needed.

This is related to the proposed store decoders in #9158. The table store decoder would automatically implement the interface described there so that modules using the table store would be automatically indexable in databases like PostgreSQL.

/cc @blushi @i-norden @robert-zaremba

[tac0turtle]

This has come up with 2-3 in the past couple weeks. I would love to see this land in the sdk. Are there more docs I can read on it, I would like to start using the package sooner rather than later.

[aaronc]

Sorry, docs aren't great yet. We really need to work on this. The best code examples are here I think: https://github.com/regen-network/regen-ledger/blob/master/x/group/server/server.go

[fedekunze]

I concur with the problem outlined by this discussion. There's a lack of information on how keys should be structured, not only for the purpose of creating second idxs, but also in terms of format and ordering of its components. This ordering affects how range iteration is performed and is usually very error-prone or underperforming due to the lack of docs.

I agree with @marbar3778 that this should definitely be included on the SDK and that we should create a comprehensive doc for keys and prefixing as the acceptance criteria so that other apps can also follow the standards we set for the SDK.

[aaronc]

Yeah constructing multi-part keys is pretty complex and shouldn't need to be figured out every time from scratch.

[aaronc]

Proposed Upgrades to ORM

I’d like to propose a future direction that is a hybrid of the current ORM and AIB’s State Object proposal. /cc @fdymylja @jgimeno @robert-zaremba @blushi

Store Objects/Tables in proto files

• all “store objects” or tables would be defined in proto files and have a dedicated proto message
• primary key field(s) and indexes depending on the object’s fields are defined using protobuf files, ex:

message Balance {
    option (cosmos_proto.table) = {
        primary_key: "address, denom"
        index: "denom, address"
    };

    bytes address = 1;
    string denom = 2;
    string amount = 3;
}

Auto-generated store object clients

• this generates a protobuf Client interface and implementation:

type BalanceClient interface {
	Get(ctx context.Context, address []byte, denom string, opts ...client.GetOption) (*Balance, error)

	List(ctx context.Context, opts ...client.ListOption) (BalanceIterator, error)

  	ListByAddress(ctx context.Context, address []byte, opts ...client.ListOption) (BalanceIterator, error)

  	ListByDenom(ctx context.Context, denom string, opts ...client.ListOption) (BalanceIterator, error)

	Create(ctx context.Context, balance *Balance, opts ...client.CreateOption) error

	Delete(ctx context.Context, balance *Balance, opts ...client.DeleteOption) error

	Update(ctx context.Context, balance *Balance, opts ...client.UpdateOption) error
}

This Client can automatically generate List methods based on indexes. Since we have address, denom as the primary key and denom, address as an index, ListByAddress and ListByDenom methods can be auto-generated. Other helper methods beyond what I’ve described can be generated including store decoder methods to support #9158.

Also, primary key storage should be handled efficiently via code generation, meaning:

• before storage, the primary key fields are deleted from the value (because they’re already in the key part)
• upon retrieval, the primary key fields are set in the value (coming from the key part)

I have included a context in the Client methods which isn’t in the original AIB implementation. I don’t think we can avoid context because then things like simulations can’t be implemented without thread locals. But, maybe we could move the context into a constructor/accessor (ex. BalanceStore.Open(context.Context) BalanceClient).

Proof Format

With the separation of SS (state storage) and SC (state commitment/proof) in ADR 040, I would like to propose the following formats:

• For SS, state objects/tables are identified by a one or two byte prefix as we do now, that is automatically selected either by code generation or at runtime
• SS primary key and index parts are stored efficiently for ordered prefix scans, i.e. key parts except the last part follow these rules:
  • bytes are length prefixed
  • string is null-terminated
  • integer types (i.e. uint32, uint64, etc.) are stored as 4 or 8 big-endian
• SS values are protobuf binary as we do now
• SC keys (before hashing are): <fully-qualified-message-name>/<key-part-1/key-part-2/… where:
  • fully-qualified-message-name is the proto message URL (ex. cosmos.bank.store.v1.Balance
  • key-part-1 is a string encoding of the key part (hex for bytes)
• SC values (before hashing) are either deterministic proto binary or proto JSON. Proto JSON may be valuable because clients will need to use deterministic proto JSON for SIGN_MODE_TEXTUAL and thus this will be a common client-friendly format
• only primary keys, not indexes are stored in SC

I believe this will allow for a much better client UX for proofs because the:

• proof format will be well-defined by the protobuf file and not depend on the one or two byte table prefix but instead full proto message URL
• clients won’t need worry about length-prefixing, big-endianness, etc. for key parts, just string encoding
• clients will be able to reuse the same infrastructure for SIGN_MODE_TEXTUAL (if we use Proto JSON)

Other possibilities

• auto-generated REST or even gRPC service endpoints (we'd need to generate the service definition but I think that's okay...)
• memory cache of pre-decoded objects (that still follows consensus gas rules)
• encoding of proto JSON proof in separate go routine

[fdymylja]

Basically, I'm wondering if we should really use the main storage for indexes. Alternative is that a module will have an it's own DB for additional data. Ref: regen-network/regen-ledger#304

I think this will make dealing with caches more complex, especially if we plan to have ORM as a store in multistore.

[aaronc]

I don't see a reason why we should use different keys for SC than SC? I think it's better to use the same key - we can easily query storage without doing extra transformation. Even though we are hashing a key SC, using same key provides more consistency.

The key structure can be customizable by an object (by implementing an interface method). For example: it may be possible that we don't need to use key prefixes (if a key is not composed, or all prefix parts have fixed length).

So a few design goals I'm holding in mind are:

• the .proto file should be the source of truth for key composition in 90% of the cases (what I've described above actually I think will cover 100% of the cases I've encountered in the SDK)
• the key structure should be code generated to make it more efficient - as you've pointed out @robert-zaremba, manually composing the key wastes space because the primary key is stored in both the key and value of SS
• the format for SS should be storage and query efficient which in my mind means a binary prefix for object stores just like we have in the SDK, not a long string like cosmos.bank.v1.Balance

With that in mind, we could make the SC format identical to the SS format which will mean that clients need to:

• do binary key composition (not too big a deal)
• know the binary store prefix, which is a bit cumbersome because I cannot think of a clean way to statically generate them so clients would need to query state to learn the binary prefix for cosmos.bank.v1.Balance
• delete the primary key from the value before serializing because remember we're making SS values efficient - this in my mind is the most cumbersome step

What I'm proposing would be a standard that allows any client to take a storage object defined in protobuf and know exactly what the proof should look like without a) needing to lookup a stateful binary prefix and b) do special efficiency-oriented binary encodings. IMHO there are enough benefits to this to merit a different SC vs SS encoding.

[aaronc]

This is a good point for having the low level interface. However, I'm still not confident, if an auxiliary, module level DB will be better for that kind of indexes.
@robert-zaremba can you say a little bit more about what you mean?

@aaronc It's related to this discussion #9451 (comment)
Basically, I'm wondering if we should really use the main storage for indexes. Alternative is that a module will have an it's own DB for additional data. Ref: regen-network/regen-ledger#304

I think this isn't that different from what I'm proposing by allowing SS and SC to be different, with one use case being not encoding indexes in SC. I would also note that a lot of these indexes are needed for the state machine.

[robert-zaremba]

What I'm proposing would be a standard that allows any client to take a storage object defined in protobuf and know exactly what the proof should look like without

You, mean what the query will look like? The proof is a list of pseudo-random hashes.
How about this: client, to query an object X, will need to use the following API: QueryObj(typeURL: string, key: string, withProof: bool)? The backend will convert typeURL to the key prefix (binary) and will use the same key for both SC and SS. The client won't have a direct access to the store anyway.

NOTE: The value stored in the proof leaf is hash(key || value) - which is the key and the value we save in the SS. Now, if we return a different value to the user, s/he won't be able to verify it.

[robert-zaremba]

I would also note that a lot of these indexes are needed for the state machine.

I know. Indexes are not needed for the consensus though. If one node will have wrong index he will process transactions differently and the state will be different. So the index correctness doesn't need to be checked explicitly. Although we can still commit an index commitment to the main store. My general approach for regen-network/regen-ledger#304 is that we have more choices for designing indexes. Indexes required for processing efficiently a transaction can be in the main store or operated on more efficient DB managed by a module. Indexes for processing user queries should be all off-chain.

[fdymylja]

The API I was experimenting with for ORM Objects was a fastpath implementation of protoreflect.

Given the protobuf ORM Object definition:

syntax="proto3";

package cosmos.base.orm.v1alpha1;

option go_package = "github.com/cosmos/cosmos-sdk/orm/types";
// SchemaDefinition defines an ORM object schema definition
message SchemaDefinition {
  // singleton marks if the object is a singleton
  // by singleton we mean an object of which only
  // one instance can exist in the object namespace.
  // if singleton is set to true, primary_keys and
  // secondary_keys must be empty and autoincrement must
  // be set to false.
  bool singleton = 1;
  // auto_id marks associates the object with an unique
  // ID which is auto generated and increased each time
  // a new object is created in the namespace.
  // If auto_id is set to true, singleton must be false
  // and primary_keys must be empty, there can be secondary keys.
  bool auto_id = 2;
  // primary_keys marks the fields that are used to
  // to save the concrete object.
  repeated string primary_keys = 3;
  // secondary_keys marks the field of the object
  // that are used to make the object queryable
  // by its fields.
  repeated string secondary_keys = 4;
}

The following would be the StateObject interface generated by the code for objects:

// Object represents an object that can be used with ORM
type Object interface {
	codec.ProtoMarshaler
	
	// NewObject instantiates a new empty instance of Object
	NewObject() Object
	// UnsetField unsets Object's field given its protoreflect.FieldDescriptor.
	// It panics if the field is not part of the Object
	UnsetField(field protoreflect.FieldDescriptor)
	// SetField sets the Object's field given its protoreflect.FieldDescriptor.
	// It panics if the field is not part of the Object or if the
	// protoreflect.Value used is of a kind that does not match the field.
	SetField(field protoreflect.FileDescriptor, value protoreflect.Value)
	// GetField gets the Object's field given its protoreflect.FieldDescriptor
	// It panics if the field is not part of the Object.
	GetField(field protoreflect.FieldDescriptor) protoreflect.Value
}

This API is flexible enough to allow us to build the primary keys and secondary keys of object.
It allows to unset primary key fields to save up on space, it allows to set them back after unmarshalling the object.
And it's a fast implementation of protoreflection (which by the way, after some benchmarking (over New) is slower than golang's reflection).

The idea is that then given a SchemaDefinition a Schema interface is produced (for each object) based on the object type (singleton/auto_id/default) which composes primary keys, encodes the object etc.

type Schema interface {
	// Name returns the name identifier, represented as the protobuf fullname of the object
	Name() string
	// TypePrefix identifies the [2]byte prefix for the object namespace
	TypePrefix() TypePrefix
	// EncodePrimaryKey returns the primary key of the provided orm.Object
	EncodePrimaryKey(object orm.Object) []byte
	// EncodeObject encodes the orm.Object after resetting its primary key fields
	// NOTE: the fields are set back after encoding, but this means that orm.Object
	// cannot be used concurrently when is being encoded by Schema
	EncodeObject(object orm.Object) []byte
	// DecodeObject decodes the orm.Object given its primary key and value
	DecodeObject(primaryKey []byte, value[]byte, object orm.Object)
	// EncodeSecondaryKeyByName encodes the field of the provided object
	// after retrieving its value given the protoreflect.Name of the field 
	EncodeSecondaryKeyByName(fieldName protoreflect.Name, object orm.Object) []byte
	// EncodeSecondaryKey encodes the field of the provided object
	// after retrieving its value given the protoreflect.FieldDescriptor of the field
	EncodeSecondaryKey(fd protoreflect.FieldDescriptor, object orm.Object) []byte
}

For example, if balance was a StateObject, the following would be the generated interface implementation of StateObject:

type Balance struct {
   Owner []byte
   Amount string (sdk.Coin)
}

func (x Balance) GetField(fd protoreflect.FieldDescriptor) protoreflect.Value {
   switch fd.Name() {
   case "owner": 
      return protoreflect.ValueOfBytes(x.Owner)
   case "amount":
      return protoreflect.ValueOfString(x.Owner)
   default:
      panic("object blabla does not have field bla bla")      
  }
}

func (x *Balance) SetField(fd protoreflect.FieldDescriptor, value protoreflect.Value) {
  switch fd.Name() {
  case "owner":
     x.Owner = value.Bytes()
  ...   
  }
}

func (x *Balance) UnsetField(fd protoreflect.FieldDescriptor) { ... }

[fdymylja]

thoughts @aaronc @AmauryM, do you think this API would be fine? other possibilities (such as custom encoding/decoding with removal of primary key fields seemed overkill and overlapping with the work which is being done by tyler.

And also I was wondering in light of #9694 (proto customtypes)

I think this would be harder to execute and highly coupled with options which modify object internal structures.

[fdymylja]

I ran some benches to output some concrete numbers of using the protoreflect approach vs golang reflection vs two autogenerated fast reflection paths:

cpu: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz

protoreflect:
Benchmark_ProtoReflect-12 12509864 86.64 ns/op

golang reflection:
Benchmark_GoReflection-12 14749225 70.45 ns/op

reflection fast path with field descriptor:
Benchmark_FastPath-12 70583667 16.33 ns/op

reflection fast path with field name:
Benchmark_GetFieldByName-12 282286454 4.331 ns/op

[aaronc]

Awesome, so a few comments:

• we want to support multiple multi-column secondary indexes, so it would be an array of arrays conceptually. x/staking Redelegation is an example which has these complex indexes
• we are actually working on codegen for fast paths of the full protoreflect.Message API: Fast-path protoreflect.Message methods cosmos-proto#3 so that would cover all the Object code generation and we can just use Get, Set, Clear, etc.
• singleton and auto_id make sense, but we do need to specify the auto_id field. Should it just be uint64 or should we also suport random strings and bytes?

[aaronc]

Here are the other things we have in mind for the codegen: https://github.com/cosmos/cosmos-proto/issues. The goal is a very limited set of language agnostic extensions (mapped to golang types with config files) just for custom types and Anys. Ideally the orm codegen can work off of this or even be part of the same code generator.

[aaronc]

Somewhat related to #9337, we can use the design in #9156 (comment)) to define generic URIs for any on-chain entity. Maybe something like:

cosmos:<chain>:<fully-qualified-message-name>/<primary-key-part1>/<primary-key-part2>/…

Ex: cosmos:hub:cosmos.gov.state.v1.Proposal/1234

The question of how to uniquely name a chain in an IBC context is still an unsolved problem, but this sort of URI format could still be useful for off-chain linked data (i.e. RDF, JSON-LD) use cases where there is social consensus on chain names.

Also in a linked data context, we could define a JSON-LD serialization of an entity as its proto JSON serialization with a linked data context that maps every field name to a URI like cosmos:<fq-message-name>#<field-name (ex. cosmos:cosmos.gov.v1.Proposal#name).

/cc @blushi @clevinson

[robert-zaremba]

Do we need cosmos:<chain> prefix? This is only for local store, object, right? For IID does not need to be equal to a key saved in a store. If we will have foreign asset in the x/bank then I think it's cross-chain ID will be in primary-key-part1. Eg:
If Regen Chain ID is regen then regen token could be ..../bank/coin/regen:regen/...

[robert-zaremba]

Auxiliary Module Store

Linking a proposal of using a separate store for managing helper records (helper record is a record which doesn't need a state proof, but it's needed to efficiently process a transaction).
regen-network/regen-ledger#304