Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

TxFlow DAG pruning #116

Closed
3 tasks
MaksymZavershynskyi opened this issue Nov 30, 2018 · 1 comment
Closed
3 tasks

TxFlow DAG pruning #116

MaksymZavershynskyi opened this issue Nov 30, 2018 · 1 comment
Assignees
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one.
Milestone

Comments

@MaksymZavershynskyi
Copy link
Contributor

In the current implementation, once TxFlow message is constructed and added to DAG it is never modified, which allows safety and efficiency. However, each TxFlow message carries heavy "aggregators" -- containers that aggregate information from the parents of the message -- which we use to compute properties of the message in near-constant time without traversing the DAG, see approved_* and computed_* fields in message/mod.rs. Since these containers grow with the number of past messages the current memory usage of the DAG grows quadratically. We can solve it by pruning the aggregators of the very old messages in the DAG. It requires several changes:

  • The aggregators should be wrapped in RefCell. This will allow to have a mutable access to them even for the messages that are deep down in DAG (note, these messages are linked to their children through immutable references, so we cannot avoid RefCel).

  • The aggregators should be prunable and restorable. Meaning the containers should have function prune or some such that erases its content. If later this message is used again (e.g. a new message comes in that refers to it as parent) then we should be able to "restore" the content by recomputing it from the parents.

  • Implement "pruner" a struct that will monitor the usage of the DAG and prune rarely used messages.

Note, we might not need to implement this for MVB, because TxFlow is getting restarted for each BeaconChain block.

@MaksymZavershynskyi MaksymZavershynskyi added the C-enhancement Category: An issue proposing an enhancement or a PR with one. label Nov 30, 2018
@MaksymZavershynskyi MaksymZavershynskyi added this to the MVB milestone Nov 30, 2018
@MaksymZavershynskyi MaksymZavershynskyi self-assigned this Nov 30, 2018
@MaksymZavershynskyi
Copy link
Contributor Author

TxFlow is getting removed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one.
Projects
None yet
Development

No branches or pull requests

1 participant