Hashring

Problem contributed by @asdf

Implement a HashRing, a consistent hashing ring that routes chat sessions to servers.

Design a distributed chat load balancer using a consistent hashing ring — a circle of integers in the range [0, 2^32). Both servers and chats are assigned positions using a hash function. A chat is routed to the first server clockwise from its position on the ring, with wraparound.

This problem is divided into multiple parts. Each part builds on the previous one.

A hash function is provided — treat it as a black box:

Tiebreak rule (applies to all parts): When scanning the ring clockwise, distinct physical servers are visited in clockwise order starting from the primary. If two ring positions collide on the same hash, ties are broken lexicographically by server_id. Test data will not rely on collision tiebreaks for correctness, but your implementation must be deterministic.

• Initializes an empty hash ring with no servers.

• Adds a server to the ring at position hash_fn(server_id).
• If the server already exists, do nothing.

• Removes the server from the ring.
• If the server does not exist, do nothing.

• Hashes chat_id and returns the first server clockwise from that position on the ring.

A single ring position per server leads to uneven load distribution. Extend your implementation to support virtual nodes: each physical server gets v positions on the ring at:

Modify add_server and remove_server to handle virtual nodes. get_server behavior is unchanged — it still returns the physical server id.

• Adds a server with v virtual nodes at the positions described above.
• If the server already exists, do nothing.
• The single-argument add_server(server_id) from Part 1 is equivalent to add_server(server_id, 1) with the position computed from hash_fn(server_id) directly (no #0 suffix).

• Removes the server and all of its virtual nodes from the ring.

Extend routing to support affinity-based fallback. When looking up a chat, instead of always returning the primary ring server, scan up to k distinct physical servers clockwise (including the primary) and prefer servers that have previously handled this chat.

• Records that server_id has an affinity for chat_id.

• Scans up to k distinct physical servers clockwise from chat_id's ring position (including the primary).
• If k is greater than the number of distinct physical servers on the ring, the scan visits every server exactly once.
• If any scanned server has a recorded affinity for chat_id, return the first such server in clockwise order.
• Otherwise, return the primary ring server as in Part 2.

Affinities are tied to a server's identity. If a server is removed, its affinities are discarded; re-adding the same server_id later starts with no affinities.

Each server now tracks two memory tiers:

• VRAM: chat sessions loaded in GPU memory.
• RAM: chat sessions loaded in regular memory.

Replace affinity tracking from Part 3 with explicit memory state. When routing a chat_id, apply the following priority logic:

1. VRAM hit on primary — If the primary ring server has chat_id in VRAM, route there.
2. RAM hit on primary — Else if the primary ring server has chat_id in RAM, route there.
3. Scan fallback — Else scan up to k distinct physical servers clockwise (including the primary).
   • If any have chat_id in VRAM, route to the first one in clockwise order.
   • Else if any have chat_id in RAM, route to the first one in clockwise order.
4. Default — If no match is found, route to the primary ring server.

• Marks chat_id as loaded in VRAM on server_id.
• If chat_id was in RAM on the same server, it is removed from RAM.

• Marks chat_id as loaded in RAM on server_id.
• If chat_id was in VRAM on the same server, it is removed from VRAM.

A chat may exist in VRAM or RAM on a given server, but not both.

• Returns the best server for chat_id using the priority logic above, scanning up to k distinct physical servers clockwise.

Memory state, like affinity, is tied to a server's identity. If a server is removed, its VRAM and RAM contents are discarded; re-adding the same server_id later starts with empty memory.

• All server_id and chat_id values consist of lowercase letters, digits, and underscores.

• The ring is guaranteed to be non-empty at the time of any GET, GET3, or GET4 operation.

• record_affinity, load_to_vram, and load_to_ram are only called with server_id values that currently exist on the ring.

• You do not need to declare or define a hash function of your own. It is defined in the judge.

• Input format: The first line contains N, the number of operations. Each of the next N lines is one operation. The operation name maps to methods as follows:

  • ADD server_id → add_server(server_id)
  • ADD server_id v → add_server(server_id, v)
  • REMOVE server_id → remove_server(server_id)
  • GET chat_id → get_server(chat_id)
  • AFFINITY server_id chat_id → record_affinity(server_id, chat_id)
  • GET3 chat_id k → get_server_v3(chat_id, k)
  • VRAM server_id chat_id → load_to_vram(server_id, chat_id)
  • RAM server_id chat_id → load_to_ram(server_id, chat_id)
  • GET4 chat_id k → get_server_v4(chat_id, k)

• Output format: For each GET, GET3, or GET4, print the resolved server_id on its own line. All other operations produce no output.