README
¶
#Changesets encoding
Storage changeset encoding
Storage encoding contains several blocks: Address hashes, Incarnations, Length of values, Values. AccountChangeSet is serialized in the following manner in order to facilitate binary search
Address hashes
There are a lot of address hashes duplication in storage changeset when we have multiple changes in one contract. To avoid it we can store only unique address hashes. First 4 bytes contains number or unique contract hashes in one changeset. Then we store address hashes with sum of key hashes from first element.
For example: for addrHash1Inc1Key1, addrHash1Inc1Key2, addrHash2Inc1Key1, addrHash2Inc1Key3 it stores
2,addrHash1,2,addrHash2,4
Incarnations
Currently, there are a few not default incarnations(!=1) in current state. That was the reason why we store incarnation only if it's not equal to fffffffe(inverted 1).
First part is 4 byte that contains number of not default incarnations
Then we store array of id of address hash(4 byte) plus incarnation(8 byte)
For example: for addrHash1fffffffe..., addrHash1fffffffd... it stores
1,1,fffffffd
Values lengths
The default value length is 32(common.Hash), but if we remove leading 0 then average size became ~7. Because a length of value could be from 0 to 32 we need this section to be able to find quite fast value by key.
It is contiguous array of accumulating value indexes like len(val0), len(val0)+len(val1), ..., len(val0)+len(val1)+...+len(val_{N-1})
To reduce cost of it we have three numbers: numOfUint8, numOfUint16, numOfUint32. They can answer to the question: How many lengths of values we can put to uint8, uint16, uint32.
This number could be huge if one of the contracts was suicided during block execution. Then we could have thousands of empty values, and we are able to store them in uint8(but it depends).
For example for values: "ffa","","faa" it stores 3,0,0,3,3,6
Values
Contiguous array of values.
Finally
| Value | Type | Comment |
|---|---|---|
| numOfUniqueElements | uint32 | |
| Address hashes | [numOfUniqueElements]{[32]byte+[4]byte} | [numOfUniqueElements](common.Hash + uint32) |
| numOfNotDefaultIncarnations | uint32 | mostly - 0 |
| Incarnations | [numOfNotDefaultIncarnations]{[4]byte + [8]byte} | []{idOfAddrHash(uint32) + incarnation(uint64)} |
| Keys | [][32]byte | []common.Hash |
| numOfUint8 | uint32 | |
| numOfUint16 | uint32 | |
| numOfUint32 | uint32 | |
| Values lengths in uint8 | [numOfUint8]uint8 | |
| Values lengths in uint16 | [numOfUint16]uint16 | |
| Values lengths in uint32 | [numOfUint32]uint32 | |
| Values | [][]byte |
Account changeset encoding
AccountChangeSet is serialized in the following manner in order to facilitate binary search. Account changeset encoding contains several blocks: Keys, Length of values, Values. Key is address hash of account. Value is CBOR encoded account without storage root and code hash.
Keys
The number of keys N (uint32, 4 bytes) Contiguous array of keys (N*32 bytes)
Values lengthes
Contiguous array of accumulating value indexes: len(val0), len(val0)+len(val1), ..., len(val0)+len(val1)+...+len(val_{N-1}) (4*N bytes since the lengths are treated as uint32).
Values
Contiguous array of values.
Finally
| Value | Type | Comment |
|---|---|---|
| num of keys | uint32 | |
| address hashes | [num of keys][32]byte | [num of keys]common.Hash |
| values lengthes | [num of keys]uint32 | |
| values | [num of keys][]byte |
Documentation
¶
Index ¶
- Constants
- Variables
- func EncodeAccountsPlain(blockN uint64, s *ChangeSet, f func(k, v []byte) error) error
- func EncodeStoragePlain(blockN uint64, s *ChangeSet, f func(k, v []byte) error) error
- func FromDBFormat(addrSize int) func(dbKey, dbValue []byte) (blockN uint64, k, v []byte)
- func GetModifiedAccounts(db ethdb.Database, startNum, endNum uint64) ([]common.Address, error)
- func Len(b []byte) int
- func RewindData(db ethdb.Getter, timestampSrc, timestampDst uint64, quit <-chan struct{}) (map[string][]byte, map[string][]byte, error)
- func Truncate(tx ethdb.Tx, from uint64) error
- func Walk(db ethdb.Database, bucket string, startkey []byte, fixedbits int, ...) error
- type AccountChangeSetPlain
- type Change
- type ChangeSet
- func (s *ChangeSet) Add(key []byte, value []byte) error
- func (s *ChangeSet) ChangedKeys() map[string]struct{}
- func (s *ChangeSet) Equals(s2 *ChangeSet) bool
- func (s *ChangeSet) KeySize() int
- func (s *ChangeSet) Len() int
- func (s *ChangeSet) Less(i, j int) bool
- func (s *ChangeSet) String() string
- func (s *ChangeSet) Swap(i, j int)
- type Decoder
- type Encoder
- type StorageChangeSetPlain
- func (b StorageChangeSetPlain) Find(blockNumber uint64, k []byte) ([]byte, error)
- func (b StorageChangeSetPlain) FindWithIncarnation(blockNumber uint64, k []byte) ([]byte, error)
- func (b StorageChangeSetPlain) FindWithoutIncarnation(blockNumber uint64, addressToFind []byte, keyToFind []byte) ([]byte, error)
- type Walker
Constants ¶
const (
DefaultIncarnation = uint64(1)
)
Variables ¶
var ( ErrNotFound = errors.New("not found") ErrFindValue = errors.New("find value error") )
var Mapper = map[string]struct { IndexBucket string WalkerAdapter func(cursor ethdb.CursorDupSort) Walker KeySize int Template string New func() *ChangeSet Encode Encoder Decode Decoder }{ dbutils.PlainAccountChangeSetBucket: { IndexBucket: dbutils.AccountsHistoryBucket, WalkerAdapter: func(c ethdb.CursorDupSort) Walker { return AccountChangeSetPlain{c: c} }, KeySize: common.AddressLength, Template: "acc-ind-", New: NewAccountChangeSetPlain, Encode: EncodeAccountsPlain, Decode: FromDBFormat(common.AddressLength), }, dbutils.PlainStorageChangeSetBucket: { IndexBucket: dbutils.StorageHistoryBucket, WalkerAdapter: func(c ethdb.CursorDupSort) Walker { return StorageChangeSetPlain{c: c} }, KeySize: common.AddressLength, Template: "st-ind-", New: NewStorageChangeSetPlain, Encode: EncodeStoragePlain, Decode: FromDBFormat(common.AddressLength), }, }
Functions ¶
func EncodeAccountsPlain ¶
func EncodeStoragePlain ¶
func FromDBFormat ¶
func GetModifiedAccounts ¶
GetModifiedAccounts returns a list of addresses that were modified in the block range
func RewindData ¶
func RewindData(db ethdb.Getter, timestampSrc, timestampDst uint64, quit <-chan struct{}) (map[string][]byte, map[string][]byte, error)
RewindDataPlain generates rewind data for all plain buckets between the timestamp timestapSrc is the current timestamp, and timestamp Dst is where we rewind
Types ¶
type AccountChangeSetPlain ¶
type AccountChangeSetPlain struct {
// contains filtered or unexported fields
}
type ChangeSet ¶
type ChangeSet struct {
// Invariant: all keys are of the same size.
Changes []Change
// contains filtered or unexported fields
}
ChangeSet is a map with keys of the same size. Both keys and values are byte strings.
func NewAccountChangeSetPlain ¶
func NewAccountChangeSetPlain() *ChangeSet
func NewChangeSet ¶
func NewChangeSet() *ChangeSet
func NewStorageChangeSetPlain ¶
func NewStorageChangeSetPlain() *ChangeSet
func (*ChangeSet) Add ¶
Add adds a new entry to the AccountChangeSet. One must not add an existing key and may add keys only of the same size.
func (*ChangeSet) ChangedKeys ¶
type StorageChangeSetPlain ¶
type StorageChangeSetPlain struct {
// contains filtered or unexported fields
}
func (StorageChangeSetPlain) Find ¶
func (b StorageChangeSetPlain) Find(blockNumber uint64, k []byte) ([]byte, error)
func (StorageChangeSetPlain) FindWithIncarnation ¶
func (b StorageChangeSetPlain) FindWithIncarnation(blockNumber uint64, k []byte) ([]byte, error)
Source Files