search

brando90 / RoadRunner

High performant, fault tolerant, persistent, key value store
0 stars 0 forks source link

Routing client requests to leader #18

Open pcattori opened 10 years ago

pcattori commented 10 years ago

How do we plan to route client requests to a leader?

pcattori commented 10 years ago

Couple of options:

1) Have client send requests to all servers of a group.

1a) In the above scheme, send requests sequentially and stop sending once we reach the first client. This avoids duplicates and avoids further contention.

1b) In 1a, the client may suffer multiple RTT's before its request can reach a leader. We can instead concurrently send requests to all servers in a group to suffer only 1 RTT. Servers that are not leaders respond with a Nack to client, servers that are leaders process the client request. We will have as many duplicates for that request as the number of leaders the client was able to reach. Rely on duplicate detection for correctness.

2) Have a client send a request to 1 server in the group.

2a) If the server is a leader, process the client request.

Otherwise, Nack, but tell the client the server with the highest ID who you consider alive (who you think is the leader). The client retries by sending the request to the prospective leader.

2b) Have the server route the request to a potential leader, until it reaches a server that is considered to be the leader. This can create a chain of RPC calls.

2c) Make a designated router. Similar to 2b. However, with 1 designated router we can accomplish pipelining of client requests. Suffers an RTT between router and leader. Allows for pipelining. Consider fault-tolerance of router (probably best implemented as primary/backup... for the scope of the project maybe assume router is fault-tolerant).

3) Come up with a scheme for communicating leader id's. Have the client contact a potential leader directly.

\ We can improve the performance of all of these schemes by having clients keep track of successfully reached leaders. Keep contacting that leader until we cannot reach it anymore. Use this leader as temporary pipelining-router.

brando90 commented 10 years ago

contention == dueling proposers?

brando90 commented 10 years ago

I was wondering, I thought the tick()'s were not in the critical path, so doesn't it mean that the RTT due to ticks dont matter?

pcattori commented 10 years ago

@brando90 Correct & correct.

pcattori commented 10 years ago

Possible issue: What do we do when the client cannot reach the leader it was routed to?

brando90 commented 10 years ago

If the client can't reach a leader, then shouldn't he check if the leader is dead? If he is not dead, but can't reach him, we could have some other server act as a "temporary router" and send his request to the leader? Would this create any problems for pipelining?

pcattori commented 10 years ago

@brando90 Servers in general cannot differentiate between dead servers and unreachable servers, so your first point is not really doable in my opinion.

Routing through our own servers can be done without ruining pipelining. BUT, it adds another layer of complexity... let's talk about how this can be done after we have it working for the case where a client is always able to reach the leader they have been directed to.