Shard Map

The Proxy has a memory copy at ProxyCommitData::keyInfo of type KeyRangeMap<ServerCacheInfo>, which maps a shard to a number of storage servers.

Database stores the mapping in system keyspace at "keyServers": map from keys to destination servers "\xff/keyServers/[[begin]]" := "[[vector<serverID>, vector<serverID>]|[vector<Tag>, vector<Tag>]]" Note the range's begin is in the key. The range's end is implicitly in the next key.

So when inserting/assigning a new range to a server, applyMetadataMutation will:

KeyRef end = keyInfo->rangeContaining(k).end();
KeyRangeRef insertRange(k,end);
...
keyInfo->insert(insertRange,info);

See krmSetPreviouslyEmptyRange below, which has two set ops.

For clearRange, applyMetadataMutation will:

KeyRangeRef r = range & keyServersKeys;
KeyRangeRef clearRange(r.begin.removePrefix(keyServersPrefix), r.end.removePrefix(keyServersPrefix));
keyInfo->insert(clearRange,  clearRange.begin == StringRef() ? ServerCacheInfo() :
                            keyInfo->rangeContainingKeyBefore(clearRange.begin).value());

See krmSetRange below, which has a clear and two set ops.

startMoveKeys(Database occ, KeyRange keys, vector<UID> servers, MoveKeysLock lock, FlowLock *startMoveKeysLock, UID relocationIntervalId)

// serverKeys: two-dimension map: [servers][keys], value is the servers' state of having the keys: active(not-have), complete(already has), ""(). // Set keyServers[keys].dest = ##servers // Set serverKeys[servers][keys] = active for each subrange of keys that the server did not already have, complete for each subrange that it already has // Set serverKeys[dest][keys] = "" for the dest servers of each existing shard in keys (unless that destination is a member of servers OR if the source list is sufficiently degraded)

For an empty range, set two keys: beginKeyWithPrefix = newValue; endKeyWithPrefix = oldValue.

void krmSetPreviouslyEmptyRange( Transaction* tr, const KeyRef& mapPrefix, const KeyRangeRef& keys, const ValueRef& newValue, const ValueRef& oldEndValue )
{
	KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + keys.begin.toString(), mapPrefix.toString() + keys.end.toString() );
	tr->set( withPrefix.begin, newValue );
	tr->set( withPrefix.end, oldEndValue );
}

ACTOR Future<Void> krmSetRange( Transaction* tr, Key mapPrefix, KeyRange range, Value value ) {
	state KeyRange withPrefix = KeyRangeRef( mapPrefix.toString() + range.begin.toString(), mapPrefix.toString() + range.end.toString() );
	Standalone<RangeResultRef> old = wait(tr->getRange(lastLessOrEqual(withPrefix.end), firstGreaterThan(withPrefix.end), 1, true));
	
	Value oldValue;
	bool hasResult = old.size() > 0 && old[0].key.startsWith(mapPrefix);
	if(hasResult)
		oldValue = old[0].value;

	KeyRange conflictRange = KeyRangeRef( hasResult ? old[0].key : mapPrefix.toString(), keyAfter(withPrefix.end) );
	if( !conflictRange.empty() )
		tr->addReadConflictRange( conflictRange );
	
	tr->clear(withPrefix);
	tr->set( withPrefix.begin, value );
	tr->set( withPrefix.end, oldValue );

	return Void();
}

There is a krmSetRangeCoalescing_ function.

//Sets a range of keys in a key range map, coalescing with adjacent regions if the values match
//Ranges outside of maxRange will not be coalesced
//CAUTION: use care when attempting to coalesce multiple ranges in the same prefix in a single transaction
ACTOR template <class Transaction>
static Future<Void> krmSetRangeCoalescing_(Transaction* tr, Key mapPrefix, KeyRange range, KeyRange maxRange,
                                           Value value) {