The shard key was uniform and the traffic was not

# Self-authored for the EML case corpus (no external origin). The shard key
# distributes forty million keys across sixty-four shards to within three parts
# in a thousand. What one shard serves is computed below.
#
# The distribution test is real and it passes. Forty million keys were hashed,
# every shard's share was measured, and the largest deviation from even is three
# parts in a thousand. The hash was chosen after an earlier key produced a
# forty-percent imbalance, and the test exists because of that incident.
#
# Uniformity of KEYS is not uniformity of REQUESTS. Each key carries its own
# traffic, that traffic is heavy-tailed in every system that has customers of
# different sizes, and the placement function has no input for it.
#
# One key takes thirty-one percent of all requests.

40000000 => keys
64 => shards
30 => largest_key_deviation_per_myriad
180000 => requests_per_second
3100 => hottest_key_share_per_myriad

int(keys / shards) => keys_per_shard
int(requests_per_second / shards) => even_requests_per_shard
int(requests_per_second * hottest_key_share_per_myriad / 10000) => hottest_key_requests
requests_per_second - hottest_key_requests => remaining_requests
hottest_key_requests + int(remaining_requests / shards) => hot_shard_requests
int(hot_shard_requests / even_requests_per_shard) => hot_shard_times_even

"keys                        : " + str(keys) ^0
"shards                      : " + str(shards) ^0
"keys per shard              : " + str(keys_per_shard) ^0
"largest key deviation       : " + str(largest_key_deviation_per_myriad) + " per ten thousand" ^0
"" ^0
"requests per second         : " + str(requests_per_second) ^0
"an even shard would serve   : " + str(even_requests_per_shard) ^0
"the hottest key alone takes : " + str(hottest_key_requests) ^0
"the shard holding it serves : " + str(hot_shard_requests) ^0
"which is the even share times: " + str(hot_shard_times_even) ^0
"" ^0

# ---- what the distribution test verified ----

"the key distribution test" ^0
"  keys hashed          : " + str(keys) ^0
"  shards               : " + str(shards) ^0
"  largest deviation    : " + str(largest_key_deviation_per_myriad) + " per ten thousand" ^0
"  written after        : an earlier key with a 40 percent" ^0
"    imbalance" ^0
"  verdict              : UNIFORM" ^0
"" ^0
"  the test is not theatre; it caught a real problem once" ^0
"  and it would catch it again" ^0
"" ^0

# ---- what it counted ----

"the two populations" ^0
"  keys           : " + str(keys) + ", measured, uniform" ^0
"  requests       : " + str(requests_per_second) + " a second, not measured by this test" ^0
"  the placement function's inputs : the key" ^0
"  its inputs about traffic        : none" ^0
"" ^0
"  a hash cannot weight by a quantity it is not given, and" ^0
"  giving it one would make placement depend on load and" ^0
"  therefore move under it" ^0
"" ^0

# ---- the shape of the tail ----

# The hottest key is a single customer. Rebalancing moves it to another shard,
# which then becomes the hot one; splitting the key requires the application to
# have a second dimension to split on, and it does not.
"remedies, and what each does" ^0
"  rehash with a different seed : the hot key lands" ^0
"    somewhere else and that shard becomes hot" ^0
"  add shards                   : the even share falls," ^0
"    the hot key does not" ^0
"  split the key                : needs a second dimension" ^0
"    in the data, which is an application change" ^0
"" ^0

int(hottest_key_requests * 10000 / hot_shard_requests) => one_key_share_of_hot_shard
"the hot shard's load that is one key : " + str(one_key_share_of_hot_shard) + " per ten thousand" ^0
"" ^0

# ---- null control ----

# The same hash and the same keys, with requests measured instead of keys.
int(hot_shard_requests * 10000 / even_requests_per_shard) => nc_measured_imbalance_per_myriad

"null control - measure the request distribution, not the key distribution" ^0
"  key deviation        : " + str(largest_key_deviation_per_myriad) + " per ten thousand, unchanged" ^0
"  request imbalance    : " + str(nc_measured_imbalance_per_myriad) + " per ten thousand of even" ^0
"  the sharding did not change; the test started counting" ^0
"  the quantity that arrives rather than the one that is" ^0
"  stored" ^0
"" ^0

# ---- the rule ----

"what a uniform shard key guarantees" ^0
"  keys are spread evenly     : exactly" ^0
"  load is spread evenly      : not addressed; load is a" ^0
"    property of each key and the hash is a function of" ^0
"    the key's name" ^0
"" ^0
"a distribution test measures what it enumerates; enumerate" ^0
"the keys and you learn about storage, enumerate the requests" ^0
"and you learn about the shard that falls over" ^0
"" ^0

"The key distribution is uniform to " + str(largest_key_deviation_per_myriad) + " parts in ten thousand across " + str(shards) ^0
"shards, measured over " + str(keys) + " keys by a test written after a real 40 percent" ^0
"imbalance. One key takes " + str(hottest_key_requests) + " of " + str(requests_per_second) + " requests a second, so its shard" ^0
"serves " + str(hot_shard_requests) + " against an even " + str(even_requests_per_shard) + " - " + str(hot_shard_times_even) + " times the share, " + str(one_key_share_of_hot_shard) ^0
"per ten thousand of it a single key - and the placement function was never told." ^0

keys = 40000000
shards = 64
largest_key_deviation_per_myriad = 30
requests_per_second = 180000
hottest_key_share_per_myriad = 3100
keys_per_shard = int(keys / shards)
even_requests_per_shard = int(requests_per_second / shards)
hottest_key_requests = int(requests_per_second * hottest_key_share_per_myriad / 10000)
remaining_requests = requests_per_second - hottest_key_requests
hot_shard_requests = hottest_key_requests + int(remaining_requests / shards)
hot_shard_times_even = int(hot_shard_requests / even_requests_per_shard)
print("keys                        : " + str(keys))
print("shards                      : " + str(shards))
print("keys per shard              : " + str(keys_per_shard))
print("largest key deviation       : " + str(largest_key_deviation_per_myriad) + " per ten thousand")
print("")
print("requests per second         : " + str(requests_per_second))
print("an even shard would serve   : " + str(even_requests_per_shard))
print("the hottest key alone takes : " + str(hottest_key_requests))
print("the shard holding it serves : " + str(hot_shard_requests))
print("which is the even share times: " + str(hot_shard_times_even))
print("")
print("the key distribution test")
print("  keys hashed          : " + str(keys))
print("  shards               : " + str(shards))
print("  largest deviation    : " + str(largest_key_deviation_per_myriad) + " per ten thousand")
print("  written after        : an earlier key with a 40 percent")
print("    imbalance")
print("  verdict              : UNIFORM")
print("")
print("  the test is not theatre; it caught a real problem once")
print("  and it would catch it again")
print("")
print("the two populations")
print("  keys           : " + str(keys) + ", measured, uniform")
print("  requests       : " + str(requests_per_second) + " a second, not measured by this test")
print("  the placement function's inputs : the key")
print("  its inputs about traffic        : none")
print("")
print("  a hash cannot weight by a quantity it is not given, and")
print("  giving it one would make placement depend on load and")
print("  therefore move under it")
print("")
print("remedies, and what each does")
print("  rehash with a different seed : the hot key lands")
print("    somewhere else and that shard becomes hot")
print("  add shards                   : the even share falls,")
print("    the hot key does not")
print("  split the key                : needs a second dimension")
print("    in the data, which is an application change")
print("")
one_key_share_of_hot_shard = int(hottest_key_requests * 10000 / hot_shard_requests)
print("the hot shard's load that is one key : " + str(one_key_share_of_hot_shard) + " per ten thousand")
print("")
nc_measured_imbalance_per_myriad = int(hot_shard_requests * 10000 / even_requests_per_shard)
print("null control - measure the request distribution, not the key distribution")
print("  key deviation        : " + str(largest_key_deviation_per_myriad) + " per ten thousand, unchanged")
print("  request imbalance    : " + str(nc_measured_imbalance_per_myriad) + " per ten thousand of even")
print("  the sharding did not change; the test started counting")
print("  the quantity that arrives rather than the one that is")
print("  stored")
print("")
print("what a uniform shard key guarantees")
print("  keys are spread evenly     : exactly")
print("  load is spread evenly      : not addressed; load is a")
print("    property of each key and the hash is a function of")
print("    the key's name")
print("")
print("a distribution test measures what it enumerates; enumerate")
print("the keys and you learn about storage, enumerate the requests")
print("and you learn about the shard that falls over")
print("")
print("The key distribution is uniform to " + str(largest_key_deviation_per_myriad) + " parts in ten thousand across " + str(shards))
print("shards, measured over " + str(keys) + " keys by a test written after a real 40 percent")
print("imbalance. One key takes " + str(hottest_key_requests) + " of " + str(requests_per_second) + " requests a second, so its shard")
print("serves " + str(hot_shard_requests) + " against an even " + str(even_requests_per_shard) + " - " + str(hot_shard_times_even) + " times the share, " + str(one_key_share_of_hot_shard))
print("per ten thousand of it a single key - and the placement function was never told.")

keys                        : 40000000
shards                      : 64
keys per shard              : 625000
largest key deviation       : 30 per ten thousand

requests per second         : 180000
an even shard would serve   : 2812
the hottest key alone takes : 55800
the shard holding it serves : 57740
which is the even share times: 20

the key distribution test
  keys hashed          : 40000000
  shards               : 64
  largest deviation    : 30 per ten thousand
  written after        : an earlier key with a 40 percent
    imbalance
  verdict              : UNIFORM

  the test is not theatre; it caught a real problem once
  and it would catch it again

the two populations
  keys           : 40000000, measured, uniform
  requests       : 180000 a second, not measured by this test
  the placement function's inputs : the key
  its inputs about traffic        : none

  a hash cannot weight by a quantity it is not given, and
  giving it one would make placement depend on load and
  therefore move under it

remedies, and what each does
  rehash with a different seed : the hot key lands
    somewhere else and that shard becomes hot
  add shards                   : the even share falls,
    the hot key does not
  split the key                : needs a second dimension
    in the data, which is an application change

the hot shard's load that is one key : 9664 per ten thousand

null control - measure the request distribution, not the key distribution
  key deviation        : 30 per ten thousand, unchanged
  request imbalance    : 205334 per ten thousand of even
  the sharding did not change; the test started counting
  the quantity that arrives rather than the one that is
  stored

what a uniform shard key guarantees
  keys are spread evenly     : exactly
  load is spread evenly      : not addressed; load is a
    property of each key and the hash is a function of
    the key's name

a distribution test measures what it enumerates; enumerate
the keys and you learn about storage, enumerate the requests
and you learn about the shard that falls over

The key distribution is uniform to 30 parts in ten thousand across 64
shards, measured over 40000000 keys by a test written after a real 40 percent
imbalance. One key takes 55800 of 180000 requests a second, so its shard
serves 57740 against an even 2812 - 20 times the share, 9664
per ten thousand of it a single key - and the placement function was never told.

Trace event types