In the previous article, I described how Dubo-Go implements the routing policy function. The routing policy function is one of the important functions in Dubbo-Go, which can perform fine control on the control side of service routes. Meanwhile, at the beginning of implementation, the routing policy configuration is loaded in serial with other configurations. After obtaining the instance list of the server, the routing policy is matched with the processed routing rules to filter out the candidate instances that can be used. The complexity of processing the matching logic increases the time it takes to start the service. When a network request is matched with a routing instance through a health instance-first routing rule, it is matched through a double loop. ) list, which increases the search time. Is there a solution to these problems? The answer is yes. Therefore, this article introduces how to optimize routing policies based on routing policies by analyzing two methods, namely, asynchronous routing rule resolution and fast routing rule matching.

Figure 1 visualizes the modification point. Before the transformation, routing configuration converts user-configured routing rules into matching request processing logic through four steps of reading, parsing, filtering and matching, and finally obtains a requestable instance. The main purpose of this transformation is as follows: When a network request is matched with a routing instance through the healthy instance preference routing rule, two lists need to be intersected, namely [Healthy instance list] and [Instance list that meets the routing rule], so as to obtain the accessible instance list. If a double loop is used, the algorithm complexity increases as the amount of data in the two lists increases. Therefore, in this transformation, we choose compressed bitmap as the bottom storage, so that the matching is more efficient.

During the transformation, it was found that filtering and matching were affected mainly after the storage mode was changed. More construction logic is required to transform to a compressed bitmap when starting filtering. If synchronous execution is performed during startup, it takes a long time. So change to asynchronous execution at startup. When matching, you need to transform the input instance list into a compressed bitmap for subsequent matching.

Route rules are resolved asynchronously

Next, we’ll look at how to transform the serial route resolution rules into asynchronous ones to reduce service startup time.

To improve the efficiency of matching routing rules, routing rules are read and resolved when the application is started. As the number of route configurations to be read increases, the startup time becomes longer and longer. The operation of filtering instance list in routing rule resolution is changed to asynchronous, thus reducing the amount of information to be processed and reducing the startup time. Here you may have a small question: what is the optimization of the transformation?

In the construction method for constructing the route chain, change the synchronous build filter and filter the instance list to asynchronous build. In the constructor, an asynchronous timer is called with a listening modification method: chain.loop.

Func NewRouterChain(url * common.url) (*RouterChain, error) {...... Go chain.loop () <---- async timer and listener change method return chain, nil}Copy the code

If you go deep into the chain. Loop, you can see that there are two operations: timing and notification refresh cache.

  • Timed refresh: Used to initialize the cache.

  • Notification refresh: A cache used to receive notification of updates to update routes, structured as router -> Invokers. This action is triggered when the routing rule is dynamically added through the configuration center and the instance list is updated.

func (c *RouterChain) Loop() { ticker := time.NewTicker(timeInterval) for { select { case <-ticker.C: / / time to refresh the cache if protocol. GetAndRefreshState () {mount uildCache ()} case < - citigroup otify: / / notified, build cache mount uildCache ()}}}Copy the code

After optimization, the startup time of the service is effectively reduced.

storage

This change is to store the array, changed to a bitmap, and the bitmap used: RoaringBitmap.

The main idea is as follows: Divide a 32-bit unsigned integer into buckets by 16 bits. A maximum of 216 buckets can be created. Each bucket has one Container for storing data. When storing data, locate the bucket to be stored based on the 16 bits (K % 2^16) of the data. If the bucket does not exist, create a new bucket and put the lower 16 bits (k mod 2^16) into the container of the bucket. In other words: a bitmap is a collection of buckets.

Figure 2

In FIG. 2, respectively represent 3 data sets:

  • The first bucket holds the first 1,000 multiples of 62.

  • The second bucket stores the numbers in the range [216, 216+100].

  • The third bucket contains all the even numbers in the range [2×216, 3×216).

For more information, please visit: roaringbitmap.org/.

List of matched instances

In the specific implementation of routing, there are four main implementations: conditional routing, ConnCheck, HealthCheck and TAG. The optimization applies only to connCheck, HealthCheck, and TAG routes, but not to condition routes.

Taking conditional routing (Condition) as an example, it is necessary to match the content of routing configuration with that of metadata (including Provider and Consumer) (as shown in Figure 2), and the content of routing configuration is in the form of expression, so bitmap matching cannot be performed.

Figure 2

Taking healthCheck as an example, the list of accessible instances can be quickly obtained by judging the intersection of [Healthy instance list] and [instance list that meets routing rules] (as shown in Figure 3). In order to reduce the algorithm complexity caused by double loop, improve the performance of the program. Performance does not deteriorate significantly when the healthy instance list or routing rule instance list data volume increases.

Figure 3

The implementation of connCheck and TAG routes is consistent in the implementation idea, so I am not a burden.

conclusion

You already know how Dubo-Go is optimized when optimizing routing policies. There are many in-depth knowledge about routing policies that are worth exploring and learning. For example:

  • How is Dubo-Go conditional routing implemented?

  • How is dubo-Go tag routing implemented and its logic optimized by pooling?

The answers to these questions, you can look for them in the code.

Welcome to the community

In the public account [minister technology road] background reply keyword [dubbogo] to join the community.