Definition

It is supposed that there are N L7 pods, for each pod, it will get hash slots number Ni, the total hash slots is 256.

     ratio = Max(Ni) / Min(Ni)

    Ni = 256  (i=1,2,3...N)

    worst = Max(Ni)/256

We can conclude that the ratio is lower, the traffic is more balanced. we will focus more on the pod which takes most traffic. So here the worst value is lower, it is better. If we focus more on resource utilization, we should pay attention to the ratio value.

Hash Test

For N L7 pods, randomly assign a weight 0 < Wi <= 256 to pod Ni.

Different pods have different weights. For each Wi, we use the rendezvous algorithm with a different hash function to test the slot distribution.

Test round: 1000

Hash function: crc32/murmur32/murmur64/murmur128

Code:

package ipvs

import (
    "fmt"
    "math/rand"
    "sort"
    "strconv"
    "testing"
    "time"

    "github.com/tysonmote/rendezvous"
)

const (
    BUCKET_SIZE = 256
    REPLICAS    = 2
    TEST_ROUND  = 1000
)

type TABLE struct {
    replicas [REPLICAS]int
}

func getPercentile(data []float64, percentile int) float64 {
    number := len(data)
    sort.Float64s(data)
    return data[number*percentile/100]

}

type Result struct {
    ratio float64 // (max slots)/(min slots)
    worst float64 //  (max slots)/BUCKET_SIZE
}

func minmaxSlice(s map[int]int) (int, int) {
    max := 0
    min := 0xffff
    for _, v := range s {
        if v > max {
            max = v
        }
        if v < min {
            min = v
        }
    }
    return min, max
}

func randomGenerate(epNumber int) (int, int) {
    table := [BUCKET_SIZE]TABLE{}
    nums := make([]int, epNumber)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < epNumber; i++ {
        for {
            nums[i] = rand.Intn(BUCKET_SIZE)
            for j := 0; j < i; j++ {
                if nums[i] == nums[j] {
                    break
                }
            }
            break
        }
    }
    generateTable(nums, &table)
    result := make(map[int]int, epNumber)
    for _, v := range table {
        result[v.replicas[0]]++
    }
    min, max := minmaxSlice(result)
    //ratio := float32(max) / float32(min)
    //fmt.Printf("ids: %v, ratio: %v,  result: %+v\n", nums, ratio, result)
    return min, max
}

func generateTable(ids []int, table *[BUCKET_SIZE]TABLE) {
    hash := rendezvous.New()
    for _, id := range ids {
        hash.Add(strconv.Itoa(id))
    }
    for i := 0; i < BUCKET_SIZE; i++ {
        nodes := hash.GetN(REPLICAS, strconv.Itoa(i))
        for r := 0; r < REPLICAS; r++ {
            nodeId := 0
            if len(nodes) > r {
                nodeId, _ = strconv.Atoi(nodes[r])
            }

            if nodeId >= BUCKET_SIZE {
                nodeId = 0
            }
            table[i].replicas[r] = nodeId
        }
    }
}
func TestHash(t *testing.T) {
    var minRatio, maxRatio float64
    maxEP := 20
    p50 := make([]Result, maxEP)
    p75 := make([]Result, maxEP)
    p90 := make([]Result, maxEP)
    p99 := make([]Result, maxEP)
    fmt.Printf("L7 pods, min ratio, max ratio,  p50,  p75, p90, p99\n")
    for ep := 2; ep <= maxEP; ep++ {
        minRatio = 0xffff
        maxRatio = 1
        worst := make([]float64, TEST_ROUND)
        ratios := make([]float64, TEST_ROUND)
        for i := 0; i < TEST_ROUND; i++ {
            min, max := randomGenerate(ep)
            worst[i] = float64(max) / 256
            ratio := float64(max) / float64(min)
            //fmt.Printf("ratio: %f\n", ratio)
            ratios[i] = ratio
            if ratio > maxRatio {
                maxRatio = ratio
            } else if ratio < minRatio {
                minRatio = ratio
            }
        }
        //fmt.Printf("rations: %v\n", ratios)
        var r Result
        r.ratio = getPercentile(ratios, 50)
        r.worst = getPercentile(worst, 50)
        p50[ep-2] = r
        //fmt.Printf("p50: %v\n", p50)

        r.ratio = getPercentile(ratios, 75)
        r.worst = getPercentile(worst, 75)
        p75[ep-2] = r

        r.ratio = getPercentile(ratios, 90)
        r.worst = getPercentile(worst, 90)
        p90[ep-2] = r

        r.ratio = getPercentile(ratios, 99)
        r.worst = getPercentile(worst, 99)
        p99[ep-2] = r
        fmt.Printf("%-2v,  %-5.2f, %-5.2f,  %-5.2f,  %-5.2f,  %-5.2f, %-5.2f\n", ep, minRatio, maxRatio, p50[ep-2].ratio, p75[ep-2].ratio, p90[ep-2].ratio, p99[ep-2].ratio)
    }
    fmt.Printf("\nL7 pods, p50,  p75,  p90,  p99\n")
    for ep := 2; ep <= maxEP; ep++ {
        fmt.Printf("%-2v, %-5.2f,  %-5.2f,  %-5.2f, %-5.2f\n", ep, p50[ep-2].worst, p75[ep-2].worst, p90[ep-2].worst, p99[ep-2].worst)
    }
}

Conclusion

Murmur32 is the best hash function for our case. It is much better than crc32. But the ratio is still high, especially when the L7 pod number increases.
、