Metadata

Daily batch processes introduce significant latency, since input changes reflected in the output only after a day. For fast paced business, this is too slow. To reduce delays, stream processing occurs more frequently (e.g., every second) or continuously, where events are handled as they happen.  In stream processing, a record is typically called an event—a small, immutable object containing details of an occurrence, often with a timestamp. Polling for new events becomes costly when striving for low-latency continuous processing. Frequent polling increases overhead as most requests return no new data. Instead, systems should notify consumers when new events are available. Messaging systems handle this by pushing events from producers to consumers. Direct messaging systems require application code to handle message loss and assume producers and consumers are always online, limiting fault tolerance. Message brokers (or message queues) improve reliability by acting as intermediaries. P...

Batch processing allows large-scale data transformations through bulk-synchronous processing. The simplicity of this approach allowed building reliable, scalable, maintainable applications with it. If you recall, "reliable-scalable-maintainable" was what we set out to learn when we began the DDIA book. This story of MapReduce starts when Google engineers realize there were a lot of repetitive tasks involved when computing over large data. These tasks often involved individually processing elements and then gathering and fusing their output. Interestingly, this bores a striking resemblance to electromechanical IBM card-sorting machines from the 1940-50s. MapReduce also got some inspiration from the map reduce operations in Lisp: (map square '(1 2 3 4)) gives us  (1 4 9 16), and (reduce + '(1 4 9 16))  gives us 30. The key innovation of Google's MapReduce framework was its ability to simplify parallel processing by abstracting away complex network communication and ...

Incremental computation represents a transformative (!) approach to data processing. Instead of recomputing everything when your input changes slightly, incremental computation aims to reuse the original output and efficiently update the results. Efficiently means performing work proportional only to input and output changes. This paper introduces DBSP, a programming language inspired by signal processing (hence the name DB-SP). DBSP is  simple, yet it offers extensive computational capabilities. With just four operators, it covers complex database queries, including entire relational algebra, set and multiset computations, nested relations, aggregations, recursive queries, and streaming computations. Basic DBSP operators  The language is designed to capture computation on streams. Streams are represented as infinite vectors indexed by consecutive time. Each stream can represent values of any type and incorporates basic mathematical operations like addition, subtraction, and ...

This paper, which appeared in OSDI 2018 , considers the question of how to design a read-optimized RDBMS database with built-in support for caching and fast lookup answers to complex queries. The resulting system, Noria is implemented in Rust, and is available as opensource at https://github.com/mit-pdos/noria . There are already two good summaries written of the paper (from Adrian Colyer and Micah Lerner ), so my job today will be simpler. Artwork created by Stable Diffusion Motivation and overview Databases (mostly relational databases) are overwhelmingly used with read-heavy workloads due to all those SQL querying they serve, but they fail to take advantage of this and improve their designs to optimize for read-heavy workloads. Some crutch solutions was added to address this: memcached, read-only replicas etc., but these have shortcomings. Many deployments employ an in-memory key-value cache (like Redis, memcached, or TAO) to speed up common-case read queries. Such a cache avoids r...

This paper is by Stephanie Wang (UC Berkeley), John Liagouris (ETH Zurich), Robert Nishihara (UC Berkeley), Philipp Moritz (UC Berkeley), Ujval Misra (UC Berkeley), Alexey Tumanov (UC Berkeley), Ion Stoica (UC Berkeley). I really liked this paper. It has a simple idea, which has a good chance of getting adopted by real world systems. The presentation was very well done and was very informative. You can watch the presentation video here. Low-latency processing is very important for data processing, stream processing, graph processing, and control systems. Recovering after failures is also important for them, because for systems composed of 100s of nodes, node failures are part of daily operation. It seems like there is a tradeoff between low latency and recovery time. The existing recovery methods either have low runtime overhead or low recovery overhead, but not both. Global checkpoint approach to recovery achieves a low runtime overhead, because a checkpoint/snapshot can be ta...

Companies care about cheap computing. Well, the first thing they care about is usability: Is it easy for average programmers to develop solutions using the framework? And the second thing they care about is cheap computing: Does this break the bank? Can I do this cheaper? Speed, efficiency, elegance, technical strength... These are often not of interest. People are OK with their analytic jobs return results hours later. We watched aghast, at the beginning of Hadoop epidemic, people use MapReduce for doing analytics in a wasteful and slow manner. I was recently thinking about this question: How can we trade-off speed with monetary cost of computing?  If the constraints are that the user will not need the results before a couple hours but it would be nice to get the results in a day, what is the cheapest way to get this analytics job done in the cloud? While distributed systems may be the answer for a lot of questions (such as providing fault-tolerance, low-latency access f...

This paper appeared in Eurosys 2018 and is authored by Hang Qu, Omid Mashayekhi, Chinmayee Shah, and Philip Levis from Stanford University. I liked the paper a lot, it is well written and presented. And I am getting lazy, so I use a lot of text from the paper in my summary below. Problem motivation  In data processing frameworks, improved parallelism is the holy grail because it can get more data processed in less time. However, parallelism has a nemesis called the control plane . While, control plane can have a wide array of meaning, in this paper control plane is defined as the systems and protocols for scheduling computations, load balancing, and recovering from failures. A centralized control frame becomes a bottleneck after a point. The paper cites other papers and states that a typical cloud framework control plane that uses a fully centralized design can dispatch fewer than 10,000 tasks per second. Actually, that is not bad! However, with machine learning (ML) app...

This article, by Jimmy Lin, looks at the Lambda and Kappa architectures, and through them considers a larger question: Can one size fit all? The answer, it concludes, is it depends on what year you ask! The pendulum swings between the apex of one tool to rule them all , and the other apex of multiple tools for maximum efficiency . Each apex has its drawbacks: One tool leaves efficiency on the table, multiple tools spawns integration problems. In the RDBMS world, we already saw this play out. One size RDBMS fitted all, until it couldn't anymore. Stonebraker declared "one size does not fit all", and we have seen a split to dedicated OLTP and OLAP databases connected by extract-transform-load (ETL) pipelines. But these last couple years we are seeing a lot of one size fits all "Hybrid Transactional/Analytical Processing (HTAP)" solutions being introduced again. Lambda and Kappa OK, back to telling the story from the Lambda and Kappa architectures perspecti...

This paper, dated March 11, 2017 on arxiv, is from UB Berkeley.   Here is Prof. Michael Jordan's Strata Hadoop conference talk on this. The paper first motivates the need for real-time machine learning. For this it mentions in-situ reinforcement learning (RL) that closes the loop by taking actions that affect the sensed environment. (The second paragraph mentions that such RL can be trained more feasibly by using simulated/virtual environments: by first trying multiple actions [potentially in parallel] to see their affect in simulation before interacting with the real world. Again this requires real-time performance as the simulation should be performed faster than real-time interaction.) Based on this application scenario, here are their desired requirement from the ML platform. R1: low latency R2: high throughput R3: dynamic task creation (RL primitives such as Monte Carlo tree search may generate new tasks during execution) R4: heterogeneous tasks (tasks would have wide...

This paper is by Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and David Maier. It appears in October 2017 issue of ACM Transactions on Database Systems. A preliminary conference version appeared in ICDE 2014.  This paper builds a theory of dataflow/stream-processing programs, which cover the Spark , Storm, Heron , Tensorflow , Naiad, TimelyDataflow work. The paper introduces compositional operators of labels, and shows how to infer the coordination points in dataflow programs. When reading below, pay attention to the labeling section, the labels "CR, CW, OR, OW", and the section on reduction rules on labels. To figure out these coordination points, the Blazes framework relies on annotations of the dataflow programs to be supplied as an input. This is demonstrated in terms of a Twitter Storm application and a Bloom application. The paper has many gems.  It says at the conclusion section in passing that when designing systems, we should pay attention to coordinat...