Hashring

Problem contributed by @asdf

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

---

Description

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:

int hash_fn(string key);  // provided, do not implement

---

Constructor

HashRing()

• Initializes an empty hash ring with no servers.

---

Part 1: Basic Consistent Hashing

add_server(server_id)

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

remove_server(server_id)

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

get_server(chat_id) -> str

• Hashes chat_id and returns the first server clockwise from that position on the ring.
• If multiple servers share the same hash position, any consistent tiebreak is acceptable.

---

Part 2: Virtual Nodes

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:

hash_fn(server_id + "#0"), hash_fn(server_id + "#1"), ..., hash_fn(server_id + "#v-1")

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

add_server(server_id, v)

• Adds a server with v virtual nodes at the positions described above.

remove_server(server_id)

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

---

Part 3: Server Affinity

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

record_affinity(server_id, chat_id)

• Records that server_id has an affinity for chat_id.

get_server_v3(chat_id, k) -> str

• Scans up to k servers clockwise from chat_id's ring position (including the primary).
• If any have a recorded affinity for chat_id, return the first such server in clockwise order.
• Otherwise, return the primary ring server as in Part 2.

---

Part 4: Memory-Aware Routing

Each server now has two memory tiers:

• VRAM (fast, limited capacity): chat sessions loaded in GPU memory.
• RAM (slower, larger capacity): 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 — If the primary ring server has chat_id in VRAM, route there.
2. RAM hit — Else if the primary ring server has chat_id in RAM, route there.
3. Affinity scan — Else scan up to k servers clockwise (including the primary).
   • If any have chat_id in VRAM, route to the one with the most available VRAM capacity.
   • Else if any have chat_id in RAM, route to the one with the most available RAM capacity.
4. Default — If no match is found, route to the primary ring server.

load_to_vram(server_id, chat_id)

• Marks chat_id as loaded in VRAM on server_id.
• If VRAM is at capacity, evict the least recently used chat from VRAM to RAM.
• If RAM is also at capacity, evict the least recently used chat from RAM entirely.
• A chat may exist in VRAM or RAM on a given server, but not both — loading to VRAM removes it from RAM on the same server if present.

load_to_ram(server_id, chat_id)

• Marks chat_id as loaded in RAM on server_id.
• If RAM is at capacity, evict the least recently used chat from RAM entirely.

get_server_v4(chat_id, k) -> str

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

---

Notes

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

• VRAM and RAM capacities are fixed per server and set during construction.

• LRU eviction order is determined by the most recent load_to_vram or load_to_ram call.

• 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.