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 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. - 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. - 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 - 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. - 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 }; - 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 - 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; - IP_VS_MH_LOOKUP_SIZE should 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. > 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>
