Skip to content

Instantly share code, notes, and snippets.

@zsfelfoldi
Last active March 18, 2020 01:34
Show Gist options
  • Save zsfelfoldi/3c7ace895234b7b345ab4f71dab102d4 to your computer and use it in GitHub Desktop.
Save zsfelfoldi/3c7ace895234b7b345ab4f71dab102d4 to your computer and use it in GitHub Desktop.

General utilities

Weighted random selector

WeightedRandomSelect is a passive, not thread-safe data structure that holds a set of items with assigned selection weights and can quickly select one of them randomly. Weights are specified by a callback function but the last known weights are also stored in the data structure. If the weight increases compared to the last returned value then it should be explicitly updated. If it decreases then update happens automatically.

Node state machine

NodeStateMachine connects different system components operating on subsets of network nodes. It can be considered an enhanced version of les.clientPeerSet / les.serverPeerSet which it could probably replace over time. Node states are represented by uint64 bit vectors with each bit assigned to a state flag. Each state flag has a string name and the mapping is created automatically. It is possible to subscribe to subsets of state flags and receive a callback if one of the nodes has a relevant state flag changed. Callbacks can also modify further flags of the same node or other nodes. State updates only return after all immediate effects throughout the system have happened (deadlocks should be avoided by design of the implemented state logic). You can also add timeouts assigned to a certain node and a subset of state flags. If the timeout elapses, the flags are reset. If all relevant flags are reset by some other mechanism then the timer is dropped. You can also persist a subset of state flags (including associated timers) in the database.

Extra node fields can also be registered so system components can also store more complex state for each node that is relevant to them, without creating a custom peer set. Fields can be shared across multiple components if they all know the field ID. Fields are also assigned to a set of state flags and the contents of each field is only retained for a certain node as long as at least one of these flags is set (meaning that the node is still interesting to the component(s) which are interested in the given field). Persistent fields should implement rlp.Encoder and rlp.Decoder.

This logic is supposed to make interactions between components clean and easy to follow/verify. Every interaction through NodeStateMachine happens by nodes getting in or out of certain subsets. Persisting information about nodes is handled at a single place. It is also easy to design temporary states where nodes can never get stuck by setting a timeout to the flags; the state is either explicitly updated to a next one or goes back to default if something fails.

Service value measurement and token value prediction

Request types and service vectors

lespay components are independent from the underlying protocol and therefore the actual request types of the underlying protocol are abstracted out. Here we use a simple assumption that the provided service can be modeled as a scalar vector (the service vector) consisting of typical operations with a more or less predictable cost. An actual protocol request can be modeled as a linear combination of these abstract request types (so each protocol request is described as a vector). The way les currently models its requests is that a single les request or the first part of a multi-request is assigned to a single abstract lespay request type while the subsequent parts of multi-requests are mapped to another lespay request type. These abstract types are identified by string names. For example, a GetBlockHeaders request for 192 headers is translated to one "GetBlockHeaders.first" and 191 "GetBlockHeaders.rest" requests. The names are mapped to slice indices and the mapping is specified at initialization. lespay components do verify whether the mapping matches the one used when saving structures to the database and reorders or fills out missing spaces with defaults if necessary.

Reference basket

This component keeps track of the relative usage and usual relative costs of different request types on the client side. It provides two outputs: one of them is a scalar request value factor for each server: this value scales the buffer, capacity and request cost values of each server to a common scale where they are directly comparable to each other. It is calculated as the total request value of the requests in the reference basket, divided by the total request cost of the same requests, according to the server's announced cost table. The other output is the global request value vector which gives a relative value estimate for each request type, based on the relative costs of the previously used requests. The total request value in a reference basket always equals the total amount of requests. In other words, the average of request values of previously used requests (weighted according to the amounts in the reference basket) is always 1 by definition.

Request statistics are initially gathered into separate "server baskets" where values are based on the given server's pricing but scaled with the request value factor (this also means that in a server basket the sum of values is not necessarily equal to the sum of amounts). The reference basket is updated by periodically adding baskets coming from individual servers. The values of the added basket are scaled so that their sum equals their total request value (based on the previous request values of the reference basket). This means that only the relative values of the requests present in the added basket are modified. In order to make the relative prices in the added baskets relevant they should represent a sufficiently long period of the service provided by the given server. Therefore the contents of the server baskets are slowly and gradually transferred to the main reference basket instead of adding everything and resetting the server baskets in each update period.

Response time statistics

This component collects response time distribution statistics weighted with request values. It is calculated both globally and for individual servers. Individual distributions are used to calculate service value as a function of the expected response time:

serviceValue = SUM(requestValue * MAX(-1, 1-responseTime/expectedResponseTime))

Since the distribution is weighted with request values, the total service value can be calculated as the distribution vector's dot product with a weight vector that depends only on expectedResponseTime.

The global statistics can be used to suggest suitable values for expectedResponseTime and softRequestTimeout. The Timeout(ratio) function returns a suggested timeout value that would have resulted in the specified ratio of timeouts in the past.

Value tracker

The value tracker is an active component that maintains and updates request baskets and response time statistics. It also applies a long term exponential expiration to both statistics and is responsible for persisting statistics in an ethdb.KeyValueStore database.

Capacity tracker

WIP

Token value predictor

WIP

Peer selection and payment logic

WRS iterator

WrsIterator implements enode.Iterator and selects nodes randomly from a set using WeightedRandomSelect. It also uses NodeStateMachine. The selectable set is specified by two node state bit masks (requireStates and disableStates) while the selection weights are specified by a callback function.

Pre-negotiation filter

WIP

Token buyer

WIP

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment