Distributed MPSC queues form the basis of many distributed applications such as distributed actor models and task data-dependencies frameworks. Therefore, a highly efficient non-blocking MPSC queue can improve the applications’ performance and fault tolerance. However, currently in the distributed-memory literature, there is no known non-blocking distributed MPSC queue. This pales in comparison to the shared-memory domain, where there is a great wealth of non-blocking shared-memory MPSC queues. Fortunately, recent studies have proposed approaches to bridge this apparent gap between the two domains. Hence, in this paper, we provide a brief survey into such approaches and select one approach, BCL CoreX, to design non-blocking distributed MPSC queues based on shared-memory counterparts. With BCL CoreX, we survey the shared-memory literature for non-blocking shared-memory MPSC queues and reason about their viability in adaptation to distributed environments. Based on these results, we propose dLTQueue, the first non-blocking distributed MPSC queue, which is inspired by the shared-memory data structure LTQueue. To successfully adapt LTQueue, we have to workaround its use of the load-link/store-conditional instruction, which does not exist in distributed environments. Finally, an empirical evaluation of dLTQueue in comparison to other existing distributed MPSC queues is conducted. We find that even though dLTQueue scores much higher on the fault tolerance scale, dLTQueue performs much worse than other existing alternatives.

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

dLTQueue: A Non-blocking Distributed-Memory Multi-producer Single-Consumer Queue

  • Do Nguyen An Huy,
  • Manh-Thin Nguyen,
  • Thanh-Dang Diep,
  • Nam Thoai

摘要

Distributed MPSC queues form the basis of many distributed applications such as distributed actor models and task data-dependencies frameworks. Therefore, a highly efficient non-blocking MPSC queue can improve the applications’ performance and fault tolerance. However, currently in the distributed-memory literature, there is no known non-blocking distributed MPSC queue. This pales in comparison to the shared-memory domain, where there is a great wealth of non-blocking shared-memory MPSC queues. Fortunately, recent studies have proposed approaches to bridge this apparent gap between the two domains. Hence, in this paper, we provide a brief survey into such approaches and select one approach, BCL CoreX, to design non-blocking distributed MPSC queues based on shared-memory counterparts. With BCL CoreX, we survey the shared-memory literature for non-blocking shared-memory MPSC queues and reason about their viability in adaptation to distributed environments. Based on these results, we propose dLTQueue, the first non-blocking distributed MPSC queue, which is inspired by the shared-memory data structure LTQueue. To successfully adapt LTQueue, we have to workaround its use of the load-link/store-conditional instruction, which does not exist in distributed environments. Finally, an empirical evaluation of dLTQueue in comparison to other existing distributed MPSC queues is conducted. We find that even though dLTQueue scores much higher on the fault tolerance scale, dLTQueue performs much worse than other existing alternatives.