SoK: Eternal War in Memory - Szekeres et al. 2013 SoK stands for 'Systematization of Knowledge' - and in this case Szekeres et al. provide a wonderful conceptual framework and overview of memory corruption attacks and the defenses against them. As you'll see, defending against these attacks is non-trivial - especially if you are concerned … Continue reading SoK: Eternal War in Memory
Month: November 2015
Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections
Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections - Steinforder & Vinju, 2015 You'd think that the collection classes in modern JVM-based languages would be highly efficient at this point in time - and indeed they are. But the wonderful thing is that there always seems to be room for improvement. Today's … Continue reading Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections
Asynchronous Complex Analytics in a Distributed Dataflow Architecture
Asynchronous Complex Analytics in a Distributed Dataflow Architecture - Gonzalez et al. 2015 Here's a theme we've seen before: the programming model offered by large scale distributed systems doesn't always lend itself to efficient algorithms for solving certain classes of problems. In today's paper, Gonzalez et al. examine the growing gap between efficient machine learning … Continue reading Asynchronous Complex Analytics in a Distributed Dataflow Architecture
FIT: A Distributed Database Performance Trade-off
FIT: A Distributed Database Performance Trade-off - Faleiro & Abadi, 2015 If the CAP FITs... This paper presents the FIT trade-off for distributed transactions: you can have any two of Fairness, (strong) Isolation, and Throughput, but not all three. Which also implies you can have both strong isolation and high throughput! As a consequence of … Continue reading FIT: A Distributed Database Performance Trade-off
GD-Wheel: A Cost-Aware Replacement Policy for Key-Value Stores
GD-Wheel: A Cost-Aware Replacement Policy for Key-Value Stores - Li & Cox 2013 One of the wonderful things about reading papers and being exposed to lots of different problems and their solutions is that you never know when an idea might resurface and be useful in a new context or challenge you are facing. Yesterday … Continue reading GD-Wheel: A Cost-Aware Replacement Policy for Key-Value Stores
Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility
Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility - Varghese & Lauck 1987 Yashiro Matsuda recently wrote a blog post describing Apache Kafka's use of Hierarchical Timing Wheels to keep track of large numbers of outstanding requests. In the Kafka use case, each request lives in a 'purgatory' … Continue reading Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility
Moving Fast with Software Verification
Moving Fast with Software Verification - Calcagno et al. 2015 This is a story of transporting ideas from recent theoretical research in reasoning about programs into the fast-moving engineering culture of Facebook. The context is that most of the authors landed at Facebook in September of 2013, when we brought the INFER static analyser with … Continue reading Moving Fast with Software Verification
Fail at Scale & Controlling Queue Delay
Controlling Queue Delay - Nichols & Van Jacobsen, 2012, and Fail at Scale - Maurer, 2015 Fail at Scale (Maurer) Ben Maurer recently wrote a great article for ACM Queue on how Facebook achieves reliability in the face of rapid change: To keep Facebook reliable in the face of rapid change we study common patterns … Continue reading Fail at Scale & Controlling Queue Delay
Minimizing Faulty Executions of Distributed Systems
Minimizing Faulty Executions of Distributed Systems - Scott et al. Now that we've spent a couple of days looking at test case minimizing for sequential systems, we're ready to tackle Colin Scott et al.'s paper on doing the same for executions of distributed systems. This is the paper that describes the core system behind Colin's … Continue reading Minimizing Faulty Executions of Distributed Systems
Hierarchical Delta Debugging
Hierarchical Delta Debugging - Misherghi & Su, 2006 The thing I find striking about the delta debugging approach we saw yesterday is that with no understanding of the syntax of the input at all, it is still able to simplify, for example, a C program - despite the fact that nearly all of the subsets … Continue reading Hierarchical Delta Debugging
the morning paper 