|
Implements the Google's Maglev hashing algorithm as a IPVS scheduler.
Basically it provides consistent hashing but offers some special
features about disruption and load balancing.
1) minimal disruption: when the set of destinations changes,
a connection will likely be sent to the same destination
as it was before.
2) load balancing: each destination will receive an almost
equal number of connections.
Seel also: [3.4 Consistent Hasing] in
https://static.googleusercontent.com/media/research.google.com/ko//pubs/archive/44824.pdf
v2: Add and refactor some features about MH and attach distribution test
results based on the MH's realtive weights.
I ran test program that pushes bunch of IP[:PORT] values via MH's
realtive weights algorithm.
The test program overview is:
- Send 1000 packet requests in test program per different weights test
case.
- Use same ip address and different ports per packet requests.
- IP_VS_MH_TAB_SIZE(prime number, M) is 4093.
- Use the highest 6 bits when the weight is very huge.
- It depends on IP_VS_MH_TAB_BITS.
The results are below.
1. All same weights.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32906 Masq 1 0 236
-> 10.105.181.70:32907 Masq 1 0 231
-> 10.105.181.70:32908 Masq 1 0 254
-> 10.105.181.70:32909 Masq 1 0 239
2. Relative weigths.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32914 Masq 1 0 88
-> 10.105.181.70:32915 Masq 2 0 212
-> 10.105.181.70:32916 Masq 3 0 296
-> 10.105.181.70:32917 Masq 4 0 364
3. Realtive weights with zero weight.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32947 Masq 1 0 92
-> 10.105.181.70:32948 Masq 2 0 187
-> 10.105.181.70:32949 Masq 3 0 280
-> 10.105.181.70:32950 Masq 4 0 401
-> 10.105.181.70:32951 Masq 0 0 0
3-1. Turn a destination with zero weight to 5.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32947 Masq 1 0 57
-> 10.105.181.70:32948 Masq 2 0 121
-> 10.105.181.70:32949 Masq 3 0 200
-> 10.105.181.70:32950 Masq 4 0 245
-> 10.105.181.70:32951 Masq 5 0 337
4. Divided all weights with gcd.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32926 Masq 10 0 27
-> 10.105.181.70:32927 Masq 20 0 55
-> 10.105.181.70:32928 Masq 30 0 61
-> 10.105.181.70:32929 Masq 40 0 106
-> 10.105.181.70:32930 Masq 50 0 145
-> 10.105.181.70:32931 Masq 60 0 162
-> 10.105.181.70:32932 Masq 70 0 194
-> 10.105.181.70:32933 Masq 80 0 210
5. Can not divided weights with gcd.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32934 Masq 15 0 128
-> 10.105.181.70:32935 Masq 31 0 284
-> 10.105.181.70:32936 Masq 63 0 548
6. Huge weights(each weight > M=4093).
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32937 Masq 5000 0 326
-> 10.105.181.70:32938 Masq 5000 0 331
-> 10.105.181.70:32939 Masq 5000 0 303
7. Gcd is not working with one huge weight.
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32940 Masq 64 0 31
-> 10.105.181.70:32941 Masq 127 0 55
-> 10.105.181.70:32942 Masq 2000 0 874
8. Gcd is not working and all weights are bigger then M(=4093).
IP Virtual Server version 1.2.1 (size=4096)
Prot LocalAddress:Port Scheduler Flags
-> RemoteAddress:Port Forward Weight ActiveConn InActConn
TCP 10.105.181.70:80 mh (flag-1,flag-2)
-> 10.105.181.70:32943 Masq 4127 0 128
-> 10.105.181.70:32945 Masq 8191 0 269
-> 10.105.181.70:32946 Masq 16381 0 563
Inju Song (3):
netfilter: ipvs: Add some configuration of Maglev hashing.
netfilter: ipvs: Keep latest weight of destination.
netfilter: ipvs: Refactor Maglev hashing scheduler
include/net/ip_vs.h | 1 +
net/netfilter/ipvs/Kconfig | 37 ++++++
net/netfilter/ipvs/Makefile | 1 +
net/netfilter/ipvs/ip_vs_ctl.c | 4 +
net/netfilter/ipvs/ip_vs_mh.c | 291 +++++++++++++++++++++++++----------------
5 files changed, 221 insertions(+), 113 deletions(-)
--
1.8.3.1
--
Inju Song
NAVER Corporation
--
To unsubscribe from this list: send the line "unsubscribe lvs-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
|
