Method Get

pkg/ring/ring.go:380–464

Get returns n (or more) instances which form the replicas for the given key. This implementation guarantees: - Stability: given the same ring, two invocations returns the same set for same operation. - Consistency: adding/removing 1 instance from the ring returns set with no more than 1 difference f

(key uint32, op Operation, bufDescs []InstanceDesc, bufHosts []string, bufZones map[string]int)

// - Stability: given the same ring, two invocations returns the same set for same operation.
// - Consistency: adding/removing 1 instance from the ring returns set with no more than 1 difference for same operation.
func (r *Ring) Get(key uint32, op Operation, bufDescs []InstanceDesc, bufHosts []string, bufZones map[string]int) (ReplicationSet, error) {
	r.mtx.RLock()
	defer r.mtx.RUnlock()
	if r.ringDesc == nil || len(r.ringTokens) == 0 {
		return ReplicationSet{}, ErrEmptyRing
	}

	var (
		replicationFactor      = r.cfg.ReplicationFactor
		instances              = bufDescs[:0]
		start                  = searchToken(r.ringTokens, key)
		iterations             = 0
		maxInstancePerZone     = replicationFactor / len(r.ringZones)
		zonesWithExtraInstance = replicationFactor % len(r.ringZones)

		// We use a slice instead of a map because it's faster to search within a
		// slice than lookup a map for a very low number of items.
		distinctHosts       = bufHosts[:0]
		numOfInstanceByZone = resetZoneMap(bufZones)
	)

	for i := start; len(distinctHosts) < replicationFactor && iterations < len(r.ringTokens); i++ {
		iterations++
		// Wrap i around in the ring.
		i %= len(r.ringTokens)
		token := r.ringTokens[i]

		info, ok := r.ringInstanceByToken[token]
		if !ok {
			// This should never happen unless a bug in the ring code.
			return ReplicationSet{}, ErrInconsistentTokensInfo
		}

		// We want n *distinct* instances.
		if slices.Contains(distinctHosts, info.InstanceID) {
			continue
		}

		// Ignore if the instances don't have a zone set.
		if r.cfg.ZoneAwarenessEnabled && info.Zone != "" {
			maxNumOfInstance := maxInstancePerZone
			// If we still have room for zones with extra instance, increase the instance threshold by 1
			if zonesWithExtraInstance > 0 {
				maxNumOfInstance++
			}

			if numOfInstanceByZone[info.Zone] >= maxNumOfInstance {
				continue
			}
		}

		distinctHosts = append(distinctHosts, info.InstanceID)
		instance := r.ringDesc.Ingesters[info.InstanceID]

		// Check whether the replica set should be extended given we're including
		// this instance.
		if op.ShouldExtendReplicaSetOnState(instance.State) {
			replicationFactor++