Explanation of Mapped Futures

Mapped Futures is a rust library that allows asynchronous operations, called Futures, to be collected and efficiently polled, but also associates each future with a key, which can be used to mutate the future, examine any data it contains, or cancel the future. I first wrote and published MappedFutures in 2023 while working on another project, the sync layer of bramble communication protocols. First I'll explain a bit about these projects, and then I'll discuss the design of mapped futures.

Storm and Bramble

I started bramble and storm as school projects, and the latter build upon the former. Bramble is the reimplementation in Rust of the bramble stack of protocols, which enable the exchange of messages between peers over the Tor network. These messages are binary strings, the meaning and syntax of which is determined by the consuming application, as such bramble can be used to build arbitrary P2P applications that communicate over the Tor network. Storm is a cross-platform application that uses bramble to exchange text messages between peers.

The Need For Mapped Futures

The implementation details of bramble were such that it was necessary to efficiently track and advance many async operations at a time. Each operation could be associated with a key, the composite of the message hash and the peer its being sent or received from, so I searched for a library that could help. Instead I found only people requesting this feature from an existing module, FuturesUnordered, part of the main Futures library. So I decided to extract that module, add the features I needed, and republish it.

Implementation

The original FuturesUnordered essentially consists of two linked lists. One list is holds all the futures, and another list holds the futures which have been woken somewhere else and remain to be polled. You may be aware that Rust's async model is such that Futures do not make progress on their own, but must be polled, and can expose a wake function which may be called to indicate that they are ready to be polled. When a future which is in FuturesUnordered is woken, it is moved to the "ready-to-run" queue, and when it is polled, if the future completes, the futures is removed and the result returned, and if it is incomplete, it is removed from the ready queue. My library works the same, but adds a HashSet of Task structs, each task containing the relevant future, which as a result of using atomic pointers to the contents, can be used to access the futures by their key by accessing into the hash set, even while the futures are contained in the linked list. Most of the complexity in the library comes from unsafe code by accessing pointers across thread boundaries, as well as from the complexity of the linked lists, which are notoriously difficult to implement in rust.

The project was well received, has prompted 20,000 downloads so far, and I have accepted multiple PRs or made updates, mainly to fix bugs or unsoundness issues.