[RFC] prefix-cache-aware routing

We are planning to add prefix-cache-aware routing support, as mentioned in #26 . Here is an initial version of design. This design focuses on building the fundamental APIs for prefix-cache-aware routing, without requiring large API changes to vLLM.

Design choices and APIs:

• Use string matching instead of token-ID-based matching. Token-ID-based matching are accurate, but it is difficult to get exactly the same sequence of token IDs because various issues (e.g. chat template) . So we use string matching. but it is slow (it takes several microseconds) so we don't want to run it for every request at the router side.
• Build a string server to keep track of the prefix cache information inside each vLLM pod. Two APIs:
  • query(request: str, server_ids: List[Int], t: Timestamp): query which server_id inside the list of server_ids should we forward this request to.
  • notify(request: str, server_id: int, t: Timestamp): notify that the request is now executed by which server, so that the string server can update its internal status.

An initial implementation:

• We will implement the string server using SQL database.
• When notify(request: str, server_id: int, t: Timestamp), we will chop the request string into fix-size chunks c0, c1, ..., cn, for each chunk we create a content hash by content_hash(ci) = hash(c0 + c1 + ... + ci), store these chunks into the token server, and evict least-recently-used chunks in the corresponding server id to make sure the total number of chunks in the server id is smaller than a pre-defined constant C.
• During query(request: str, server_ids: List[Int], t: Timestamp), we will query each server in the server list and see which one matches the maximum number of chunks.

Feel free to leave your feedback and comments!

Start by reading the related issue #26 and the proposed query and notify APIs in this RFC. Then examine how the project currently communicates with vLLM pods and uses SQL-backed state. Done means agreeing on and implementing the prefix-cache-aware routing design, including chunk matching and eviction behavior.