search

aeternity / elixir-node

Elixir full node implementation of the aeternity specification
ISC License
213 stars 38 forks source link

Time complexity of accesing contract storage #668

Open gorbak25 opened 6 years ago

gorbak25 commented 6 years ago

Our contracts currently need to have the entire contract storage as an in memory map. This map is currently generated inefficiently by iterating over each key in the contract state tree. This means that after we have looked up a contract in O(log(N)) we then iterate over the whole tree in O(N) which will be to slow for production use (Ethereum currently has many milion contracts in their trees).

We have two ways of solving this issue: 1) We can solve the issue easily by implementing a wrapper or functions for accessing a particular sub-tree of a merkle patricia tree(https://github.com/aeternity/elixir-merkle-patricia-tree/issues/17). This wrapper will need to implement the Enumerable protocol and function exactly as a map.

2) We can look if we can refactor our current code in a way which avoids generating the contract storage. For instance if listing the contents of the storage is not required then all we need to do is to directly access the required keys in the tree.

Personally I would prefer method 1 as it would easier to debug contracts later(we would have access to the entire storage in the interactive shell) and wouldn't require much code refactoring here.

cytadela8 commented 6 years ago

I would sat we should:

  1. Check if epoch also has one big tree for contract data without subtrees (this is a potential compatibility issue)
  2. Implement a get_all_with_prefix function in our elixir-merkle-patricia-tree lib that will iterate only over proper part of tree and return a map. This should be simpler to creating some wrapper implementing Enumerable protocol.
  3. Write tests for the new get_all_with_prefix function

We should not create stress tests for that in any near future probably. There are many more important (and much, much easier) tests to write.

gorbak25 commented 6 years ago

@cytadela8 Epoch stores the contract storage in the same tree(https://github.com/aeternity/protocol/blob/epoch-v0.16.0/serializations.md#contract) as all contracts.

cytadela8 commented 6 years ago

I don't trust docs. Especially old ones ;) We should investigate deeper and check if it hasn't changed in current version. If it has, then this issue might not be worth solving.