Techniques are disclosed relating to task execution with non-blocking calls. A computer system may receive a request to perform an operation comprising a plurality of tasks, each of which corresponds to a node in a graph. A particular one of the plurality of tasks specifies a call to a downstream service. The computer system may maintain a plurality of task queues, each of which is associated with a thread pool. The computer system may enqueue, in an order specified by the graph, the plurality of tasks in one or more of the plurality of task queues. The computer system may process the plurality of tasks. Such processing may include a thread of a particular queue in which the particular task is enqueued performing a non-blocking call to the downstream service. After processing the plurality of tasks, the computer system may return a result of performing the operation.