空气床OA

Implement a global load balancer.

Input
Stdin is used to provide the input. The first line of the input is space separated node name followed by region name followed by zone name. The names of the nodes would be unique, however region names and zone names will not be unique. Each zone would have multiple nodes and each region would have multiple zones.

Eg :
<n1> <r1> <z1>, <n2> <r1> <z2>, …
Remaining lines are requests made which are of the form.
<ReqId> <type> <region> <zone>

<ReqId>: Integer that uniquely identifies the req.
<type>: Http GET or POST
<region> <zone>: Strings representing the source region and zone of the request.

Output
For each of the request made, the output should be of the form,

<ReqId> <n1> <n2> <n3> …

ReqId identifies each request made uniquely. Followed by node names in preference order. The request would be sent to the first node name, however if that fails it would be sent to the second node and so on. If a node fails, requests would be retried only if the request is non-idempotent (i.e. POST request cannot be retried.).

The load balancer should satisfy the below properties:

  • The implementation should be able to handle large input load. The load balancer should handle millions of requests per hour.
  • POSTS are not retriable. Query idempotence must be taken into account;
  • Requests should go to local zone nodes first, followed by local regions, followed by nodes not in the same region. The preference order is important. The order of node names that belong to the same region does not matter, Each node within the same region should be equally load balanced. There may be some requests in zones and regions that have no nodes!
  • Requests must be evenly balanced between nodes within zones, for example if there are two nodes in a given zone, they should each appear first in the response lists for roughly 50% of the requests from that zone.

Example

node1 region1 zone1,node2 region1 zone1,node3 region2 zone1,node4 region2 zone2
1 GET region1 zone1
2 POST region1 zone1
3 GET region2 zone3
4 GET region1 zone1
5 GET region2 zone1
6 POST region1 zone1

One valid solution is:

1 node1 node2 node4 node3
2 node2
3 node4 node3 node1 node2
4 node1 node2 node4 node3
5 node3 node4 node2 node1
6 node2

Another valid solution is:

1 node1 node2 node4 node3
4 node2 node1 node3 node4
3 node4 node3 node1 node2
5 node3 node4 node2 node1
2 node1
6 node2