Demystifying the Node Selector Algorithm

Pocket Network’s decentralized infrastructure is based on the input of thousands of nodes in 20+ countries, servicing around 1 billion data relays every day. Each one of those nodes needs to stay as performant as possible in order to serve the applications that rely on them. In addition, due to Pocket’s reward mechanism, the rewards are distributed based on the amount of relays performed by the node. Viewed from this lens, how can we maintain the best performance possible for the applications that use those nodes, while at the same time incentivizing and rewarding nodes that are the most performant?Before answering the question, let’s provide some background on how the Portal API works, as it is the main entry point for applications to send their requests to the network.

Portal API: The Gateway Between Apps and Nodes

The Portal API is our main gateway to connect blockchain applications with nodes. It works by routing their data requests (or “relays” as we refer to them) to Pocket’s blockchain sessions, which contain a collection of nodes that are ready to serve requests to such applications. The Portal API is built on top of Pocket’s blockchain and has several features to improve latency and stability of the relays, such as the Quality of Service (QoS) checks and the Node Selector Algorithm, the latter of which is the primary subject of this article.The Portal API leverages all the blockchain-specific details and only exposes a single set of chain-specific endpoints for developers to use. There is no need to set up SDKs or manage private keys - developers just need to simply create an “application” in the Pocket Portal, copy the endpoint(s), and start sending relays to it.

The Node Selector Algorithm Tackles Service Issues

Shortly after the launch of mainnet, in August of 2020, no checks were performed by the Portal API, so nodes within a session would serve roughly the same amount of relays regardless of their quality and health. This meant that there were a high number of errors due to misconfigured Pocket nodes, unsynced blockchain nodes, or simply nodes that simply took too long to respond.The first measure to reduce these types of errors was the addition of Quality of Service (QoS) checks for the nodes. These checks make sure that nodes are staked correctly and are currently on the latest block height of their corresponding blockchain. Adding these checks significantly reduced the amount of errors that end users were experiencing, as this guaranteed that only the healthiest nodes were allowed to perform relays.But it wasn’t enough, as users were still experiencing latency issues and nodes sometimes failed even when they passed the QoS checks. Also, some nodes were much faster than others, so an application sending a continuous amount of requests to the same application could experience vastly different response times, thus hindering the experience. More needed to be done.Enter the Node Selector Algorithm, which is the Portal API’s way of distributing relays (and subsequently rewards) between all the nodes within an application’s session.The Node Selector Algorithm was designed to address the following service issues:

Underperforming nodes: Some nodes might have issues responding to requests in a timely fashion, or could potentially stop serving relays entirely. Such nodes should not take higher precedence over nodes that are performing as expected.
Slow nodes: The location of a node is one of the most important factors in how it can be expected to perform, but in the current iteration of the protocol (v0), location is not taken into account when creating a session. This means that a session could end up with nodes from all over the world, and the farther a node is from the requesting user, the longer it will take to respond, thus reducing service quality.
Nodes failing under higher load: Some nodes work reasonably well with a set amount of requests, but start slowing down or failing once the load increases. This can happen due to several reasons, such as nodes being overloaded and thus rejecting relays, network throttling or rollovers where the pocket node hasn’t finished syncing. To reduce downtime and failures, it is important to control the amount of relays sent to them until they’re healthy again and continue normal flow.

With all this in mind, the Node Selector Algorithm allows Pocket to better rely on the most performant nodes, so applications and users can receive their service in the fastest time possible, while also rewarding the best performing nodes.

The Node Selector Algorithm: Understanding the “Raffle”

The way the algorithm works is by measuring the latency of each node’s relay response and comparing it against other nodes within the same session. The information that is gathered includes both the time taken for successful relays as well as failed relays. For failed relays, the time is not taken into account. Instead, only the number of failures is measured over the preceding 5 minutes.From these two data points, the following is determined:

The success rate (the amount of successes divided by the total relays made)
Either one of these two values:

If the number of relays is less than or equal to 20, the median success time of all the successful relays
If the number of relays is greater than 20, the weighted success time of all the successful relays. The formula for this is:

Where:

The median node time is the median time for all relays, both successes and failures
P90 node time is the 90th percentile node time
The WEIGHT_FACTOR, which is a constant set as a buffer to more adequately calculate the median success time of a node when having more relays, currently set to 0.3

The two data points above (success rate and the median/weighted success time) are recalculated every time a relay is made for all the nodes in the session that are going to be weighted. With this data, the weighting happens.To visualize the weighting process, think of a raffle. Intuitively, the more raffle tickets one possesses, the more likely they are to win the raffle, though it is of course never guaranteed. This is the case with Pocket nodes and relays too.The raffle tickets, in this case, are the number of times that a node’s ID is copied into a weighting array. The node can be copied up to 10 times for the best performing nodes, or as few as a single time for the least performant nodes.This calculation to weight a node, based on its values above, uses this formula:

The top-rated nodes are given a weightFactor of 10. Subsequent nodes are given a weightFactor based on the difference in latency (latencyDifference) between it and the previously ranked node, multiplied by the WEIGHT_MULTIPLIER. The WEIGHT_MULTIPLIER is a constant designed to produce a curve to adequately push slow nodes down the ranking, with the effect of rewarding better optimized nodes and limiting the relays that are routed to failing or slow nodes. The WEIGHT_MULTIPLIER’s current value is 35.Some more notes on weighting:

Nodes that have less than a 95% success rate are automatically given a single entry in the array.
Any node with latency under 150ms will be ranked at the top (appearing 10 times in the array) regardless of the latency value, so nodes with 10ms, 50ms, or 120ms would all be weighted the same. This is done to avoid over-favoring nodes that are running in the same infrastructure as the API and thus will always obtain lower latency. (This value is known as EXPECTED_SUCCESS_LATENCY).
If a node passes the QoS checks, but has a 0% success rate, it will be added to the array once, but it runs the risk of being flagged as a “failure node”, which won’t be considered by the Node Selector Algorithm. This condition can last up to 5 minutes, which gives the node some time to recover from any failure it may have had. The condition is removed once the node passes the QoS checks again.

Once the weighting is complete, the array is generated, and the Node Selector Algorithm will pick a node at random from the array. This node has “won the raffle”, and will perform the relay and receive the appropriate reward.Because of this process, you can see that a node with a higher QoS will have a greater chance of being picked to perform relays.Here are some other points to take into account regarding the Node Selector Algorithm:

Even though nodes with better service characteristics have a better chance of being picked, the Node Selector Algorithm still performs a random selection, so it is always possible that a less-than-optimal node will be chosen.
Not all weightFactors from 1 to 10 need to be used. A session could contain nodes all with values of 10, or a session could contain nodes all with values of 1. And note that in both of these cases, the nodes would all be equally likely to be picked. It’s only when nodes contain different service characteristics that they become more or less likely to be picked by the Node Selector Algorithm.
The Portal API is deployed in 16 different regions (corresponding to 16 AWS regions), each of them with an individual node selector, while nodes in a session can be chosen from anywhere in the world. This means that a node that happens to be closer to a region where the data is being requested will have lower latency and therefore better success there.

Sample session

The following table shows a snapshot of summarized data from a real listing of Node Selector results. The data shows ten nodes from a single session, within a single region, in the Portal API:

Ranking

Median Success Latency (in milliseconds)

Failures

Number of relays

# 1

2654

# 2

1214

# 3

1195

# 4

966

# 5

106

911

# 6

212

706

# 7

194

698

# 8

203

376

# 9

326

199

# 10

346

166

Excerpt of Node Selector results from a live session of a single region in the Portal APIThere are several factors contributing to the values shown in the table above. First, as the top 5 nodes have a latency of less than 150 milliseconds (0.15 seconds), they are automatically deemed to be in the top tier of nodes, and are entered into the array 10 times, the maximum allowed.Another factor in play is the number of failures, which has the potential to flag the node as a failure and remove it from consideration from the Node Selector for up to 5 minutes. As the #2 node had double the number of failures of the #1 node, it was flagged as a failure for double the time and thus had more time where it was not chosen at all.This table is just a snapshot, and as node performance changes all the time during a session, mainly due to load, the values shown here may have not been constant for the life of the session (which is 4 blocks or approximately 1 hour).Of course, there is also the randomness factor. A node that is higher up in the ranking may have a better chance of being chosen to perform relays, but the randomness of the selection process means that a lower-performing node may still be chosen. This explains why the number of relays decline as you go down the list, but not in a perfectly consistent pattern.

Evolution of the Node Selector Algorithm

The Node Selector Algorithm hasn’t changed much since its initial release. However, one aspect that has changed is the weighting mechanism. Due to an initial lack of QoS checks, the Node Selector was set up to punish nodes much more harshly. After the QoS checks were implemented, the punishment for failing was to not be sent to the Node Selector Algorithm at all, in order to guarantee that a node that is being weighted by the Node Selector Algorithm is a functioning, reasonably-performant one.From there on, most changes have been made to update the WEIGHT_MULTIPLIER constant in order to offer fairer reward distribution. These decisions were originally made internally as part of development by the engineering team at Pocket Foundation.One other change implemented to improve the algorithm was changing the calculation on weighting from average to median latency, as nodes that failed only once or twice ended up being disproportionately punished. By changing to median, we were able to more accurately track the overall performance of the node.In terms of deployment, when an improvement or bug fix is added, it must pass a series of unit tests residing on the API, after which it is sent to staging and a semi-production environment where a small percentage of the production traffic is sent to review the behavior and results. If all goes as expected, it is then deployed to production.

Quality Assurance Process

The process that takes a feature, bug fix, or refactoring from development to production is similar to how other features are developed within Pocket Network’s engineering team. Once the code changes are made, they must pass a series of steps before going live into production.These steps are:

The team starts with local testing and writing unit tests. They check if the tests are passing and relays coming through. Depending on the situation, additional logging may be added to assert whether the ranking results make sense.
A pull request is made targeting the develop branch. It gets reviewed by at least one engineer from the backend team.
If no revisions are needed or all requested changes are solved, then the pull request is merged and another one is created on the staging branch.
The staging pull request needs to be reviewed and approved again by at least one engineer from the backend team.
If approved, it gets merged, released, and tested on the staging branch.
Once the change is manually tested in staging and everything is verified to be working, the feature is submitted to the “semi-production” environment (known as canary).
The “semi-production” environment canary is actively monitored by at least one member of the backend team by diverting a small percentage of real traffic to the environment and observing the behavior. If any issue is found, then the traffic is halted and engineers will investigate the issue.
If everything went well on canary, then a pull request is created for production. This must be reviewed by a Senior Engineer that has permission to release to production. At this point, it's been tested many times, so few issues are found here.
If the Senior Engineer approves the feature, then it gets released to every region simultaneously. From there, at least two engineers must be available to monitor the release for the next two hours to look for any anomalies or errors.
Once this timeframe has passed, then the engineers conclude manual monitoring and continue to rely on automatic tools to report any issue.

Improving our Processes and Communication

While updates to the Node Selector Algorithm may be infrequent, we are making much larger changes regarding how we communicate those changes to the community. Some of these changes include:

The addition of bots on the community servers that inform the users each time the Node Selector Algorithm has been updated, including details of what changes were made.
More detailed descriptions of the changes made linked to the code itself, specifically regarding the nature of the change, whether it affects the algorithm, and how. In addition, we will provide examples of the new behavior.
A stronger set of Unit Tests to better ensure the expected results based on a variety of different circumstances, such as varying latencies/failure rates and sporadic bursts of relays for some applications.
Improving the pre-production environment with internal tools used to test the behavior of the Node Selector Algorithm under production-like conditions before doing a full push to either semi-production or production.

All of these process changes are aimed to be open and public, so that community members can give feedback on the implementation and results. After all, we share the same goals: to provide the best service possible to our applications, while rewarding fairly the nodes that accomplish that.We hope that this gives you a better understanding of how not only the Node Selector Algorithm works, but also how rewards are allocated to nodes. The Node Selector Algorithm code is open-source and available on GitHub. We invite you to review the code and join the conversation on our discussion forum if you have suggestions on how we can improve our algorithms.