On Sun, Dec 10, 2017 at 03:53:21PM +0200, Julian Anastasov wrote: > > Hello, > > On Sun, 10 Dec 2017, Inju Song wrote: > > > 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. > > > > Seel also: [3.4 Consistent Hasing] > > in https://static.googleusercontent.com/media/research.google.com/ko//pubs/archive/44824.pdf > > > > V2: Fix some methods and add features based on Julian's advice. > > It is good to see incremental changes but at the final > step it is better to see single patch with a well-formed subject, > with new version, eg: > > [PATCHv2 nf-next] ipvs: Add Maglev consistent hashing > yes. I will make next maglev patch as single but maybe there will be some patchsets for v2 If it needed(ie. add some config to Kconfig). > where the used tree is net-next, nf-next or ipvs-next. > > Few notes: > > - .upd_dest: changing weight to 0 should be ignored > but if we want to allow changing the weight from/to non-0 values > then we should save in array the latest non-0 weights for the > current dests. As it is difficult to track the dest deletions > may be we can add last_weight in struct ip_vs_dest. Then MH > will work with dest->last_weight. > I think that It needs to allow changing the weight from/to non-0 values so I will add to allow only if is non-0 values. > - it is good to have configurable table size, just like > IP_VS_SH_TAB_BITS in Kconfig. You can even use 5-6 prime numbers > like 65537 and below, if needed. Large value is not so fatal, > table is updated only when servers are added (at start), so > if one uses little differences in weights and small number of > servers the small prime number can reduce the cache usage. > As we know, the table should be able to map all possible dests > based on relative weights. To give few examples: > > - for 2 servers with same weight 5 we need 2 table entries, > one per server > > - for 2 servers with weight 5 and 10 we need 3 entries, > 1 for first server and 2 for the second server > > - But in practice we can run hundreds of servers with > relative weight difference 1-64 if number of CPUs are > considered, for example. > > - To avoid waste of memory due to kmalloc's orders we can use the > previous prime number, 65521, others can be 32749, 16381, 8191, > 4093, 2039, 1021, some no so useful values due to page size: > > - 509 (2KB with 4-byte ptr, 4KB for 8-byte ptr) > - 251 (1KB/2KB of 4KB page) > > With such primes the table should be a separate allocation. > I agress this. To avoid waste of memory and provide various prime number, it is saved with static array like below. // available prime number static int PRIMES[] = { 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071}; I want to proivde larger space then 65521, so add 131071 to last index of primes. If large value is not so fatal I think it is better in case of disruption of consistent hashing. I think It is helpful for users who have high performance machine and want more minimal disruption when destinations are add/deleted. > - when table has constant size, it can be part of the state, > as result, it will be allocated only once by ip_vs_mh_init_svc > where any errors are handled properly, any reallocations in > ip_vs_mh_reassign are unwanted because currently the errors are > ignored by the IPVS core (add_dest/upd_dest/del_dest), so > we should keep the s->permutation[] allocated. But as it is too > large, see below how to avoid s->permutation[]... > > - no need to use "inline" for ip_vs_mh_permutate and ip_vs_mh_populate, > they are used only on configuration time, better the compiler to decide > Yes. I will remove it from ip_vs_mh_permutate and ip_vs_mh_populate. > - another possible issue is that users can use crazy values for > weight, for example, 64 and 127. In such case even the gcd() > function can not help enough for something that would be 1:2 > relation. But we can warn users to use as small as possible > values for weights. If needed, we can rshift the weights, so > that only the highest 5-6 bits of the largest weight are considered. > I.e. if we find the largest weight is 2000 we see that 2000 > occupies 11 bits, so we decide to use the highest 6 bits and > rshift with 5 (11-6) all weights. All resulting weights will > fit in 6 bits. > I agree that huge weight values are considerd and rshift is good idea I think. To handle it, both rshift and last_weight are considerd. I wrote my opinion below. > - ip_vs_mh_populate allocates IP_VS_MH_TAB_SIZE ints for next[] but > later next[i] can go up to num_dests which can be above the > IP_VS_MH_TAB_SIZE. We should use IP_VS_MH_TAB_SIZE as M and > Kconfig should show the above prime numbers as options. Or > we can configure IP_VS_MH_TAB_BITS as 8..16 and to use it as > index to get the actual prime value from array: > > static int primes[] = { 251, ... 65521 }; > I will add IP_VS_MH_BITS and help message in Kconfig to able to configure it like below. config IP_VS_MH_TAB_INDEX range 8..16 default 12 // and some helpful messages. and #define IP_VS_MH_TAB_INDEX CONFIG_IP_VS_MH_TAB_INDEX - 8 #define IP_VS_MH_TAB_SIZE PRIMES[IP_VS_MH_TAB_INDEX] in header of ip_vs_mh.c > - we can avoid large allocations for s->permutation(N*M), > instead we can use: > > struct ip_vs_mh_dest_setup { > int offset; /* Starting offset */ > int skip; /* skip */ > int turns; /* weight / gcd() */ > int perm; /* next_offset */ > }; > > struct ip_vs_mh_dest_setup *dests; /* 1..num_dests */ > > dests should be allocated (-ENOMEM) and freed on > every ip_vs_mh_reassign. > > Initially, we should calculate .offset and .skip for all > dests. Then we should set dests[i].perm to dests[i].offset. > When adding weight to the picture, we can calculate greatest > common divisor with the gcd() function and then to use it for > calculating 'turns' per dest. ip_vs_wrr_gcd_weight() is a good > example how to get gcd() among all dests. > > When populating table: > > The operation 'c = permutation[i][next[i]];' becomes > > c = dests[i].perm; > > The operation 'next[i] = next[i] + 1;' becomes: > > /* Add skip, mod M */ > dests[i].perm += dests[i].skip; > if (dests[i].perm >= M) > dests[i].perm -= M; > > This should be cheaper than '% 65537'. And it is correct > because: > 1. offset is 0 .. M-1 > 2. skip is 1 .. M-1 > This is very good idea I think. It shoud be used so I will change ip_vs_mh_permutate and ip_vs_mh_populate to avoid allocating s->permutation. And re-configuring weight of dests maybe have some flow in ip_vs_init_svc and ip_vs_mh_ dest_changed like below. 1. check max weight, decide value of bits range for rshift and set last weigit to dests->last_weight with rshift. - last_weight should be set only when it is changed. - If weight is zero, skip to set last_weight 2. get gcd with all dests - maybe gcd() will use dest->last_weight value not dest->weight. 3. set offset, skip and turns in ip_vs_mh_permutate dests[i].tunrs = dest->last_weight / gcd; 4. use relative weight in ip_vs_mh_populate if (++dt_count >= dests[i].turns) { p = p -> next; dt_count = 0; i++; } and I think that the configuring weight flow need to be protected by spin_lock. > - Lets do not put limit for number of dests. We can add > only such check: > > if (svc->num_dest > IP_VS_MH_LOOKUP_SIZE) > return -EINVAL; > yes. I will add such check. > - IP_VS_MH_LOOKUP_SIZE should be replaced with IP_VS_MH_TAB_SIZE > It is will be replaced with IP_VS_MH_TAB_SIZE. > Note that I only check the implementation for problems, > I don't run any tests for the algorithm. I hope you have some > test program that pushes bunch of random IP[:PORT] values via the > algorithm and the result is correct distribution based on the relative > weights. > I alredy have some a kind of test program with destination as container and always run it when I add some features and make patches. so I will attach some result about correct distribtion at next patch if needed. > > Inju Song (3): > > netfilter: ipvs: handle memory allocation fail in mh scheduler. > > netfilter: ipvs: release refcnt and improve ip_vs_mh_reassign() > > netfilter: ipvs: change method to fill lookup table based on weight. > > > > net/netfilter/ipvs/ip_vs_mh.c | 147 +++++++++++++++++++++++++++++------------- > > 1 file changed, 101 insertions(+), 46 deletions(-) > > Regards > > -- > Julian Anastasov <ja@xxxxxx> Regards -- 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
