ProxySQL Binary Search Solution for Rules

By

We sometimes receive challenging requests… this is a story about one of those times.

The customer has implemented a sharding solution and would like us to review alternatives or improvements. We analyzed the possibility of using ProxySQL as it looked to be a simple implementation. However, as we had 200 shards we had to implement 200 rules — the first shard didn’t have much overload, but the latest one had to go through 200 rules and took longer.

My first idea was to use FLAGIN and FLAGOUT creating a B-Tree, but the performance was the same. Reviewing the code, I realized that the rules were implemented as a list, which means that, in the end, all the rules were going to be processed until hit with the right one and FLAGIN is used just to filter out.

At that point, I asked, what could I do? Is it possible to implement it differently? What is the performance impact?

One Problem, Two Solutions

I think that it would be worthy to clarify again that I have to change the code because I found no performance gain with the current implementation. This means that writing the rules to take the advantage of the binary search took me halfway, and implementing the rules with Map allowed the performance gain expected, as now we are jumping to the right rule chain and skipping the others.

Solution

I decided to change the ProxySQL code to use a different structure (Map) to store the rules and when the FLAGOUT is there, start that path. This is 100% proof of concept, do not use the code in this repo on production as it is not thoroughly tested and might have several bugs. However, we can trust the behavior and results of the test under the scenario that I’m presenting.

Base case

Using ProxySQL without any change and with 1 rule per shard will be our base case. This means, that it is going to evaluate 1 rule for shard-1 but 200 evaluations need to be made to reach the rule for shard-200.

In this case, the rules will be like this:

insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 000',1,0);
insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 001',1,0);
insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 002',1,0);
insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 003',1,0);

Binary search use case

In order to reduce the number of evaluations, I decided to use the divide and conquer idea. I created the rules in this way:

replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* [0-1]',0,01,0,999);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 0' ,01, 0,1, 0);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 1' ,01, 0,1, 1);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 2' , 0, 0,1, 2);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 3' , 0, 0,1, 3);

will be more rules to write but the number of evaluations are less and evenly distributed:

Shard | Amount of Evaluations
0     | 2
1     | 3
2     | 2
3     | 3

Rule evaluation

Take into account that evaluating a rule means basically reading the parameters and comparing them. This might not be hard work if you have a few amounts of rules, but we had 200 shards, so we need at least 200 rules. Let’s compare how many evaluations are being made on each case:

root@ProxySQL_git:~/git/proxysql# grep "Evaluating rule_id" /var/lib/proxysql/proxysql.log | wc -l
202000
root@ProxySQL_git:~/git/proxysql# grep "Evaluating rule_id" /var/lib/proxysql/proxysql.log | wc -l
 37600
The first number is the number of evaluations that ProxySQL needs using the List, the second is using the B-Tree solution and Map. As you can see, we are evaluating 5.3 times less.

Tests

For the test, I created 3 EC2 instances with these roles:

  • App simulator which is going to run a script that simulates 32 threads running 2M queries like this:
/* 000 */ select 'test' from dual;
  • ProxySQL Server which is going to run both version with the best solution each.
  • Percona Server

The original version of ProxySQL was able to execute 36k of queries per second and using Map and B-Tree was able to execute 61k of queries per second, a 40% increase in throughput.

Another thing to consider is the load in the ProxySQL server for both tests:

In the first picture, we see that the server is reaching 90% of CPU usage but using Map and B-Tree is less than 60%.

Conclusions

I think this proof of concept showed 3 important facts:

  1. That ProxySQL is an amazing tool that is still growing.
  2. The performance penalty using a large number of rules could be reduced.
  3. Writing rules taking into account the binary search might not be only a solution for sharding, could be used for queries hashes for Read-Write splitting.

by David Ducos via Percona Database Performance Blog

Comments

Post a Comment