LVS
lvs-devel
Google
 
Web LinuxVirtualServer.org

[PATCHv2 ipvs-next 0/3] ipvs: Add Maglev consistent hashing

To: lvs-devel@xxxxxxxxxxxxxxx
Subject: [PATCHv2 ipvs-next 0/3] ipvs: Add Maglev consistent hashing
Cc: Julian Anastasov <ja@xxxxxx>, Simon Horman <horms@xxxxxxxxxxxx>, Wensong Zhang <wensong@xxxxxxxxxxxx>
From: Inju Song <inju.song@xxxxxxxxxxxxx>
Date: Sun, 25 Feb 2018 15:41:47 +0900
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

<Prev in Thread] Current Thread [Next in Thread>