Communications of the ACM

posed together to create a service that behaves in a desirable way.

As with futures, combining filters and services does not change the underlying, constituent components. It creates a new service with new behavior but does not change the meaning of either underlying filter or service. This again enhances reasoning since the constituent components stand on their own; we need not reason about their interactions after they are combined.

Futures, services, and filters form the foundation upon which server software is built at Twitter. Together they support both modularity and reuse: we define applications and behaviors independently, composing them together as required. While their application is pervasive, two examples nicely illustrate their power. First, we implemented an RPC tracing system à la Dapper10 as a set of filters, requiring no changes to application code. Second, we implemented backup requests2 as a small, self-contained filter.

Conclusion

“Don’t tie the hands of the implementer.”

—Martin Rinard Functional programming promotes thinking about building complex behavior out of simple parts, using higher-order functions and effects to glue them together. At Twitter we have applied this line of thinking to distributed computing, structuring systems around a set of core abstractions that express asynchrony through effects and that are composable. This allows building complex systems from components with simple semantics that, preserved under composition, makes it easier to reason about the system as a whole.

This approach leads to simpler and more modular systems. These systems promote a good separation of concerns and enhance flexibility, while at the same time permitting efficient implementations.

Functional programming has thus
furnished essential tools for managing
the complexity that is inherent in mod-
ern software—untying the hands of the
implementer.

Acknowledgments

Thanks to Jake Donham, Erik Meijer, Mark Compton, Terry Coatta, Steve Jenson, Kevin Oliver, Ruben Oanta, and Oliver Gould for their guidance on earlier drafts of this article. Early versions of the abstractions discussed here were designed together with Nick Kallen; numerous people at Twitter and in the open source community have since worked to improve, expand, and solidify them.

Related articles on queue.acm.org

Scalable SQL

Michael Rys

http://queue.acm.org/detail.cfm?id=1971597

Evolution and Practice: Low-latency Distributed Applications in Finance

Andrew Brook

http://queue.acm.org/detail.cfm?id=2770868

Distributed Development Lessons Learned

Michael Turnlund

http://queue.acm.org/detail.cfm?id=966801

References

1. Barroso, L. A., Clidaras, J. and Hölzle, U. The datacenter as a computer: an introduction to the design of warehouse-scale machines. Synthesis Lectures on Computer Architecture 8, 3 (2013), 1–154.

2. Dean, J. and Barroso, L.A. The tail at scale. Commun.

ACM 56, 2 (Feb. 2013), 74–80.

3. Dijkstra, E. W. Solution of a problem in concurrent programming control. Commun. ACM 8, 9 (Sept. 1965),

569.

4. Eriksen, M. Your server as a function. In Proceedings of the 7th Workshop on Programming Languages and Operating Systems. ACM (Nov. 2013), 5.

5. Eriksen, M. and Kallen, N. Finagle, 2010; http://twitter.

github.com/finagle.

6. Eriksen, M. and Kallen, N. Util, 2010; http://twitter.

github.com/util/.

7. Hughes, J. Why functional programming matters. The Computer Journal 32, 2 (1989), 98–107.

8. Netflix. Hystrix; https://github.com/Netflix/Hystrix.

9. Ousterhout, J. Why threads are a bad idea (for most purposes). In presentation given at the Usenix Annual Technical Conference, 1996.

10. Sigelman, B.H., Barroso, L.A., Burrows, M., Stephenson,
P., Plakal, M., Beaver, D., Jaspan, S. and Shanbhag,
C. Dapper, a large-scale distributed systems tracing
infrastructure. Technical report, Google. 2010, 36.

11. Smolka, G. The Oz programming model. Computer Science Today. Jan van Leeuwen, ed. Lecture Notes in Computer Science 1000 (1995), 324–343. Springer-Verlag, Berlin.

12. Sutter, H. The free lunch is over: a fundamental turn toward concurrency in software. Dr. Dobb’s J. 30, 3

(2005): 202–210.

Marius Eriksen ( marius@twitter.com) is a principal engineer in Twitter’s systems infrastructure group. He works on all aspects of distributed systems and server software and is currently working on data management and integration systems; he also chairs Twitter’s architecture group. Twitter @marius.

Copyright held by owner/author.

Publication rights licensed to ACM. $15.00

Figure 5. Scatter-gather lookup with resiliency measures.

val downgradeToNull: Filter[String, String] = Filter((key, service) => { } })

Another filter short-circuits requests for useless keys (these are known as stopwords in search engines), so that they don’t inflict needless load on the underlying service:

val stopwords: Set[String] …
val stopwordFilter: Filter[String, String] =
Future.value(null)
else
service.apply(key)
})

Finally, the two filters are combined and then applied to all of the services.

val resiliencyFilter: Filter[String, String] = stopwordFilter.andThen(downgradeToNull)

def resilientMultipleLookup(services: Service[String, String]) = { val resilientServices = services.map { service => resiliencyFilter.andThen(service) } multipleLookup(resilientServices)