  Distributed data structures are key to implementing scalable applications for
scientific simulations and data analysis. In this paper we look at two
implementation styles for distributed data structures: remote direct memory
access (RDMA) and remote procedure call (RPC). We focus on operations that
require individual accesses to remote portions of a distributed data structure,
e.g., accessing a hash table bucket or distributed queue, rather than global
operations in which all processors collectively exchange information. We look
at the trade-offs between the two styles through microbenchmarks and a
performance model that approximates the cost of each. The RDMA operations have
direct hardware support in the network and therefore lower latency and
overhead, while the RPC operations are more expressive but higher cost and can
suffer from lack of attentiveness from the remote side. We also run experiments
to compare the real-world performance of RDMA- and RPC-based data structure
operations with the predicted performance to evaluate the accuracy of our
model, and show that while the model does not always precisely predict running
time, it allows us to choose the best implementation in the examples shown. We
believe this analysis will assist developers in designing data structures that
will perform well on current network architectures, as well as network
architects in providing better support for this class of distributed data
structures.
