For some distributed applications, e.g. the distributed actor model, distributed multi-producer, single-consumer (MPSC) queues play a vital role. For these applications to be fault tolerant and performant, a highly efficient non-blocking distributed MPSC queue is desired. Currently, in the literature, there is no non-blocking distributed MPSC queue. Therefore, a question naturally arises: Does there exist a performant non-blocking distributed MPSC queue? We answer this question by proposing Slotqueue, a wait-free distributed MPSC queue with only a constant amount of remote operations per enqueue and dequeue call. This is achieved by the use of timestamps to order the items in the queue and the idea of using a flat array structure to maintain the timestamps. To demonstrate how well Slotqueue performs in practice, we develop a microbenchmark to measure its throughput as compared to other distributed MPSC queues we have surveyed in the literature. We discover that Slotqueue is fault tolerant while performing comparable to other distributed MPSC queues.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Slotqueue: A Wait-Free Distributed Multi-producer Single-Consumer Queue with Constant Remote Operations

  • Do Nguyen An Huy,
  • Thanh-Dang Diep,
  • Karl Fürlinger,
  • Nam Thoai

摘要

For some distributed applications, e.g. the distributed actor model, distributed multi-producer, single-consumer (MPSC) queues play a vital role. For these applications to be fault tolerant and performant, a highly efficient non-blocking distributed MPSC queue is desired. Currently, in the literature, there is no non-blocking distributed MPSC queue. Therefore, a question naturally arises: Does there exist a performant non-blocking distributed MPSC queue? We answer this question by proposing Slotqueue, a wait-free distributed MPSC queue with only a constant amount of remote operations per enqueue and dequeue call. This is achieved by the use of timestamps to order the items in the queue and the idea of using a flat array structure to maintain the timestamps. To demonstrate how well Slotqueue performs in practice, we develop a microbenchmark to measure its throughput as compared to other distributed MPSC queues we have surveyed in the literature. We discover that Slotqueue is fault tolerant while performing comparable to other distributed MPSC queues.