Route Packets with Minimal Reassignment When Servers Change
Quick Overview
Implement consistent-hash packet routing with binary-search ring lookup, deterministic collisions, wraparound, and minimal reassignment on server changes.
Route Packets with Minimal Reassignment When Servers Change
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement routing from a packet identifier to an active backend server. For the same active server set, the same packet identifier must map consistently regardless of input-list order. Support adding and removing servers while minimizing changes to existing assignments.
Use the reported circular-hash-space approach: hash server IDs and packet identifiers into a fixed ordered ring and route each packet to the first server position clockwise, wrapping at the end. A stable hash function is available.
### Constraints & Assumptions
Treat server IDs as unique. A query with no active servers returns no server. For equal server hash positions, use server-ID order as an explicit deterministic tie-breaker. The source does not provide the hash function or require its illustrative destinations as exact test vectors.
### Clarifying Questions to Ask
- Is the hash stable across processes, restarts, and languages?
- How should hash collisions, an empty server set, and duplicate IDs be handled?
- Is load balance required in addition to limited reassignment?
```hint Find the clockwise successor
A sorted ring turns packet lookup into an insertion-position search with one wraparound case.
```
### What a Strong Answer Covers
- Stable ring construction, binary-search lookup, and exact-boundary behavior.
- The intervals affected by server insertion and removal.
- Collision handling, membership updates, and load-balance limitations.
### Follow-up Questions
- How would virtual nodes improve balance or represent server weights?
- What happens if different routers temporarily disagree on membership?
Overview: Implement consistent-hash packet routing with binary-search ring lookup, deterministic collisions, wraparound, and minimal reassignment on server changes.
Implement routing from a packet identifier to an active backend server. For the same active server set, the same packet identifier must map consistently regardless of input-list order. Support adding and removing servers while minimizing changes to existing assignments.
Use the reported circular-hash-space approach: hash server IDs and packet identifiers into a fixed ordered ring and route each packet to the first server position clockwise, wrapping at the end. A stable hash function is available.
Constraints & Assumptions
Treat server IDs as unique. A query with no active servers returns no server. For equal server hash positions, use server-ID order as an explicit deterministic tie-breaker. The source does not provide the hash function or require its illustrative destinations as exact test vectors.
Clarifying Questions to Ask Guidance
Is the hash stable across processes, restarts, and languages?
How should hash collisions, an empty server set, and duplicate IDs be handled?
Is load balance required in addition to limited reassignment?
What a Strong Answer Covers Guidance
Stable ring construction, binary-search lookup, and exact-boundary behavior.
The intervals affected by server insertion and removal.
Collision handling, membership updates, and load-balance limitations.
Follow-up Questions Guidance
How would virtual nodes improve balance or represent server weights?
What happens if different routers temporarily disagree on membership?