amirziai

def update_server(
    self,
    server_id: ServerId,
    token_count: int,
) -> None:
    ...

amirziai

def alloc(
    ch: ConsistentHashingWithTokens,
) -> pd.Series:
    return pd.Series(
        ch.key_lookup(url)
        for url in urls
    ).value_counts(normalize=True)

ch = ConsistentHashingWithTokens({'a': 100, 'b': 400, 'c': 500})
alloc(ch=ch)

amirziai

def experiment_capacity(a_tokens: int) -> float:
    assert a_tokens >= 2 and a_tokens % 2 == 0
    a = random_str()
    b = random_str()
    ch = ConsistentHashingWithTokens(
        server_tokens={a: a_tokens, b: a_tokens // 2},
    )
    return sum(
        ch.key_lookup(key=url) == a
        for url in urls

amirziai

class ConsistentHashingWithTokens:
    def __init__(
        self,
        server_tokens: Dict[ServerId, int],
        seed: int = SEED,
    ):
        assert all(tokens >= 1 for tokens in server_tokens.values())
        self._seed = seed
        self._server_tokens = server_tokens
        self._allocate_servers()

amirziai

class ConsistentHashingWithTokens:
    def __init__(
        self,
        server_tokens: Dict[ServerId, int],
        seed: int = SEED,
    ):
        ...

amirziai

@dataclass(frozen=True)
class ServerToken:
    server_id: ServerId
    token_idx: int
    _seed: int = SEED
        
    @property
    @functools.lru_cache()
    def key(self) -> str:
        return f"{self.node_id}-{self.token_idx}"

amirziai

from collections import defaultdict


def compute_slices(
    n: int,
    k: int,
    seed: Optional[int] = None,
) -> List[float]:
    np.random.seed(seed)
    tokens = np.random.rand(n * k)

amirziai

pd.concat([
    run_exp(
        ns=(1, 5, 10),
        experiment_cnt=5,
        ch_cls=functools.partial(
            ConsistentHashingWithTokensNaive,
            k=k,
        ),
    ).assign(k=k)
    for k in (1, 10, 100)

amirziai

class ConsistentHashingWithTokensNaive:
    def __init__(
        self,
        server_ids: Set[ServerId],
        k: int,
        seed: int = SEED,
    ):
        server_ids_virtual = {
            f"{server_id}-{idx}"
            for server_id in server_ids

amirziai

url_cnt = 10_000
urls = [random_str() for _ in range(url_cnt)]
ns = (1, 2, 5, 10, 20, 50, 100)
experiment_cnt = 100

df_experiment_same_alloc = run_exp(
    ns=ns,
    experiment_cnt=experiment_cnt,
    ch_cls=ConsistentHashing,
)