2

I have a system where Client(C) sends request to Server(S0). S0 then sends the response back to Client that "request received" and closes the connection. C can regularly poll S0 to check on status of the task. The task to perform contains several asynchronous tasks (T1, T2, T3, etc.) that can take many hours to complete. These tasks are performed on distributed servers (S1, S2, S3) respectively. Some of these tasks depend on other tasks, some are independent.

Suppose T1, T2 got completed but S3 crashes while it it working on T3.

Questions:

  1. Assume S3 can recover: How to design this distributed system in a fault-tolerant and efficient way?
  2. Assume S3 cannot recover: How to make these distributed tasks a "transaction"? In other words: how to design all-or-nothing system when distributed servers are involved?

PS: This was a system design question asked in my recent interview. I provided answers but looking for expert advice.

3
  • Because this was an interview question, this was not about having the "correct" answer, but about showing that you know various strategies to tackle these issues (e.g. two-phase commit, Saga pattern, implications of using event-driven systems, relaxing business requirements) and can discuss their advantages and problems in this scenario. If I were tackling this in the real world I'd focus on the tasks T1-T3: what kind of data dependencies do they have, when do they produce irrevocable changes or external effects? Can they be split into independently retryable phases?
    – amon
    Nov 23, 2023 at 8:21
  • 1
    In most abstract terms: Delay the output & side effects until all is good, with a timeout.
    – S.D.
    Nov 23, 2023 at 8:55

2 Answers 2

3

The solution to this kind of problems is to be found in a two phase commit protocol. If the fact that 2PC requires a master coordination node is an issue, you can consider a three phase commit protocol. These families of algorithms ensure a distributed transaction processing with an all or nothing.

The general idea of these family of algorithms is that all servers perform their tasks, and then vote to confirm that everything went fine, and then get an ok for committing at their level. Here, an additional difficulty that some servers have to wait for predecessors on other server to finish, without knowing if they wait for nothing because of a crash or not. A combination of timeout and periodic alive notification should therefore complement the design.

Of course, 2PC and 3PC need all nodes to be able to reliably log their states in case of recovery need. Moreover, the different nodes who performed T1, T2, to be able to revert, which is usually done with some paging mechanisms for persistant data, where the new data is made available only after confirmation of the end of the transaction.

The behavior of a server that crashes can be addressed with a variety of strategies:

  • a local transaction processing algorithm for T3 steps could deal with the recovery of T3 state, in a way the processing can continue just after the last valid step without restarting from scratch.
  • alternatively, if the 2PC/3PC passed to the abort, the restarted server should be able to find out the need to abort and revert. Some engineering is still needed in this regard, as 2PC/3PC do not really explain how to recover a server long after the transaction reverted due to a failure.

This being said, the design of distributed algorithms is extremely tricky. The design of fault-tolerant algorithms is also very tricky (e.g. imagine one server is up and running and just lost the network connection for a while). The combination of both is probably of the highest possible complexity. Fortunately, the goal of your interviewer is not to make you fast track on your own the research done by significant teams of experts over a longer period, but just to see if you have a sufficient understanding of what's at stake.

1

This is a good interview question because it's technically unsolvable (the two generals problem), but has many practical solutions for most scenarios.

A hypothetical interview might go like this

Q. solve problem as described

A. Do the work, but have the overall job in a "processing" state until they all complete. If a task hard fails, mark the job failed and roll back changes, if all the tasks pass, mark them completed as the final step.

Q. What if the "final step" fails

A. Make the final step as simple as possible to minimise this risk, mark the job for human intervention.

Q. What if the tasks have unrecoverable side effects. eg "send an email"

A. Divide the task into multiple parts, so that you can do the unrecoverable bits at the end of the overall transaction to minimise risk. mark the job for human intervention, if an unrecoverable error occurs.

Q. What if a task is taking longer than usual to complete, how do you know its not stuck, when should you fail it?

A. Add a logging or healthcheck to the task so you can monitor its progress, add a "cancel" method to the task so you can cancel it, Add a timeout on the wait for the task

Not the answer you're looking for? Browse other questions tagged or ask your own question.