Function TestPartitionRing_ShuffleShard_Shuffling

ring/partition_ring_test.go:254–317

(t *testing.T)

}

func TestPartitionRing_ShuffleShard_Shuffling(t *testing.T) {
	var (
		numTenants          = 1000
		numActivePartitions = 90
		shardSize           = 3

		// This is the expected theoretical distribution of matching partitions
		// between different shards, given the settings above. It has been computed
		// using this spreadsheet:
		// https://docs.google.com/spreadsheets/d/1FXbiWTXi6bdERtamH-IfmpgFq1fNL4GP_KX_yJvbRi4/edit
		theoreticalMatchings = map[int]float64{
			0: 90.2239,
			1: 9.55312,
			2: 0.22217,
			3: 0.00085,
		}
	)

	// Initialise the ring.
	ring := createPartitionRingWithPartitions(DefaultPartitionRingOptions(), numActivePartitions, 0, 0)

	// Compute the shard for each tenant.
	partitionsByTenant := map[string][]int32{}

	for i := 1; i <= numTenants; i++ {
		tenantID := fmt.Sprintf("%d", i)

		subring, err := ring.ShuffleShard(tenantID, shardSize)
		require.NoError(t, err)

		partitionsByTenant[tenantID] = subring.PartitionIDs()
	}

	// Compute the distribution of matching partitions between every combination of shards.
	// The shards comparison is not optimized, but it's fine for a test.
	distribution := map[int]int{}

	for currTenant, currPartitions := range partitionsByTenant {
		for otherTenant, otherPartitions := range partitionsByTenant {
			if currTenant == otherTenant {
				continue
			}

			numMatching := 0
			for _, c := range currPartitions {
				if slices.Contains(otherPartitions, c) {
					numMatching++
				}
			}

			distribution[numMatching]++
		}
	}

	maxCombinations := int(math.Pow(float64(numTenants), 2)) - numTenants
	for numMatching, probability := range theoreticalMatchings {
		// We allow a max deviance of 10% compared to the theoretical probability,
		// clamping it between 1% and 0.2% boundaries.