scala/scala — pull request #2674 by richdougherty (2013-06-23 08:00:19+00:00)
Title: SI-7336 Link flatMapped promises to avoid memory leaks

This patch addresses a bug (or missing optimisation) in Future.flatMap which can lead to memory leaks. We [see these leaks in Play](https://github.com/playframework/Play20/issues/1084) because Play iteratees use futures extensively.

Backward binary compatibility is preserved by this patch. Several new methods are introduced to DefaultPromise (theoretically a "private" class) to allow linking promises together. These new methods have been whitelisted for forward binary compatibility. Strictly speaking, only a single method new method to link promises is really needed. But if we're going to introduce one new method, we may as well introduce three, right? :wink:

The patch is split into two changes. The first change can be cherry-picked into master. The second change has changes to preserve backward binary compatibility and whitelist forward binary compatibility.

This fix is based is based on the [Twitter promise implementation](https://github.com/twitter/util/blob/master/util-core/src/main/scala/com/twitter/util/Promise.scala#L421). The current Scala implementation uses onComplete handlers to propagate the ultimate value of a flatMap operation to its promise. Recursive calls to flatMap build a chain of onComplete handlers and promises. Unfortunately none of the handlers or promises in the chain can be collected until the the handlers are called and detached, which only happens when the final flatMap future is completed. (In some situations, such as an infinite stream, this may never actually happen.) Because of the fact that the promise implementation internally creates references between promises, and these references are invisible to user code, it is too easy for user code to accidentally build a large chain of promises and leak memory. See the included test which quickly exhausts JVM memory with a simple recursive loop—but not once this patch is applied. Even knowing about the internal problem, it is difficult to avoid this kind of leak without avoiding flatMap entirely.

Both the Twitter implementation and this patch solve the problem of leaks by automatically breaking these chains of promises, so that promises don't refer to each other in a long chain. This allows each promise to be individually collected. The idea is to "flatten" the chain of promises, so that instead of each promise pointing to its neighbour, they instead point directly the promise at the root of the chain. This means that only the root promise is referenced, and all the other promises are available for garbage collection if they're not referenced by user code.

To make the chains flattenable, the concept of linking promises together becomes an explicit feature in the promise implementation. This allows the implementation to navigate and rewire links as needed. A DefaultPromise gets a new state: being linked to another DefaultPromise. See the scaladoc for more details.

In practice, flattening the chain cannot always be done perfectly. When a promise is added to the end of the chain, it scans the chain and links directly to the root ("canonical") promise. But the root promise for a chain can change, which will leave all previously-linked promise pointing at a the old, now non-root, promise, rather than the new root promise. To mitigate the problem of the root promise changing, whenever any linked promise's methods are called, and it needs a reference to its root promise, it re-scans the promise chain and relinks itself directly to whatever the current root promise is, even if that promise has changed. Basically, rescanning and relinking occur at every possible opportunity. Unfortunately, even this eager relinking doesn't absolutely guarantee that the chain will be flattened and that leaks cannot occur. However it does greatly reduces the chance that they will occur.

To *guarantee* no leaks we'd probably need to retain backwards references when the root promise changed, and update all the promises pointing to the old root promise. These backward references would need to be weak references to prevent leaks. Changing the root promise would become a very expensive operation, which would be unfortunate, as most of the updated promises would be garbage anyway and updating them would be wasted work. Personally, I think mainting backwards weak references is too expensive to justify. So we are left with a fast and cheap implementation that does a pretty good, but not perfect, job of flattening promise chains.

The re-scanning and relinking code in this patch actually differs from the code in the Twitter implementation. The Twitter implementation [relinks *all* promises](https://github.com/twitter/util/blob/master/util-core/src/main/scala/com/twitter/util/Promise.scala#L542) it encounters as it scans for the root promise, whereas this patch only relinks a *single* promise. The reason for this is that the Twitter implementation uses the stack to store promises as it updates them, and so risks a stack overflow. In other words, the Twitter code is slightly more aggressive about flattening the promise chain, but runs the (admittedly small) risk of a overflowing the stack. The code in this patch does less flattening—so might leak memory in more cases—but cannot overflow the stack. There is a trade off with no clear best answer. I'd be interested to hear other opinions.