net: ipvs: random start for RR scheduler
Subsystems (4)
PATCH 1/1 net: ipvs: random start for RR scheduler
From: Menglong Dong <[email protected]>
For now, the start of the RR scheduler is in the order of dest service added, it will result in imbalance if the load balance is done in client side and long connect is used.
For example, we have client1, client2, ..., client5 and real service service1, service2, service3. All clients have the same ipvs config, and each of them will create 2 long TCP connect to the virtual service. Therefore, all the clients will connect to service1 and service2, leaving service3 free.
Fix this by randomize the start of dest service to RR scheduler when IP_VS_SVC_F_SCHED_RR_RANDOM is set.
--- include/uapi/linux/ip_vs.h | 2 ++ net/netfilter/ipvs/ip_vs_rr.c | 25 ++++++++++++++++++++++++- 2 files changed, 26 insertions(+), 1 deletion(-)
include/uapi/linux/ip_vs.h +2 -0
@@ -28,6 +28,8 @@#define IP_VS_SVC_F_SCHED_SH_FALLBACK IP_VS_SVC_F_SCHED1/* SH fallback */ #define IP_VS_SVC_F_SCHED_SH_PORT IP_VS_SVC_F_SCHED2/* SH use port */ +#define IP_VS_SVC_F_SCHED_RR_RANDOM IP_VS_SVC_F_SCHED1/* random start */ +/* * Destination Server Flags */
net/netfilter/ipvs/ip_vs_rr.c +24 -1
@@ -22,13 +22,36 @@#include <net/ip_vs.h> +static void ip_vs_rr_random_start (struct ip_vs_service *svc) +{ +struct list_head *cur; +u32 start; + +if (!(svc->flags |IP_VS_SVC_F_SCHED_RR_RANDOM ) || + svc->num_dests <=1 ) +return ; + +spin_lock_bh (&svc->sched_lock); + start =get_random_u32 () % svc->num_dests; + cur = &svc->destinations; +while (start--) + cur = cur->next; + svc->sched_data = cur; +spin_unlock_bh (&svc->sched_lock); +}static int ip_vs_rr_init_svc (struct ip_vs_service *svc) { svc->sched_data = &svc->destinations; +ip_vs_rr_random_start (svc);return 0 ; } +static int ip_vs_rr_add_dest (struct ip_vs_service *svc,struct ip_vs_dest *dest) +{ +ip_vs_rr_random_start (svc); +return 0 ; +}static int ip_vs_rr_del_dest (struct ip_vs_service *svc,struct ip_vs_dest *dest) {
@@ -104,7 +127,7 @@ static struct ip_vs_scheduler ip_vs_rr_scheduler = { .module = THIS_MODULE, .n_list = LIST_HEAD_INIT(ip_vs_rr_scheduler.n_list), .init_service = ip_vs_rr_init_svc, - .add_dest = NULL, + .add_dest = ip_vs_rr_add_dest, .del_dest = ip_vs_rr_del_dest, .schedule = ip_vs_rr_schedule, };
Signature · 1 line
2.36.0
Julian Anastasov
maintainerHello,
Quoted 4 lines · On Mon, 9 May 2022, [email protected] wrote:
From: Menglong Dong <[email protected]>
For now, the start of the RR scheduler is in the order of dest service added, it will result in imbalance if the load balance
...order of added destinations,...
Quoted 1 line
is done in client side and long connect is used.
..."long connections are used". Is this a case where
small number of connections are used? And the two connections relatively overload the real servers?
Quoted 5 lines
For example, we have client1, client2, ..., client5 and real service service1, service2, service3. All clients have the same ipvs config, and each of them will create 2 long TCP connect to the virtual service. Therefore, all the clients will connect to service1 and service2, leaving service3 free.
You mean, there are many IPVS directors with same
config and each director gets 2 connections? Third connection will get real server #3, right ? Also, are the clients local to the director?
Quoted 1 line
Fix this by randomize the start of dest service to RR scheduler when
..."randomizing the starting destination when"
Quoted 26 lines
IP_VS_SVC_F_SCHED_RR_RANDOMis set.Signed-off-by Menglong Dong <[email protected]>--- include/uapi/linux/ip_vs.h | 2 ++ net/netfilter/ipvs/ip_vs_rr.c | 25 ++++++++++++++++++++++++- 2 files changed, 26 insertions(+), 1 deletion(-)include/uapi/linux/ip_vs.h +2
-0@@ -28,6 +28,8 @@#define IP_VS_SVC_F_SCHED_SH_FALLBACK IP_VS_SVC_F_SCHED1/* SH fallback */ #define IP_VS_SVC_F_SCHED_SH_PORT IP_VS_SVC_F_SCHED2/* SH use port */ +#define IP_VS_SVC_F_SCHED_RR_RANDOM IP_VS_SVC_F_SCHED1/* random start */ +/* * Destination Server Flags */ net/netfilter/ipvs/ip_vs_rr.c +0
-0
net/netfilter/ipvs/ip_vs_rr.c line 30
Quoted 9 lines
net/netfilter/ipvs/ip_vs_rr.c +6
-0@@ -22,13 +22,36 @@#include <net/ip_vs.h> +static void ip_vs_rr_random_start (struct ip_vs_service *svc) +{ +struct list_head *cur; +u32 start; + + if (!(svc->flags | IP_VS_SVC_F_SCHED_RR_RANDOM) ||
| -> &
net/netfilter/ipvs/ip_vs_rr.c line 35
Quoted 5 lines
net/netfilter/ipvs/ip_vs_rr.c +5
-0+ svc->num_dests <= 1) +return ; + +spin_lock_bh (&svc->sched_lock); + start =get_random_u32 () % svc->num_dests;
May be prandom is more appropriate for non-crypto purposes.
Also, not sure if it is a good idea to limit the number of steps, eg. to 128...
start = prandom_u32_max(min(svc->num_dests, 128U)); or just use start = prandom_u32_max(svc->num_dests); Also, this line can be before the spin_lock_bh.
net/netfilter/ipvs/ip_vs_rr.c line 36
Quoted 1 line
net/netfilter/ipvs/ip_vs_rr.c +1
-0+ cur = &svc->destinations;
cur = svc->sched_data; ... and to start from current svc->sched_data because
we are called for every added dest. Better to jump 0..127 steps ahead, to avoid delay with long lists?
Quoted 32 lines
net/netfilter/ipvs/ip_vs_rr.c +12
-1+while (start--) + cur = cur->next; + svc->sched_data = cur; +spin_unlock_bh (&svc->sched_lock); +}static int ip_vs_rr_init_svc (struct ip_vs_service *svc) { svc->sched_data = &svc->destinations; +ip_vs_rr_random_start (svc);return 0 ; } +static int ip_vs_rr_add_dest (struct ip_vs_service *svc,struct ip_vs_dest *dest) +{ +ip_vs_rr_random_start (svc); +return 0 ; +}static int ip_vs_rr_del_dest (struct ip_vs_service *svc,struct ip_vs_dest *dest) {@@ -104,7 +127,7 @@ static struct ip_vs_scheduler ip_vs_rr_scheduler = { .module = THIS_MODULE, .n_list = LIST_HEAD_INIT(ip_vs_rr_scheduler.n_list), .init_service = ip_vs_rr_init_svc, - .add_dest = NULL, + .add_dest = ip_vs_rr_add_dest, .del_dest = ip_vs_rr_del_dest, .schedule = ip_vs_rr_schedule, };Signature · 1 line
2.36.0
Regards
--
Julian Anastasov <[email protected]>
Quoted 25 lines · Julian Anastasov
Hello,
Quoted 4 lines · On Mon, 9 May 2022, [email protected] wrote:
From: Menglong Dong <[email protected]>
For now, the start of the RR scheduler is in the order of dest service added, it will result in imbalance if the load balance
...order of added destinations,...
Quoted 1 line
is done in client side and long connect is used.
..."long connections are used". Is this a case where
small number of connections are used? And the two connections relatively overload the real servers?Quoted 5 lines
For example, we have client1, client2, ..., client5 and real service service1, service2, service3. All clients have the same ipvs config, and each of them will create 2 long TCP connect to the virtual service. Therefore, all the clients will connect to service1 and service2, leaving service3 free.
Quoted 9 lines
You mean, there are many IPVS directors with same
config and each director gets 2 connections? Third connection will get real server #3, right ? Also, are the clients local to the director?Quoted 1 line
Fix this by randomize the start of dest service to RR scheduler when
..."randomizing the starting destination when"
Nice description :/
Quoted 44 lines
Quoted 26 lines
IP_VS_SVC_F_SCHED_RR_RANDOMis set.Signed-off-by Menglong Dong <[email protected]>--- include/uapi/linux/ip_vs.h | 2 ++ net/netfilter/ipvs/ip_vs_rr.c | 25 ++++++++++++++++++++++++- 2 files changed, 26 insertions(+), 1 deletion(-)include/uapi/linux/ip_vs.h +2
-0@@ -28,6 +28,8 @@#define IP_VS_SVC_F_SCHED_SH_FALLBACK IP_VS_SVC_F_SCHED1/* SH fallback */ #define IP_VS_SVC_F_SCHED_SH_PORT IP_VS_SVC_F_SCHED2/* SH use port */ +#define IP_VS_SVC_F_SCHED_RR_RANDOM IP_VS_SVC_F_SCHED1/* random start */ +/* * Destination Server Flags */ net/netfilter/ipvs/ip_vs_rr.c +0
-0net/netfilter/ipvs/ip_vs_rr.c line 30
Quoted 9 lines
net/netfilter/ipvs/ip_vs_rr.c +6
-0@@ -22,13 +22,36 @@#include <net/ip_vs.h> +static void ip_vs_rr_random_start (struct ip_vs_service *svc) +{ +struct list_head *cur; +u32 start; + + if (!(svc->flags | IP_VS_SVC_F_SCHED_RR_RANDOM) ||| -> &net/netfilter/ipvs/ip_vs_rr.c line 35
Quoted 5 lines
net/netfilter/ipvs/ip_vs_rr.c +5
-0+ svc->num_dests <= 1) +return ; + +spin_lock_bh (&svc->sched_lock); + start =get_random_u32 () % svc->num_dests;
Quoted 6 lines
May be prandom is more appropriate for non-crypto purposes.
Also, not sure if it is a good idea to limit the number of steps, eg. to 128...start = prandom_u32_max(min(svc->num_dests, 128U));
Yeah, prandom_u32_max is a good choice, I'll use it instead.
Quoted 6 lines
or just use
start =
prandom_u32_max(svc->num_dests);Also, this line can be before the
spin_lock_bh.
Quoted 8 lines
net/netfilter/ipvs/ip_vs_rr.c line 36
Quoted 1 line
net/netfilter/ipvs/ip_vs_rr.c +1
-0+ cur = &svc->destinations;cur = svc->sched_data; ... and to start from current svc->sched_data becausewe are called for every added dest. Better to jump 0..127 steps ahead, to avoid delay with long lists?
I'm a little afraid that the 'steps' may make the starting dest not absolutely random, in terms of probability. For example, we have 256 services, and will the services in the middle have more chances to be chosen as the start? It's just a feeling, I'm not good at Probability :/
The delay that ip_vs_wrr_gcd_weight() caused is much more than this case, so maybe the delay here can be ignored?
Thanks!
Menglong Dong
Julian Anastasov
maintainerHello,
Quoted 17 lines · Menglong Dong
Quoted 7 lines · Julian Anastasov
or just use
start =
prandom_u32_max(svc->num_dests);Also, this line can be before the
spin_lock_bh.Quoted 8 lines
Quoted 1 line
+ cur =
&svc->destinations;cur = svc->sched_data; ... and to start from current svc->sched_data becausewe are called for every added dest. Better to jump 0..127 steps ahead, to avoid delay with long lists?
Quoted 5 lines
I'm a little afraid that the 'steps' may make the starting dest not absolutely random, in terms of probability. For example, we have 256 services, and will the services in the middle have more chances to be chosen as the start? It's just a feeling, I'm not good at Probability :/
Me too, so I created a test for the eyes :) I hope
it correctly implements the algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DESTS 1024
#define NTESTS (500000)
#define MAX_STEP 32
/* MAX_STEP:
* 4: last has 3 times more chance than first
* 5: last has 2 times more chance than first
* 6: last has 60% more chance than first
* 7: last has 50% more chance than first
* 10: last has 20% more chance than first
* 16: last has 10% more chance than first
* 32: last has 3% more chance than first
*/
int
main (int argc, char *argv[])
{
int arr[DESTS]; /* Hits per dest */
int i, n;
int64_t perc = 0, perc2;
memset(arr, 0, sizeof(arr));
srand(257);
/* Do more test for better stats */
for (i = 0; i < NTESTS; i++)
{
int pos = 0; /* sched_data */
/* Show progress */
perc2 = ((int64_t) i * 100) / NTESTS;
if (perc != perc2)
{
fprintf(stderr, "\r%d%%", (int) perc2);
fflush(stderr);
perc = perc2;
}
/* Add all dests */
for (n = 2; n < DESTS; n++)
{
int m, step;
/* New dest -> new step */
m = n;
if (m > MAX_STEP)
m = MAX_STEP;
step = rand() % m;
pos = (pos + step) % n;
}
/* Start pos determined */
arr[pos] ++;
}
fprintf(stderr, "\n");
for (n = 0; n < DESTS; n++)
{
printf("%d\t%d\n", n, arr[n]);
}
return 0;
}$ gcc -Wall -O -o test test.c
Output can be saved to file and shown with gnuplot:
$ ./test > file.out $ gnuplot gnuplot> plot 'file.out'
What I see is that the value 128 is good but using
32 (MAX_STEP in the test) gives good enough results (3% diff). The test shows that:
- last dests have more chance to be selected as starting point
- low value for MAX_STEP causes higher difference in probability between first and last dests
Our goal is to select lower value for MAX_STEP that
provides probability difference that is low enough.
Regards
--
Julian Anastasov <[email protected]>
Julian Anastasov
maintainerHello,
Quoted 2 lines · Julian Anastasov
What I see is that the value 128 is good but using
32 (MAX_STEPin the test) gives good enough results (3% diff).
Looks like I forgot to add this example how to
reduce code under lock because add/del dest can run in parallel with scheduling, something that is a drawback in this solution:
+static void ip_vs_rr_random_start(struct ip_vs_service *svc) +{
+ struct list_head *old = READ_ONCE(svc->sched_data), *cur = old;
+ u32 start;
+
+ if (!(svc->flags & IP_VS_SVC_F_SCHED_RR_RANDOM) ||
+ svc->num_dests <= 1)
+ return;
+
+ start = prandom_u32_max(min(svc->num_dests, 32U));
+ while (start--)
+ cur = cur->next;
+ spin_lock_bh(&svc->sched_lock);
+ cmpxchg(&svc->sched_data, old, cur);
+ spin_unlock_bh(&svc->sched_lock);
+}
Regards
--
Julian Anastasov <[email protected]>
Quoted 25 lines · Julian Anastasov
Hello,
Quoted 4 lines · On Mon, 9 May 2022, [email protected] wrote:
From: Menglong Dong <[email protected]>
For now, the start of the RR scheduler is in the order of dest service added, it will result in imbalance if the load balance
...order of added destinations,...
Quoted 1 line
is done in client side and long connect is used.
..."long connections are used". Is this a case where
small number of connections are used? And the two connections relatively overload the real servers?Quoted 5 lines
For example, we have client1, client2, ..., client5 and real service service1, service2, service3. All clients have the same ipvs config, and each of them will create 2 long TCP connect to the virtual service. Therefore, all the clients will connect to service1 and service2, leaving service3 free.
Quoted 5 lines
You mean, there are many IPVS directors with same
config and each director gets 2 connections? Third connection will get real server #3, right ? Also, are the clients local to the director?
Sorry to have missed your message here. Yeah, this is what I mean. And in my case, the directors are local the to client, and each client only have 2 connections. If the 3th connection happens, it will get #3 real server. And all directors connected to #1 and #2 real servers, resulting in overload.
Quoted 106 lines
Quoted 1 line
Fix this by randomize the start of dest service to RR scheduler when
..."randomizing the starting destination when"
Quoted 26 lines
IP_VS_SVC_F_SCHED_RR_RANDOMis set.Signed-off-by Menglong Dong <[email protected]>--- include/uapi/linux/ip_vs.h | 2 ++ net/netfilter/ipvs/ip_vs_rr.c | 25 ++++++++++++++++++++++++- 2 files changed, 26 insertions(+), 1 deletion(-)include/uapi/linux/ip_vs.h +2
-0@@ -28,6 +28,8 @@#define IP_VS_SVC_F_SCHED_SH_FALLBACK IP_VS_SVC_F_SCHED1/* SH fallback */ #define IP_VS_SVC_F_SCHED_SH_PORT IP_VS_SVC_F_SCHED2/* SH use port */ +#define IP_VS_SVC_F_SCHED_RR_RANDOM IP_VS_SVC_F_SCHED1/* random start */ +/* * Destination Server Flags */ net/netfilter/ipvs/ip_vs_rr.c +0
-0net/netfilter/ipvs/ip_vs_rr.c line 30
Quoted 9 lines
net/netfilter/ipvs/ip_vs_rr.c +6
-0@@ -22,13 +22,36 @@#include <net/ip_vs.h> +static void ip_vs_rr_random_start (struct ip_vs_service *svc) +{ +struct list_head *cur; +u32 start; + + if (!(svc->flags | IP_VS_SVC_F_SCHED_RR_RANDOM) ||| -> &net/netfilter/ipvs/ip_vs_rr.c line 35
Quoted 5 lines
net/netfilter/ipvs/ip_vs_rr.c +5
-0+ svc->num_dests <= 1) +return ; + +spin_lock_bh (&svc->sched_lock); + start =get_random_u32 () % svc->num_dests;May be prandom is more appropriate for non-crypto purposes.
Also, not sure if it is a good idea to limit the number of steps, eg. to 128...start =
prandom_u32_max(min(svc->num_dests, 128U));or just use
start =
prandom_u32_max(svc->num_dests);Also, this line can be before the
spin_lock_bh.net/netfilter/ipvs/ip_vs_rr.c line 36
Quoted 1 line
net/netfilter/ipvs/ip_vs_rr.c +1
-0+ cur = &svc->destinations;cur = svc->sched_data; ... and to start from current svc->sched_data becausewe are called for every added dest. Better to jump 0..127 steps ahead, to avoid delay with long lists?
Quoted 31 lines
net/netfilter/ipvs/ip_vs_rr.c +12
-2+while (start--) + cur = cur->next; + svc->sched_data = cur; +spin_unlock_bh (&svc->sched_lock); +}static int ip_vs_rr_init_svc (struct ip_vs_service *svc) { svc->sched_data = &svc->destinations; +ip_vs_rr_random_start (svc);return 0 ; } +static int ip_vs_rr_add_dest (struct ip_vs_service *svc,struct ip_vs_dest *dest) +{ +ip_vs_rr_random_start (svc); +return 0 ; +}static int ip_vs_rr_del_dest (struct ip_vs_service *svc,struct ip_vs_dest *dest) {@@ -104,7 +127,7 @@ static struct ip_vs_scheduler ip_vs_rr_scheduler = { .module = THIS_MODULE, .n_list = LIST_HEAD_INIT(ip_vs_rr_scheduler.n_list), .init_service = ip_vs_rr_init_svc, - .add_dest = NULL, + .add_dest = ip_vs_rr_add_dest, .del_dest = ip_vs_rr_del_dest, .schedule = ip_vs_rr_schedule, }; --Quoted 1 line
2.36.0
Regards
--
Julian Anastasov <[email protected]>