MIT's Noria Cuts Cache Memory Two-Thirds, Outpaces MySQL 18-Fold

Thesis: Partial State in Dataflow-Based Materialized Views — Jon Gjengset

Jon Gjengset

Allowing materialized views to hold partial state and resolve missing records on demand eliminates ad hoc application caching while preventing the memory exhaustion typical of traditional stream processors.

AI-assisted summary of Thesis: Partial State in Dataflow-Based Materialized Views — original source. Check the original for full context.

Source published:

Key ideas

  • Jon Gjengset introduces partial state in dataflow materialized views, allowing entries to be missing and reconstructed on demand to act as an automatic, transparent database cache. (0:00)
  • Noria resolves missing view state via backward-propagating 'upqueries' that elicit normal forward delta responses, eliminating redundant backward-execution query engines. (15:52)
  • Incongruent join deadlocks and staleness hazards caused by missing upstream state are safely resolved by pushing evictions downstream instead of stalling the pipeline on synchronous queries. (32:50)
  • Evaluated against a synthetic Lobste.rs benchmark, partial-state Noria achieved ~7,500 pages/second—an 18x throughput increase over MySQL and a 67% improvement over fully stateful Noria while reducing memory usage by roughly two-thirds. (36:01)

Detailed notes

## Background This video was published on YouTube by Jon Gjengset on October 23, 2020. It captures his virtual PhD dissertation defense at MIT from the previous day, presenting his research on using partially stateful materialized views in the Noria database system to transparently cache read-heavy application workloads.

## TL;DR In read-heavy web applications, traditional relational databases waste significant compute re-executing identical queries, forcing engineers to build brittle, ad hoc caching layers. Jon Gjengset introduces partially stateful materialization in Noria, an architecture that treats materialized views as dynamic caches by deliberately allowing state to be missing or evicted. When cache misses occur, backward-propagating 'upqueries' reconstruct required data on demand through dataflow paths, while tricky edge cases like incongruent joins are resolved by downstream evictions rather than blocking data pipelines. Benchmarks using the Lobste.rs workload demonstrate that partial state achieves up to an 18x throughput increase over MySQL, uses two-thirds less memory than fully stateful views, and performs within a factor of two of an idealized Redis cache while retaining a SQL interface.

## Atmosphere & style The presentation carries the polished, scholarly weight of an MIT doctoral defense balanced by Gjengset's approachable, systems-hacker charisma. Following a warm, heartfelt introduction from his advisor Robert Morris, Gjengset delivers a lucid, fast-paced technical narrative that methodically unpacks complex concurrency hazards with dry wit and clarity. The session transitions from rigorous database theory and benchmark graphs to sincere personal vulnerability during the closing acknowledgments, evoking the relief and profound gratitude of culminating six years of intense academic labor.

## Bulletin - [00:00](https://www.youtube.com/watch?v=GctxvSPIfr8&t=0s) Jon Gjengset introduces partial state in dataflow materialized views, allowing entries to be missing and reconstructed on demand to act as an automatic, transparent database cache. - [15:52](https://www.youtube.com/watch?v=GctxvSPIfr8&t=952s) Noria resolves missing view state via backward-propagating 'upqueries' that elicit normal forward delta responses, eliminating redundant backward-execution query engines. - [32:50](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1970s) Incongruent join deadlocks and staleness hazards caused by missing upstream state are safely resolved by pushing evictions downstream instead of stalling the pipeline on synchronous queries. - [36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) Evaluated against a synthetic Lobste.rs benchmark, partial-state Noria achieved ~7,500 pages/second—an 18x throughput increase over MySQL and a 67% improvement over fully stateful Noria while reducing memory usage by roughly two-thirds.

## Key takeaways - [02:06](https://www.youtube.com/watch?v=GctxvSPIfr8&t=126s) Modern web applications suffer from a structural read-write asymmetry where read queries repeatedly execute expensive aggregations and joins over identical data. - [04:02](https://www.youtube.com/watch?v=GctxvSPIfr8&t=242s) Manual application caching (e.g., Redis or denormalization) introduces severe failure modes, including cache invalidation bugs, thundering herds, and complex eviction logic. - [07:05](https://www.youtube.com/watch?v=GctxvSPIfr8&t=425s) Materialized views maintain query results incrementally via deltas, but traditional systems hold full state and cater to low-frequency analytical workloads rather than high-throughput web reads. - [08:25](https://www.youtube.com/watch?v=GctxvSPIfr8&t=505s) Noria structures computation as a push-based dataflow graph where updates propagate along edges as positive and negative relational deltas. - [14:08](https://www.youtube.com/watch?v=GctxvSPIfr8&t=848s) Real-world web access patterns are heavily skewed, making the complete materialization of traditional views wasteful in terms of both memory and maintenance computation. - [15:52](https://www.youtube.com/watch?v=GctxvSPIfr8&t=952s) Parameterized view definitions allow Noria to explicitly identify missing entries and trigger targeted upqueries along existing dataflow edges on cache misses. - [15:52](https://www.youtube.com/watch?v=GctxvSPIfr8&t=952s) Upquery responses travel forward as regular dataflow deltas, unifying on-demand cache population with streaming view maintenance. - [20:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1207s) Partial state enables aggressive compute pruning: intermediate operators discard incoming delta updates for keys that are not currently materialized downstream. - [24:42](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1482s) Noria relies on eventual consistency to decouple fast reads from write pipelines, avoiding the heavy coordination overhead present in traditional stream processors. - [25:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1548s) Partially stateful graphs introduce correctness risks such as concurrent upquery-delta races and incongruent join staleness. - [28:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1681s) Incongruent joins—where the join key differs from the downstream query key—can deadlock streaming pipelines if forced to block on missing attribute lookups. - [32:50](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1970s) Noria escapes incongruent join deadlocks by emitting downstream evictions, letting future reads safely re-materialize data on demand via standard upquery pathways. - [36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) On a synthetic Lobste.rs benchmark, partially stateful Noria sustained ~7,500 pages per second, outperforming denormalized MySQL (400 pages/sec) and fully stateful Noria (4,500 pages/sec). - [36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) Partial materialization lowered Noria's active memory footprint from over 100 GB down to approximately 34 GB under comparable benchmark workloads. - [39:13](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2353s) In an idealized single-query benchmark, Noria achieved read throughput within a factor of two of a theoretical 16-core Redis ceiling while preserving full SQL abstractions. - [41:18](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2478s) Future research directions include supporting range queries and streaming windows, integrating Noria as an external cache in front of existing relational databases, and utilizing partial state for fast node recovery.

## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=GctxvSPIfr8&t=0s) Advisor Introduction and Thesis Overview

Robert Morris introduces Jon Gjengset for his virtual doctoral dissertation defense at MIT, praising Jon's research vision for how high-traffic web applications should manage their data. Beyond his technical contributions, Morris highlights Jon's active involvement in the broader community—ranging from his infinite patience as a teaching assistant, to organizing events for graduate students, to live-streaming systems programming tutorials. Noting that Jon will be deeply missed across MIT if the committee approves his graduation, Morris remarks:

> "Jon's sure to be valuable and valued whatever he sets his hand to. And assuming his committee lets him go, many people at MIT are going to miss him."

Jon takes over and frames his talk on *Partial State in Dataflow-Based Materialized Views*, setting the ambitious goal of condensing roughly six years of PhD work into 45 minutes so that attendees understand what the title means and why the work matters. He acknowledges his supervisory committee—Robert Morris, Frans Kaashoek, Sam Madden, and Malte Schwarzkopf—who worked alongside him to ensure the research was both rigorous and practically valuable. Addressing the foundational question of why he is giving the talk, Jon states:

> "I am here because I want to make databases better."

[02:06](https://www.youtube.com/watch?v=GctxvSPIfr8&t=126s) The Read-Heavy Web and the Problem with Traditional Databases

To explain how databases can be improved, Jon reviews basic relational database mechanics using a toy schema with two tables: `stories` and `votes`. Applications interact with the database by submitting read queries—operations that aggregate, filter, or join tables together to produce data the application cares about—or by submitting writes like inserts, updates, and deletes directly into the underlying tables. Although SQL technically categorizes all statements as queries, Jon clarifies that throughout the talk, "queries" refers strictly to read operations like `SELECT`, whereas inserts, updates, and deletes are termed "writes" or "updates."

Jon points out a structural imbalance in database architectures: a simple write modifies a single table directly, whereas a read query often triggers substantial computational work across multiple relational operators. This mismatch is especially painful for modern web applications, which are overwhelmingly read-heavy. Because applications execute thousands of reads for every write, the most frequent operation is also the most expensive. Applications routinely submit identical or near-identical queries over and over again, forcing the database engine to waste compute cycles repeatedly calculating the same results.

```mermaid flowchart TD accTitle: Traditional Database Read vs Write Asymmetry accDescr: Visual comparison showing writes executing directly on tables while reads pass through multiple relational operators.

subgraph Reads ["Read Query (Expensive)"] Q["SELECT Query"] --> AGG["Aggregation (Count)"] AGG --> JOIN["Join Engine"] end

subgraph Storage ["Base Tables"] JOIN --> T1["stories Table"] JOIN --> T2["votes Table"] W["INSERT / UPDATE / DELETE"] -->|"Direct Write"| T2 end ```

[04:02](https://www.youtube.com/watch?v=GctxvSPIfr8&t=242s) The Pitfalls of Ad Hoc Application Caching

A standard remedy to reduce database read pressure is placing an external cache, such as an in-memory key-value store, in front of the database. When an application queries the system, it first inspects the cache; on a hit, it returns immediately with low latency, hitting the backend database only on a cache miss. Other developers achieve similar benefits via denormalization—such as storing a precomputed vote tally directly within the `stories` table. However, Jon emphasizes that while caching sounds straightforward in theory, delegating cache management to application code creates immense operational complexity.

Whenever underlying data changes—such as when a user casts a new vote—the cached count becomes stale. The specific application path executing that write is now obligated to invalidate or refresh that cache entry. Furthermore, coordinating cache misses introduces severe failure modes. If 100,000 concurrent users request a story that is not cached, naive application logic can trigger a thundering herd, where all 100,000 requests swarm the backend database simultaneously to compute the identical query. Developers must also orchestrate which worker writes the computed result back into the cache and determine eviction policies to purge old or unpopular entries before memory runs out. Jon summarizes the burden placed on software engineers:

> "And hopefully this image gives you an idea of just all the stuff that needs to be figured out by the application developers in order to make databases serve these kinds of read-heavy workloads."

Rather than forcing developers to invent custom, brittle caching layers, Jon's research focuses on automatic database caching: moving all eviction, miss handling, and invalidation logic out of the application and embedding it transparently inside the database itself.

[07:05](https://www.youtube.com/watch?v=GctxvSPIfr8&t=425s) Materialized Views and Incremental Maintenance

To explain how automatic caching can be implemented, Jon deconstructs his thesis title from right to left, beginning with *materialized views*. First introduced by database researchers in the early 1980s, a materialized view simply executes a query and stores the evaluated result for future retrieval, behaving functionally like a cache. The central engineering challenge is view maintenance: how the stored materialization stays accurate when underlying base tables change.

Ideally, materialized view maintenance must be incremental. If a story already has 100,000 votes and a single new vote arrives, the database should not scan all 100,001 rows to recompute the count from scratch. Instead, it should simply take the existing count and increment it by one. Systems also face an architectural design choice between eager maintenance on write (proactively updating the view as soon as a mutation occurs) or lazy maintenance on demand (deferring the update until a subsequent read query requests the data).

- Materialized views date back to the early 1980s in database literature. - Incremental maintenance computes deltas instead of re-executing entire queries from scratch. - Systems choose between write-time proactive maintenance and read-time lazy maintenance.

[08:25](https://www.youtube.com/watch?v=GctxvSPIfr8&t=505s) Dataflow-Based Computation and the Noria Model

Jon moves to the next phrase in the title: *dataflow-based*. Within computer systems, dataflow represents an architectural style where data moves directly to compute, rather than having compute routines reach out and pull data from storage tables. It functions as a push-based processing model where underlying database modifications propagate through a directed acyclic graph of relational operators, including joins, aggregations, and filters.

In this dataflow graph, edges represent data dependencies. A join operator depends on its incoming input streams, and an aggregation depends on the upstream data being grouped. The messages exchanged between operators along these edges are *deltas*. A delta is structured like a full database row with typed columns, accompanied by an explicit positive (`+`) or negative (`-`) sign. A positive delta signals the arrival of a new or updated row that should be added to the result, whereas a negative delta represents a retraction or deletion of a previously produced row. Jon explains that this dataflow model serves as the foundation for Noria, an eventually consistent materialized view system.

Jon presents a concrete example of how Noria transforms a SQL query into an incremental dataflow graph. Using a query that constructs a materialized view named `StoryWithVC` (Story With Vote Count), the query joins the `stories` and `votes` tables on story ID and aggregates the total votes per story using `GROUP BY stories.id`. As changes arrive at the base tables, Noria pushes delta records through the aggregation and join operators, keeping the final view updated in real time.

[11:02](https://www.youtube.com/watch?v=GctxvSPIfr8&t=662s) Incremental Maintenance and Delta Propagation in Noria

When mapping a relational query into a dataflow graph, the individual relational operators appear directly as graph nodes. For example, an aggregation such as a count on votes grouped by `story_id` is represented by an aggregation operator, while the combination of stories and votes is handled by a join operator. In a naive translation, one might expect the join to sit directly between the base `stories` and `votes` tables, but Noria’s query optimizer can reorder these operations for efficiency. As Jon Gjengset points out regarding the aggregation running before the join: “Noria has decided that it's going to do the aggregation first for optimization purposes.” When an application reads from the final materialized view at the bottom of the graph—named `StoryWithVC` (stories with vote count)—it issues a parameterized query such as `SELECT * FROM StoryWithVC WHERE id =?`, using the runtime parameter as a lookup key to retrieve only the specific record it needs.

Whenever underlying base tables mutate, Noria incrementally updates the downstream materialized view via streaming deltas. If a new vote arrives for a given story (say, story 7), the change is injected into the dataflow graph at the `votes` table node and flows along the graph edges toward the view. As deltas pass through intermediate operators, they are transformed. The vote count operator converts the incoming `+1` increment into a negative delta for the old count alongside a positive delta for the new count: `- (7, 42)` and `+ (7, 43)`. Jon explains that one can think of this emitted message as communicating: “It used to be that the count for story 7 was 42. Forget that, it is now 43.” When these deltas arrive at the join operator, the join reads the `stories` table to stitch on the missing story columns, producing combined output deltas that update the `StoryWithVC` materialized view in place so subsequent application reads immediately observe the new count.

- Base table changes enter the dataflow graph as delta records at table root nodes. - Aggregation operators replace raw increments with explicit retraction and insertion pairs (e.g., subtracting old count 42 and adding new count 43 for key 7). - Join operators enrich streaming deltas by looking up required attribute columns from sibling table state before forwarding updates downstream.

---

[14:08](https://www.youtube.com/watch?v=GctxvSPIfr8&t=848s) The Case for Partial State: Learning to Forget

Traditional materialized view systems compute and maintain complete answers for every possible key, an approach that wastes massive amounts of memory and CPU cycles on data that may never be accessed again. Jon introduces the core thesis contribution—partial state—summarizing the fundamental philosophy as “learning to forget.” In typical real-world workloads, access distributions are heavily skewed: unpopular or ancient stories linger indefinitely in view memory without serving read traffic. Jon highlights this inefficiency directly: “The observation here is that the chances are most entries in any given view are not accessed.” Furthermore, repeatedly recalculating and maintaining up-to-date counts for stories no reader cares about squanders processing capacity that could otherwise serve active queries.

Under memory pressure, a system must be able to retain only the most popular, frequently accessed subset of records rather than keeping the entire universe of data hot. Standard materialized views offer no mechanism to evict stale entries and re-materialize them on demand because views are defined to materialize full relations. To resolve this tension, the dissertation articulates three principal contributions:

1. **The Notion of Missing State:** Explicitly allowing materialized views and intermediate operators to mark specific entries as absent, avoiding allocating memory to unread keys. 2. **The Mechanism of Upqueries:** An on-demand recursive query mechanism that traverses backward through the dataflow graph to backfill missing state over existing dataflow paths. 3. **Implementation and Evaluation in Noria:** Realizing partially stateful materialized views within a high-performance streaming database system to prove latency, throughput, and memory benefits.

---

[15:52](https://www.youtube.com/watch?v=GctxvSPIfr8&t=952s) Parameterized Views and Upquery Resolution

To support partial state, the database must know which key the application uses to partition and query the view. In traditional relational systems, the view definition and the application’s query over that view are decoupled; the view definition does not reveal what specific key the application will query at runtime. Jon resolves this by folding the query parameter directly into the view definition itself (e.g., `WHERE id =?`). Because the parameter is baked into the view schema, Noria knows exactly which key defines presence or absence. When an application queries `StoryWithVC` for story 7, Noria inspects the materialized view index. If story 7 is not present, it is represented as a missing entry—visualized as a hollow box.

```mermaid flowchart TD accTitle: Upquery and Delta Flow in Noria accDescr: An upquery travels backward from missing view state to stateful ancestors, which respond via regular forward dataflow.

subgraph Base["Base Tables"] Stories["stories Table"] Votes["votes Table"] end

subgraph Pipeline["Dataflow Pipeline"] Count["Count Operator<br/>(holds partial aggregation state)"] Join["Join Operator<br/>(stateless)"] end

subgraph View["Client Interface"] MV["StoryWithVC View<br/>(Missing entry: Story 7)"] App["Application Client"] end

App -->|"1. Query (id = 7)"| MV MV -.->|"2. Upquery(7)"| Join Join -.->|"3. Forward Upquery(7)"| Count Count -->|"4. Delta (+43 for 7)"| Join Stories -.->|"5. Lookup attributes"| Join Join -->|"6. Enriched Delta"| MV MV -->|"7. Query Response"| App ```

To resolve a cache miss, the view initiates an “upquery” up the dataflow graph, requesting that upstream operators re-transmit the historical deltas necessary to construct the state for that key. Jon describes the intuition behind this exchange: “You can think of it sort of as the downstream saying: ‘tell me about 7 again, because I forgot all about it’.” If an intermediate operator like the join is stateless, the upquery recurses further upstream. In this scenario, the join forwards the upquery to the count operator. Because the count operator maintains its own internal materialized view of past counts to calculate deltas, it can satisfy the upquery directly if story 7 is present in its internal state, avoiding recursing all the way back to the raw `votes` table.

Crucially, upqueries do not require dedicated backward-processing execution engines. When an upstream operator satisfies an upquery, it emits a standard delta message downstream over the normal forward dataflow graph. The message represents the current state of the requested key and is processed by the join exactly like any live update: the join looks up story 7 in the `stories` table, stitches the title and metadata to the vote count, and pushes the consolidated record to the materialized view. The materialized view fills in its missing entry and immediately returns the result to the client.

- View definitions incorporate parameter placeholders (`?`), tying partial indexing directly to runtime query access patterns. - Upqueries travel upward through graph edges until encountering an operator holding sufficient state to reconstruct the key. - Upquery responses travel forward along normal dataflow edges as standard dataflow deltas, avoiding redundant processing pipelines. - Once populated, subsequent reads for the same key hit the materialized view directly with zero upstream coordination.

---

[20:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1207s) Cache Eviction and Avoiding Unnecessary Computation

Because Noria can materialize state on demand, it can also safely evict state whenever memory is needed or entries fall out of use. If story 7 ceases to receive traffic, the system can reclaim memory by evicting story 7 from the downstream materialized view, from internal aggregation operator caches, or from both. Eviction transforms a populated entry back into missing state without breaking correctness: if a client ever requests story 7 months or years later, a new upquery will seamlessly re-materialize the row.

Beyond memory reduction, partial state yields dramatic compute savings by pruning updates for cold data. If the author of story 7 updates the story's title long after story 7 has been evicted from the views, the update delta propagates to the join operator. When the join attempts to look up the corresponding vote count in the aggregation operator's state, it discovers that story 7 is missing. Because the count state is missing, Noria knows that no downstream view is currently materializing story 7. The join safely drops the delta entirely instead of completing the join and computing updates for an unread view. Jon summarizes the power of this pruning rule: “And therefore there is nothing to update — there is no state for 7 downstream — and so don't need to update it and can discard this update entirely.”

- Inactive keys can be evicted at any layer of the dataflow graph to free memory for hot items. - Upstream delta updates that encounter missing sibling state in intermediate joins are discarded immediately, eliminating wasted CPU cycles on cold data. - The system achieves the dual benefits of dynamic caching and incremental view maintenance without requiring custom application-level cache invalidation code.

[22:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1327s) Traditional Materialized Views and Automated Caching

Materialized view systems have traditionally targeted workloads fundamentally different from high-throughput, read-heavy web applications. In typical deployments, materialized views exist to serve occasional queries run by human analysts. Because an analyst might want to run an intensely complex computation only periodically, running that query directly on raw data every time would take far too long. A materialized view maintains the result continuously behind the scenes so that when the analyst sits down, the report opens immediately. Because writes are frequent and read queries are rare, database research has overwhelmingly prioritized maintenance efficiency over read latency. It is completely acceptable in those systems if a read query performs a moderate amount of work at retrieval time, provided that work remains vastly smaller than executing the entire query from scratch.

Consequently, traditional systems rarely incorporate mechanisms for on-demand query evaluation or dynamic cache eviction. Their view definitions are usually pre-compiled into static query plans or standalone programs. As Gjengset observes: “And for similar reasons these systems rarely have support for eviction, because it's not really needed; the analyst's query is what it is.” There is no designated subset of an analytical view that takes precedence over any other portion of the dataset.

Automated caching systems developed in industry and academia similarly fall short of providing a drop-in database solution. Industrial caching systems are notoriously tailored to the hyper-specific architectural needs of the companies that invent them. A developer cannot easily take an internal infrastructure tool built by a large tech company and integrate it into a standard Ruby on Rails application. Furthermore, these systems rely primarily on cache invalidation rather than incremental maintenance: when an underlying row changes, entries are evicted instead of updated in place. That invalidation pattern leads to frequent cache misses and forces unnecessary trips back to the primary database. Most of these caching tools also operate above the storage layer, requiring tight coupling with a language-specific Object-Relational Mapping (ORM) framework rather than exposing an ergonomic, standard SQL interface featuring parameterized prepared statements.

- Traditional materialized views prioritize write-maintenance performance over read speed because reads are infrequent. - Analytical materialized views lack eviction mechanisms because all rows in the view are assumed to be equally relevant. - Industry automated caches rely on cache invalidation rather than incremental updates, leading to higher backend miss rates. - Caching layers typically require application-level ORM integrations rather than exposing a drop-in SQL view abstraction.

---

[24:42](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1482s) Stream Processing Systems and Consistency Trade-Offs

Dataflow and stream processing platforms share many design assumptions with traditional materialized views, concentrating heavily on ingestion throughput across sustained data pipelines. These stream engines tend to enforce strong consistency across their pipelines. However, guaranteeing strong consistency introduces a steep cost in read latency: read operations frequently have to coordinate directly with the write dataflow, in many cases traversing the exact same processing path as mutating writes to ensure uncorrupted views of the world.

Noria takes an alternative approach by taking advantage of eventual consistency. Because web applications tolerate brief moments of staleness, Noria bypasses strict stream-write coordination, serving instantaneous reads directly from its partially materialized views. Furthermore, existing stream processing platforms provide very limited support for on-demand computations or partial evictions. Once a stream query is initialized, it runs continuously across all data; evicting a specific subset of state from an intermediate operator requires tearing down and restarting the entire processing topology.

> “Whereas with Noria we can leverage the eventual consistency to give much faster results by leveraging the fact that the results are allowed to be stale.” — Jon Gjengset

---

[25:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1548s) Practical Challenges: Concurrency, Missing State, and Exactly-Once Updates

While the high-level concept of partial materialization is conceptually straightforward, executing it reliably in a production system reveals significant technical hazards. Gjengset notes with dry humor that while these hurdles complicate matters, “if it were, this thesis wouldn't be very valuable, and so I'm kind of glad that there are more challenges.” The fundamental requirement is ensuring that all data mutations to underlying base tables take effect exactly once in downstream views. A row inserted into a base table must neither vanish silently nor be applied multiple times to duplicate records. While traditional databases avoid this naturally by traversing indexes and physical disk pages once per query, partially stateful dataflow engines face continuous race conditions.

```mermaid flowchart TD accTitle: Concurrency Hazard Between Upqueries and Dataflow Updates accDescr: Diagram showing how an on-demand upquery and an in-flight delta update can conflict over the same record ID.

subgraph DataflowPaths["Concurrent Paths for Story 7"] UQ["Upquery: Fetches historical state for Story 7"] DF["Dataflow Update: Streaming delta for Story 7"] end

JoinOp["Join Operator / Downstream View"]

UQ -->|"Summarizes past state"| JoinOp DF -->|"Concurrently mutates state"| JoinOp

JoinOp --> Res["Risk: Exactly-once violations or permanent staleness"] ```

These hazards emerge from two distinct properties of the architecture:

1. **Concurrent upqueries and delta updates:** An upquery represents a snapshot summary of past historical state and preceding deltas for a specific key (such as `story 7`). However, an upquery may run concurrently with a live update flowing down through the dataflow graph for that exact same key. If the system fails to coordinate these overlapping operations, mutations may be double-counted or overwritten, violating exactly-once semantics. 2. **Premature update discarding:** In a partially stateful graph, operators discard updates when they encounter missing state in siblings to prevent storing unnecessary records. However, if an operator misidentifies missing state and discards an update that downstream views actually rely upon, those downstream materialized views become permanently stale and never heal.

The thesis catalogs numerous consistency hazards, with the presentation focusing specifically on the intricacies of incongruent join evictions.

---

[28:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1681s) The Mechanics of Incongruent Joins

The term "incongruent join" describes a join operator where the downstream query key differs from the internal join key. In a sample web scenario, an application maintains a `stories` base table with an `author_id` column, alongside a `users` table storing user metadata such as the author's display name. To present an article, the UI queries a view called `StoriesWithAuthor`, which joins `stories` and `users` to replace the raw numerical `author_id` with a textual `name`.

```mermaid flowchart LR accTitle: Incongruent Join Dataflow Architecture accDescr: Shows the stories table and users table feeding into a join operator, which outputs to a materialized view keyed differently.

subgraph Inputs["Upstream Tables"] S["Stories Table\nKey: story_id\nValue: author_id"] U["Users Table\nKey: author_id\nValue: name"] end

J["Join Operator\nJoin Key: author_id\nQuery Key: story_id"] MV["Materialized View\nStoriesWithAuthor\nIndexed on story_id"]

S -->|"Deltas / Upquery responses"| J U -->|"Author metadata"| J J -->|"Combined rows (id, author name)"| MV ```

In this query, the view is indexed and fetched by `story_id` (the query key), but the join operator correlates rows using `author_id` (the join key). When state is fully populated, handling an upquery is clean:

1. A client queries `StoriesWithAuthor` for `story 7`. 2. The read misses, emitting an upquery upstream to the stateless join operator. 3. The join passes the upquery upstream to the `stories` table. 4. The `stories` table resolves `story 7`, noting its `author_id` is `42`, and pushes a response delta downstream into the join. 5. The join uses `42` to query the `users` table, successfully retrieving the author's name (`Lena`). 6. The join stitches the story attributes and the author name together, forwarding the fully populated row downstream to fill the empty entry in the materialized view.

> “What makes this join incongruent is the fact that query key is different from the join key. The query key here is the story id, whereas the join key is the author id of the story.” — Jon Gjengset

---

[30:03](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1803s) Hazards of Incongruent Join Updates and Missing State

The system encounters severe correctness hazards when an incongruent join processes streaming updates alongside missing state. When an update alters a story's author, the base table emits two corresponding deltas into the dataflow graph: a negative delta removing the story under the old author ID, and a positive delta inserting the story under the new author ID.

```mermaid flowchart TD accTitle: The Incongruent Join Dilemma on Missing State accDescr: Flowchart demonstrating the dilemma when a positive delta misses in the users table during an author update.

Delta["Author Update for Story 7\n- (Story 7, Author 42)\n+ (Story 7, Author 43)"] JoinOp["Incongruent Join Operator"]

LookupOld["Lookup Author 42: Hits ('Lena')"] LookupNew["Lookup Author 43: Misses in Users state!"]

Delta --> JoinOp JoinOp --> LookupOld JoinOp --> LookupNew

LookupNew --> BadOptions{"Available Fallback Actions"} BadOptions -->|"Drop positive, send negative"| EmptyState["Materialized view has no rows for Story 7"] BadOptions -->|"Drop entire update"| StaleState["Materialized view permanently displays old author Lena"] BadOptions -->|"Block dataflow on upquery"| Stall["Dataflow pipeline stalls behind expensive view queries"] ```

When these two deltas reach the join operator: - The join operator resolves author `42` in the `users` table, successfully matching `Lena` and preparing the negative delta for output. - The join operator attempts to look up author `43` in the `users` table to complete the positive delta, but the lookup misses.

A cache miss can happen if base tables manage memory by keeping cold rows on disk, or more commonly, if `users` is not a raw base table at all, but rather an upstream view with partial state and its own active evictions. Regardless of the underlying cause, the join operator is trapped with incomplete data: - **Forwarding only the negative delta:** If the join emits the negative delta and drops the unresolvable positive delta, the downstream materialized view purges `story 7` entirely. Any subsequent read for `story 7` returns no rows, falsely indicating the story no longer exists. - **Dropping the update entirely:** If the join silently discards both deltas, the materialized view retains the old author `Lena`. Any subsequent lookup sees out-of-date information, rendering the cached entry permanently stale. - **Pausing the pipeline for an on-demand upquery:** The obvious instinct is to trigger an immediate upquery from the join to fetch user `43` before processing the delta. However, blocking the join operator stalls the entire streaming pipeline while waiting for an upstream view query to complete, degrading write performance across the whole database.

> “We cannot forward just the negative, and just sort of discard the positive, because if we did, the downstream materialized view would now have no rows for story 7. And any subsequent query for story 7 would get no results, which is obviously not correct.” — Jon Gjengset

[32:50](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1970s) Breaking Deadlocks with Downstream Evictions

```mermaid flowchart TD accTitle: Downstream Eviction Strategy accDescr: Diagram showing how an incongruent join handles missing state by pushing an eviction downstream instead of issuing a blocking upquery.

subgraph Dataflow ["Dataflow Engine"] Join["Incongruent Join Operator"] MatView["Downstream Materialized View"] end

Update["Incoming Update<br/>(e.g., Story 7)"] --> Join Join -- "Cannot resolve update immediately<br/>(Emits Eviction)" --> MatView MatView -- "Evicts Record 7" --> State["State Marked Missing"] ClientReq["Later Read Request (Story 7)"] --> MatView MatView -. "Triggers normal Upquery".-> Join ```

Issuing an upquery directly from an active join operator creates severe operational risks. If a join sits beneath a massive dataflow graph, resolving an upquery upward can take a very long time, during which the join is completely blocked from processing further updates. Gjengset explains that the situation is actually far worse: in certain configurations, circular dependencies cause absolute deadlocks. “Where the join can't process more updates until the upquery finishes, but the upquery cannot finish until the join processes more updates. And now we're stuck.” Processing subsequent updates out of order is impossible because later updates may depend directly on the update currently being stalled.

Partial state itself provides the elegant escape hatch from this conundrum: evictions. Rather than blocking the dataflow to resolve unknown fields (such as identifying the author for an updated story), the join emits an eviction downstream. By evicting story 7 from the downstream materialized view, the database simply forgets the state. When an application subsequently issues a read query for story 7, the missing entry triggers the standard upquery flow on demand, which is already designed to operate safely without deadlocking. Furthermore, Noria statically detects incongruent joins and selectively issues evictions only when strictly necessary, rather than penalizing every join in the system.

[34:26](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2066s) Evaluation Setup: Benchmarking Against Lobste.rs

To prove whether partial state provides real-world value without crushing performance under internal mechanism overhead, Gjengset evaluated Noria against Lobste.rs, an open-source, Hacker News–style news aggregator. Lobste.rs was selected for two primary reasons: its codebase is open-source (making all queries issued across distinct web pages transparent), and its traffic statistics are publicly available. These statistics capture aggregate requests per second, page distributions, active users, and story popularity.

Using these statistics, Gjengset built a workload generator that generates synthetic Lobste.rs traffic, allowing artificial load modulation to determine when systems reach their breaking point. The generator includes a pluggable backend compatible with both MySQL and Noria, and crucially bypasses the Ruby on Rails application tier. This isolation ensures the benchmarks evaluate pure database backend performance rather than the overhead of front-end scripting runtimes.

- **Workload:** Synthetic Lobste.rs interactions (story submissions, upvotes, comments, front-page views). - **Target environment:** 16-core Amazon EC2 instances with 128 GB of RAM. - **Metric evaluated:** Maximum sustainable throughput in pages per second before core saturation or latency spikes.

[36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) Throughput Benchmarks: MySQL vs. Stateful vs. Partial Noria

```mermaid flowchart LR accTitle: Throughput Comparison Across Configurations accDescr: Bar-style chart comparison of system throughput across MySQL, Noria without partial state, and Noria with partial state.

subgraph Throughput ["Throughput (Pages / Second)"] direction TB M["MySQL (Denormalized): ~400"] NW["Noria without Partial State: ~4,500 (OOM Bottleneck)"] NP["Noria with Partial State: ~7,500 (18x MySQL)"] end

M -->|11.25x| NW NW -->|1.67x| NP ```

On a 16-core EC2 instance, MySQL topped out at roughly 400 pages per second before saturating all CPU cores and suffering latency spikes. Gjengset emphasized that this baseline reflects an already heavily optimized, denormalized schema where the Lobste.rs developers had deliberately made story "hotness" (vote score) an explicit column on the stories table to dodge real-time joins and aggregations. “If you don't include this kind of manual denormalization the throughput for MySQL… it can't even keep up with a single page request per second.”

Standard Noria (without partial state) improved performance by an order of magnitude, sustaining roughly 4,500 pages per second due to precomputed materialized views converting complex joins into simple key-value lookups. However, standard Noria hit a hard memory wall: it exhausted the entire 128 GB of RAM. Because memory usage increases continuously over time in fully stateful dataflow, it could not sustain this load over longer runs, despite internal optimizations to materialize only actively queried views.

Noria equipped with partial state achieved roughly 7,500 pages per second—a 67% improvement over fully stateful Noria and an 18x leap over MySQL. Rather than hitting a CPU or memory bottleneck, partial Noria’s performance limit was dictated by an update-heavy dataflow branch processing upqueries. In memory consumption tests run just below standard Noria's failure threshold: - Noria without partial state consumed over 100 GB of memory. - Noria with partial state consumed approximately one-third of that footprint (~34 GB).

[39:13](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2353s) Evaluating Against an Idealized Redis Cache

Anticipating the pragmatic objection that production architectures deploy dedicated key-value caches rather than plain relational databases, Gjengset tested Noria against Redis. Because real-world cache implementations vary wildly, he constructed an idealized, best-case caching benchmark: a single query (stories combined with vote counts), almost all reads, zero misses, zero evictions, and pure single-key lookups.

Under this idealized workload, single-threaded Redis processed slightly below 1,000,000 requests per second on a single core. To construct a fair hardware comparison against multi-core Noria, Gjengset multiplied this figure by 16 to represent a theoretical upper bound of an optimally scaled, multi-core Redis deployment. When Noria ran the identical workload, it scaled reads across available cores and performed within a factor of two of this theoretical Redis ceiling. Gjengset highlighted that Noria achieves this competitive performance while eliminating manual application caching entirely: “Noria provides SQL, automatic maintenance of this cache, and it doesn't have these requirements of everything has to be implemented in the application logic.”

[41:18](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2478s) Future Work and Acknowledgments

Reflecting on the limitations of the current implementation, Gjengset outlined key directions for future research: - **Expanded query primitives:** Noria currently lacks native support for range queries, cursors, and time-windowed streaming operators. - **Upstream database integration:** Adapting Noria to sit directly in front of external sources of truth (such as an existing PostgreSQL or MySQL instance) rather than acting as the primary storage layer. - **End-to-end reactive views:** Extending dataflow streams beyond server-side materialized views directly into client-side devices, enabling live UI updates via reactive streams. - **Fault tolerance via partial state:** Leveraging partial materialization for node recovery; if a dataflow node crashes, its lost records could simply be marked as missing and restored lazily via upqueries.

Concluding his presentation, Gjengset expressed gratitude to his academic committee and collaborators. He thanked his advisor Robert Morris and Frans Kaashoek for their relentless pressure to sharpen the dissertation's focus, noting: “I think initially I had these sort of hazy ideas for something that might be cool, and I think the two of them have really helped hone the story, hone the argument, for why this is useful and what the work should focus on.” He also credited post-doc Malte Schwarzkopf, emphasizing that without Malte's contributions, Noria would lack SQL support and query optimization and remain a bare dataflow runtime.

[44:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2647s) Committee, PDOS Group, and Personal Acknowledgments

Jon Gjengset continues his acknowledgments by recognizing the members of his dissertation committee, highlighting Sam Madden's deep database expertise. Gjengset notes how valuable that perspective was to draw upon, joking that database knowledge is “something that he has a lot more of us than us mere systems people.” He also expresses his gratitude to his colleagues in the Parallel and Distributed Operating Systems (PDOS) group at MIT. He credits the lab's collaborative culture, boundless curiosity, technical insight, and ongoing support with shaping him as a scholar, remarking: “And I don't think I would be here without having them surround me throughout the years.”

Turning to his personal life, Gjengset thanks his parents and step-parents for championing his interests from an early age, regardless of how esoteric or nerdy those pursuits appeared. He reflects warmly that their constant encouragement steadily nudged him along until he reached this milestone, giving what he readily acknowledges is a very geeky presentation that he hopes makes them proud. Finally, he shares an emotional thank-you to his girlfriend, Talia, praising her patience and understanding throughout the grueling phases of graduate school. As Gjengset admits: “I am amazed that she's tolerated me just locking myself in my room for hours on end working on this work, on the evaluation, on the thesis, on this presentation.” He concludes his acknowledgments by expressing his love and deep appreciation for her.

[45:24](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2724s) Summary and Conclusion: Materialized Views as Transparent Caches

Gjengset brings the defense to a close by synthesizing the primary contributions of his thesis: enabling dataflow-based materialized views to function effectively as dynamic query caches. Traditional materialized views require holding full state across all materializations and intermediate nodes, making them prohibitively memory-intensive and inflexible for evolving workloads. By introducing partially stateful materialization, the system allows arbitrary state entries to be absent or evicted, resolving cache misses on demand through backward-propagating upqueries that traverse the dataflow graph.

This architecture enables Noria to provide transparent, automated caching for complex SQL queries directly within the database infrastructure. Application developers gain the high throughput and low read latency of specialized key-value caches without having to construct, maintain, or debug error-prone, ad hoc application-level caching logic. Gjengset summarizes the central value proposition in his concluding statement: “The resulting system provides automated caching for SQL queries, and reduces the need for complex, ad hoc caching logic.” He finishes by thanking the virtual audience and inviting questions from the committee and attendees.

```mermaid flowchart TD accTitle: Summary of Partially Materialized Views Architecture accDescr: Diagram showing how partial state and upqueries allow materialized views to act as an automated database cache. subgraph Client Layer Q["Read Query"] end subgraph Noria Materialized View Engine MV{"Partial State<br/>Materialized View"} UQ["Upquery<br/>(Demand-Driven)"] DF["Dataflow Operators<br/>(Partially Stateful)"] end subgraph Storage Layer Base["Base Tables"] end

Q --> MV MV -->|"Hit: Cached Result"| Q MV -->|"Miss: Missing Entry"| UQ UQ --> DF DF --> Base Base -->|"Forward Maintenance"| DF DF -->|"Populate View"| MV ```

- **Committee Perspective**: Sam Madden provided essential database domain knowledge to complement the research group's systems-focused approach. - **PDOS Culture**: The MIT Parallel and Distributed Operating Systems group's community and intellectual curiosity served as the foundation for the doctoral work. - **Core Takeaway**: Allowing missing state and filling it dynamically via upqueries lets materialized views behave like adaptive caches, reducing memory footprints and eliminating manual cache management in read-heavy applications.

## Notable quotes > [14:08](https://www.youtube.com/watch?v=GctxvSPIfr8&t=848s) The observation here is that the chances are most entries in any given view are not accessed. — Jon Gjengset

## Mentioned Jon Gjengset, Robert Morris, Frans Kaashoek, Sam Madden, Malte Schwarzkopf, Talia, MIT, PDOS, Noria, MySQL, Redis, PostgreSQL, Lobste.rs, Amazon EC2, Ruby on Rails

## Video description This is my PhD dissertation presentation, which I gave at MIT (virtually) on October 22nd, 2020. It was immediately followed by my thesis defense, which I passed subject to the typical bits and pieces of revisions the committee wanted to see.

The person who introduces me in the video is Robert Morris, my thesis advisor. The Q&A has been cut out, as I want to edit it a bit and mix in questions from the public presentation I gave on YouTube the day before. I will link the Q&A video here once it is out. You can find the slides at https://jon.thesquareplanet.com/slides/thesis.pdf and at https://docs.google.com/presentation/d/1w2PlmqUIeue8VcNhBqOC0V3GTKQs9zBccrhd9tfAang/edit?usp=sharing. The thesis is available at https://jon.thesquareplanet.com/papers/phd-thesis.pdf.

What follows is the thesis abstract:

This thesis proposes a practical database system that lowers latency and increases supported load for read-heavy applications by using incrementally-maintained materialized views to cache query results. As opposed to state-of-the-art materialized view systems, the presented system builds the cache on demand, and evicts cache entries in response to a shifting workload.

The enabling technique the thesis introduces is partially stateful materialization, which allows entries in materialized views to be missing. The thesis proposes upqueries as a mechanism to fill such missing state on demand using dataflow, and implements them in the materialized view system Noria. The thesis then discusses additional mechanisms needed to establish eventual consistency for partially stateful dataflow.

Noria with partial materialization saves application developers from implementing their own ad hoc caching mechanisms to speed up their database accesses. Instead, the caching is built into the database, and is transparent to the application. Experimental results suggest that the presented system increases supported application load by up to 20x over MySQL and performs similarly to an optimized key-value store cache. Partial state also reduces memory use by up to 2/3 compared to traditional materialized views.

[Source](https://www.youtube.com/watch?v=GctxvSPIfr8)

中文简报

麻省理工学院Noria将缓存内存削减三分之二，吞吐量达MySQL的18倍 通过允许物化视图保存部分状态并按需解析缺失记录，既消除了应用层的临时缓存，又避免了传统流处理器常见的内存耗尽问题。 在读密集型Web应用中，传统关系型数据库因重复执行相同查询而浪费大量计算资源，迫使工程师构建脆弱的临时缓存层。Jon Gjengset在Noria中引入了部分状态物化架构，该架构通过主动允许状态缺失或被逐出，将物化视图作为动态缓存使用。当发生缓存未命中时，反向传播的“上游查询”（upqueries）会通过数据流路径按需重构所需数据；而对于不一致连接等棘手边界情况，则通过下游逐出解决，避免了阻塞数据管道。基于Lobste.rs工作负载的基准测试表明，部分状态物化相比MySQL实现了高达18倍的吞吐量提升，比全状态视图减少了三分之二的内存占用，并在保留SQL接口的同时达到了理想化Redis缓存两倍以内的性能。 Jon Gjengset在数据流物化视图中引入了部分状态机制，允许条目缺失并按需重构，从而起到自动化、透明的数据库缓存作用。 (0:00) Noria通过反向传播的“上游查询”解析缺失的视图状态，并引发正常的正向增量响应，消除了冗余的反向执行查询引擎。 (15:52) 上游状态缺失导致的不一致连接死锁和陈旧性风险，通过向下游推送逐出操作得以安全解决，而无需因同步查询而停滞管道。 (32:50) 在针对合成Lobste.rs基准测试的评估中，部分状态Noria达到了约7,500页/秒的处理能力——比MySQL吞吐量提升了18倍，比全状态Noria提升了67%，同时内存使用量减少了约三分之二。 (36:01)

Reading summary

Jon Gjengset argues that read-heavy web applications suffer from an architectural mismatch between expensive relational queries and brittle application-level caching layers. To solve this, his doctoral research introduces partial state to dataflow-based materialized views in Noria, allowing the database to dynamically evict cold entries and reconstruct missing records on demand via recursive upqueries. The Bottleneck of Manual Application Caching (2:06) Traditional relational databases execute simple writes directly against tables, but read queries often trigger computationally expensive joins and aggregations. In read-heavy web workloads, identical queries execute repeatedly, placing heavy compute strain on the database engine. To reduce latency, engineering teams commonly deploy external in-memory caches or manually denormalize relational schemas. However, Gjengset points out that delegating cache management to application logic introduces immense operational complexity. Developers must write bespoke code to invalidate or refresh stale cache entries across all mutation paths. High concurrency also creates severe failure modes like thundering herds, where cache misses cause concurrent requests to swarm the primary database with identical queries. Traditional materialized views offer automated incremental maintenance via delta records, but they historically target analytical systems by materializing complete relations indefinitely, lacking mechanisms for dynamic eviction. Partial State, Upqueries, and Delta Pruning (14:08) Because real-world web traffic is heavily skewed toward a small set of popular records, Gjengset argues that materialized views must 'learn to forget.' Noria introduces partial state, explicitly permitting views and intermediate operators to mark cold or unread records as missing. Parameterized view definitions (such as queries containing `WHERE id = ?`) tie partial indexing directly to runtime query keys. When an application queries an evicted or unmaterialized key, the view initiates a backward 'upquery' through the dataflow graph. Upqueries traverse upstream until encountering an operator holding sufficient state to reconstruct the key. The resolving operator emits a standard delta message downstream over normal forward dataflow edges, avoiding dedicated backward execution pipelines. Furthermore, intermediate joins prune compute: if an update delta arrives for an entry missing from sibling operator caches, Noria drops the update immediately rather than expending cycles computing changes for unread downstream views. Concurrency Hazards and Incongruent Join Deadlocks (28:01) Maintaining partial state introduces concurrency hazards, particularly the requirement to ensure streaming updates apply exactly once. Concurrent upqueries (fetching historical snapshots) and forward dataflow updates (applying streaming mutations) can collide on identical keys, risking duplicate records or permanent staleness if updates are misidentified as missing and discarded. These risks intensify in 'incongruent joins,' where the runtime query key differs from the internal join key—such as indexing a view by `story_id` while joining tables on `author_id`. If an update modifies a story's author, the join operator requires the new author's attributes. If that user entry is missing from memory, triggering a synchronous upstream upquery can block the streaming pipeline, causing circular dataflow dependencies and deadlocks. Noria circumvents deadlocks by having incongruent joins emit downstream evictions instead of blocking. Evicting the affected story clears the downstream view, allowing subsequent reads to backfill state safely through the standard upquery mechanism. Empirical Benchmarks on Lobste.rs and Redis (34:26) Gjengset evaluated Noria against a synthetic workload modeled on Lobste.rs on 16-core EC2 instances with 128 GB of RAM. A denormalized MySQL baseline peaked at roughly 400 pages per second before saturating CPU cores. Fully stateful Noria sustained approximately 4,500 pages per second by converting joins into key-value view reads, but eventually exhausted the 128 GB memory limit due to unbounded view growth. In contrast, Noria with partial state reached roughly 7,500 pages per second—an 18x speedup over MySQL and a 67% gain over stateful Noria—while consuming approximately 34 GB of memory, one-third of stateful Noria's footprint. Tested against an idealized, single-key cache scenario with zero misses, Noria achieved throughput within a factor of two of a multi-core scaled Redis configuration, delivering comparable read performance while transparently handling cache maintenance through SQL. While Noria demonstrates that partially stateful views can automate caching directly inside the database, Gjengset notes that the prototype lacks native support for range queries, cursors, and time windows. He highlights future research paths including integrating Noria in front of existing external relational engines, streaming reactive updates to client interfaces, and using partial state to accelerate node recovery after crashes.

精炼阅读摘要

Jon Gjengset 在其麻省理工学院（MIT）博士论文答辩中提出，通过在基于数据流的物化视图中引入“部分状态”（Partial State）与按需向上查询机制，可以让数据库内部自动实现动态缓存，从而在无需应用层编写复杂缓存逻辑的前提下大幅降低读延迟与内存占用。 读多写少架构瓶颈与手动缓存困境 (2:06) 现代 Web 应用普遍呈现“读多写少”特征，一次写操作通常仅修改单张数据表，而读查询却往往需要跨多个关系操作符进行昂贵的聚合与连接计算。由于系统反复执行相同或相近的查询，传统关系数据库引擎消耗了大量算力来重复计算已知结果。若采用未经反范式化设计的模式，处理高并发读操作时性能会迅速恶化。 应用层缓存的维护复杂度与失效风险 (4:02) 工程实践中常使用 Redis 等外部内存键值缓存或通过表反范式化来缓解读压力，但 Gjengset 指出将缓存管理委托给应用代码会带来巨大的运维复杂性。底层数据一旦变化，应用必须精准失效或刷新缓存条目；当高并发请求遭遇缓存未命中时，还极易引发惊群效应（thundering herd）并拖垮底层数据库。开发人员不得不耗费精力处理复杂的并发控制、驱逐策略与重填逻辑，因而亟须一种直接内嵌于数据库内部的自动化缓存方案。 数据流物化视图与部分状态核心机制 (8:25) 物化视图能将查询结果持久化以加速后续读取，但在全状态模型下，系统必须为所有键维护完整结果，造成巨大的内存浪费。Gjengset 依托其构建的高性能流式数据库系统 Noria，将“部分状态”理念引入数据流图：物化视图与其上游操作符显式允许特定条目处于“缺失”状态。当读请求命中缺失条目时，视图触发向上查询（Upquery）沿数据流图向后递归追溯历史增量；当遇到具备足够状态的祖先节点时，再沿常规正向数据流管线以增量消息（Delta）形式补全数据。同时，系统允许安全驱逐冷数据，并在中间连接操作符检测到缺失状态时直接丢弃针对冷数据的增量更新，大幅节省了计算资源。 不全等连接并发挑战与下游驱逐破局 (25:48) 支持部分状态的最大挑战在于保证底层基础表的突变在视图中“恰好生效一次”，避免实时增量更新与向上查询发生竞态导致数据永久陈旧。在查询键与连接键不一致的“不全等连接”（Incongruent Join）场景中，若更新抵达时某侧关联状态缺失，阻断流水线发起向上查询容易引发死锁或拖慢整体写入吞吐。Noria 采取的创新解法是转而向下游视图发送针对该键的驱逐（Eviction）信号，直接遗忘该记录；当客户端后续再次请求该数据时，系统再通过成熟的向上查询路径按需回填，在保证最终一致性的同时规避了流水线停滞。 实证基准测试与系统性能表现 (34:26) 在基于开源新闻聚合网站 Lobste.rs 真实流量模式的测试中，16 核 EC2 实例上的反范式化 MySQL 上限约为 400 页面/秒即达到 CPU 饱和；完全状态版的 Noria 虽将吞吐量提升至约 4,500 页面/秒，却迅速耗尽了 128 GB 内存。搭载部分状态机制的 Noria 达到了约 7,500 页面/秒的吞吐量，比 MySQL 高出 18 倍，且在相同负载下内存占用仅为完全状态版的约三分之一（约 34 GB 对比超过 100 GB）。在针对纯读且无未命中的理想化缓存基准测试中，Noria 的吞吐表现达到了单核 Redis 理论 16 核线性扩展上限的二分之一以内，同时完整保留了标准 SQL 接口。 Gjengset 总结认为，部分状态机制成功使物化视图兼具动态缓存的高吞吐、低延迟与数据库声明式视图的易用性。该系统当前仍存在未原生支持范围查询、游标和时间滑动窗口等功能局限；未来研究方向包括将 Noria 作为透明外部缓存挂载于现有 PostgreSQL 或 MySQL 前端、实现面向客户端的端到端响应式流，以及利用缺失状态与向上查询进行节点崩溃后的懒惰容错恢复。

Detailed notes — zh

## Background 该视频由 Jon Gjengset 于 2020 年 10 月 23 日发布在 YouTube 平台上。视频记录了作者在麻省理工学院（MIT）进行的博士学位论文答辩，其论文主题为《基于数据流的物化视图中的部分状态》（Partial State in Dataflow-Based Materialized Views），重点探讨如何通过部分状态化与动态按需缓存机制来提升读密集型数据库的性能并降低内存开销。 ## TL;DR 面对现代 Web 应用中读多写少、传统数据库反复执行昂贵查询以及应用层手写缓存难以维护一致性的痛点，Jon Gjengset 提出了基于数据流的物化视图系统 Noria。该系统打破了传统物化视图必须全量物化的限制，创新地引入了“部分状态”（Partial State）与“向上查询”（Upqueries）机制，允许冷数据条目缺失或被驱逐，并在查询未命中时沿数据流按需动态回填。在真实开源社区 Lobste.rs 的负载测试中，带部分状态的 Noria 展现出超过 MySQL 18 倍的页面吞吐量，相比全量物化减少了多达三分之二的内存开销，并展现出逼近理想化 Redis 缓存的极高读性能。 ## Atmosphere & style 整个答辩呈现出严谨扎实却又生动风趣的顶级学术系统研究氛围。从导师 Robert Morris 充满温情与高度赞赏的开场致辞，到 Jon Gjengset 抽丝剥茧、循序渐进地拆解核心系统构架与并发危险，演讲兼具工程极客的务实与学术论证的严密。尾声阶段，讲者真挚地致谢导师、实验室伙伴、家人及伴侣，使整场高强度的技术汇报在理性严密的技术自豪感与温暖动人的情感共鸣中圆满落幕。 ## Bulletin - [14:08](https://www.youtube.com/watch?v=GctxvSPIfr8&t=848s) Jon Gjengset 提出基于数据流的部分状态物化视图系统 Noria，允许物化视图中存在缺失状态并通过向上查询（Upquery）按需回填，将缓存能力透明下沉至数据库内部。 - [03:50](https://www.youtube.com/watch?v=GctxvSPIfr8&t=230s) 针对不协调连接（Incongruent Join）可能引发的死锁与数据流长时间阻塞，Noria 采用主动驱逐（Eviction）机制剔除下游物化状态，将补齐操作推迟到后续读取时按需执行。 - [36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) 在真实社区网站 Lobste.rs 的负载基准评测中，引入部分状态的 Noria 吞吐量达到 MySQL 的 18 倍以上，并相较全量物化视图节省了多达三分之二的物理内存。 - [39:13](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2353s) 在高度理想化的只读点查基准测试中，Noria 在提供通用 SQL 接口与全自动增量物化的前提下，吞吐性能逼近多核线性扩展 Redis 理论上限的二分之一以内。 ## Key takeaways - [01:41](https://www.youtube.com/watch?v=GctxvSPIfr8&t=101s) 读密集型 Web 应用在传统架构中需要反复穿透繁重的 Join 与聚合算子，导致昂贵的读取操作占据大量吞吐并产生大量冗余计算。 - [03:58](https://www.youtube.com/watch?v=GctxvSPIfr8&t=238s) 传统应用层缓存（如 Redis/Memcached）在工程上面临缓存失效、缓存击穿、并发回写编排及内存驱逐策略等复杂的双写一致性痛点。 - [06:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=408s) Noria 采用基于数据流（Dataflow）的推模式架构，将底层数据变更转化为带正负号的增量消息（Deltas）向下游关系算子管道持续传播。 - [14:08](https://www.youtube.com/watch?v=GctxvSPIfr8&t=848s) 部分状态（Partial State）的核心思想在于让系统“学会遗忘”，避免为无人读取的冷数据持续消耗宝贵的内存与增量维护算力。 - [15:52](https://www.youtube.com/watch?v=GctxvSPIfr8&t=952s) Noria 将参数化查询键直接融入视图定义中，当遭遇缺失状态时通过向上查询（Upquery）递归向祖先算子索取快照，并复用既有前向流通道填补空缺。 - [20:25](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1225s) 当算子检测到兄弟节点中对应键的状态处于缺失状态时，能够安全地直接丢弃（Discard）下行更新，避免无意义的级联计算。 - [22:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1327s) 传统物化视图偏向于低频分析查询的写入维护且缺乏细粒度淘汰，而流处理系统偏向写性能与强一致性，均无法很好满足 Web 端低延迟动态点查的需求。 - [25:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1548s) 引入部分状态后，系统面临并发向上查询与流式更新之间的顺序错乱、重复计算，以及提前丢弃可能引发下游永久陈旧（Permanently Stale）等一致性挑战。 - [03:50](https://www.youtube.com/watch?v=GctxvSPIfr8&t=230s) 在查询键与连接键不一致的不协调连接（Incongruent Join）场景中，直接挂起流管道等待向上查询会引发死锁与全线阻塞，Noria 采用主动发送驱逐信号的策略予以化解。 - [36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) 在 Lobste.rs 真实负载下，MySQL 吞吐受限于约 400 pages/sec，全量物化 Noria 遭遇 128GB 内存耗尽瓶颈，而部分状态 Noria 达到了 7500+ pages/sec 且内存仅占原先的三分之一。 - [41:18](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2478s) Noria 的未来演进方向包括支持范围查询与滑动窗口算子、无缝挂接现有主数据库、端到端响应式推送，以及利用部分状态特性实现运行时的透明自愈容错。 - [45:24](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2724s) 该论文的核心学术贡献在于证明了部分有状态物化视图能够作为透明的内置数据库缓存，彻底解耦业务开发者手写 ad-hoc 缓存逻辑的负担。 ## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=GctxvSPIfr8&t=0s) 导师致辞与答辩开场 博士生导师 Robert Morris 教授简要致辞，为 Jon Gjengset 的博士论文答辩拉开序幕。Robert Morris 回顾了 Jon 在读博期间的研究历程与对学术社群的奉献，评价道：“在学术研究中，Jon 始终在探索一个非常出色的构想，即高并发网站应当如何管理它们的数据；见证他提出这一构想并凭借高超的技术将其实现，令人印象深刻。”他还高度赞扬了 Jon 在教学和社区方面的热情与付出：从担任助教时展现出的无穷耐心，到组织研究生学术活动，再到在网络上直播系统编程教程。Robert Morris 感慨道：“无论 Jon 未来着手做什么，他都注定会大放异彩并深受重视；假设答辩委员会今天同意让他毕业，MIT 的许多人都会非常想念他，我个人也绝对会非常想念他。” 随后 Jon Gjengset 接过主持权，向现场及线上观众致谢，并正式开始题为《基于数据流的物化视图中的部分状态》（Partial State in Dataflow-Based Materialized Views）的博士学位论文答辩。Jon 幽默地表示，自己今天的目标是在大约 45 分钟内浓缩并总结过去六年的研究工作，至少要让大家彻底明白论文标题中每一个词的含义，以及为什么这项工作值得耗费六年心血。他特别提到，这项研究是在导师 Robert Morris 以及委员会成员 Frans Kaashoek、Sam Madden 和 Malte Schwarzkopf 的悉心指导下完成的，正是他们共同确保了这项研究的价值与扎实度。 --- ### [01:41](https://www.youtube.com/watch?v=GctxvSPIfr8&t=101s) 数据库基础与读密集型应用的瓶颈 Jon 开门见山地抛出一个根本性问题：“我们为什么在这里？”他澄清这并不是哲学层面上探讨人生的意义，而是解释自己为何要向大家做这场报告。Jon 直言不讳地指出：“我站在这里，是因为我想要让数据库变得更好。” 为了说明传统数据库的痛点，Jon 带着听众回顾了基础的数据库原理（Database 101）。在一个典型的应用场景中，通常存在若干基础数据表，比如存储文章内容的 `stories` 表和记录用户点赞的 `votes` 表。应用端主要通过两类操作与数据库交互： 1. **写操作（Writes / Updates）**：包括 SQL 中的 `INSERT`、`UPDATE` 和 `DELETE`，用于直接修改底层数据表（例如向 `votes` 表中插入一条新的点赞记录）。Jon 明确指出，在后续演讲中他会将写入统称为“写”或“更新”，而不将其归为查询。 2. **读操作（Queries / Reads）**：指 SQL 中的 `SELECT` 操作。应用通常需要将不同表的数据进行聚合（Aggregate）、筛选或跨表关联（Join），以便生成业务所需的数据视图。 在图示架构中，读取操作涉及的计算算子数量远多于写入操作。这意味着执行一次读取往往比执行一次写入要付出大得多的计算代价。然而在现实世界中，绝大多数应用（尤其是 Web 应用程序）都是“读密集型”（Read-heavy）的，其读取流量往往是写入流量的数个数量级。让成本最昂贵的操作占据系统吞吐的大头，必然导致严重的性能瓶颈，特别是在成千上万个请求反复执行相同或极度相似的读取查询时，数据库底层在无休止地做着重复的冗余计算。 ```mermaid flowchart TD accTitle: 传统数据库的读写不对称性 accDescr: 展示写操作直接进入基础表，而读操作需要穿过昂贵的聚合与连接算子。 subgraph Operations["应用端操作"] W["写操作 (INSERT/UPDATE/DELETE)"] R["读操作 (SELECT Queries)"] end subgraph QueryExecution["查询执行层 (计算繁重)"] J["连接算子 (Join)"] A["聚合算子 (Aggregation)"] end subgraph Storage["底层存储"] T1[("stories 表")] T2[("votes 表")] end W -->|"直接写入"| T2 T1 --> J T2 --> J J --> A A -->|"返回复杂数据"| R ``` --- ### [03:58](https://www.youtube.com/watch?v=GctxvSPIfr8&t=238s) 传统缓存方案及其在工程落地中的困境 面对读密集型应用的性能挑战，工业界的经典做法是在数据库前方引入缓存层（例如基于 Key-Value 的存储系统），或者采用反规范化（Denormalization，例如直接在 `stories` 表中维护冗余的计数字段）。Jon 承认缓存非常优秀，如果查询命中缓存，便能以极低的延迟立即返回；仅当缓存未命中时，才去向后端数据库发起昂贵的 SQL 查询。 然而，Jon 强调：“缓存固然很棒，但不幸的是，要把它用正确也是极其困难的。”应用开发者为了实现正确的缓存逻辑，必须在业务层背负巨大的复杂度： - **缓存失效与一致性（Invalidation & Staleness）**：随着底层数据表被写入（例如用户投出了新的一票），缓存中的文章票数即刻失效。应用中执行写入的代码路径必须准确追踪哪些缓存需要被作废，或者显式地去更新对应缓存。 - **缓存击穿与写入编排（Thundering Herd & Orchestration）**：如果某条热门文章未被缓存，而瞬间有 10 万个并发请求涌入，是否允许这 10 万个请求同时轰击后端数据库去执行同一条复杂 SQL？这种流量雪崩极具破坏性。同时，当查询返回后，究竟由哪一个并发线程负责将数据回写到缓存中，其并发协调非常棘手。 - **缓存逐出策略（Eviction）**：服务器的物理内存是有限的，随着数据不断累加，必须有一种机制将陈旧或冷门的数据从缓存中清除。究竟应该由谁来触发逐出、何时逐出、采用何种策略逐出，都给应用层逻辑带来了沉重的工程负担。 Jon 指出，这些错综复杂的缓存边缘逻辑原本不应该由应用开发者来苦苦维系。他的博士研究核心正是针对这一难题，探索“自动化数据库缓存”（Automatic Database Caching）机制——让缓存的填充、失效与逐出逻辑彻底下沉到数据库内部，由数据库透明地对外提供服务，使应用代码彻底解耦。 --- ### [06:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=408s) 解构核心概念：物化视图与数据流架构 为了系统性地阐述解决方案，Jon 决定沿着论文标题《基于数据流的物化视图中的部分状态》（*Partial State in Dataflow-Based Materialized Views*）从右向左逐词拆解。 首先是 **物化视图（Materialized Views）**。Jon 介绍说，物化视图是数据库学术界早在 20 世纪 80 年代初就提出的概念。它的本质非常质朴：“运行查询，然后把结果记住。”这听起来与缓存如出一辙。而物化视图的核心挑战也与缓存一致：如何进行“物化视图维护”（Materialized View Maintenance）。如果基础表数据更新，系统显然不能每次都从头全量重新执行整个查询。例如，一篇文章已经积累了 10 万票，当第 100,001 票到来时，理想的系统应当直接在原有的 100,000 上累加 1，而不是重新全表扫描统计这 100,001 票。这种按需计算增量的机制被称为“增量维护”（Incremental Maintenance）。此外，维护还面临着是在写入时主动计算（Maintain-on-write），还是在后续读取时惰性按需计算（Lazy / On-demand）的权衡。 标题中的下一个关键词是 **基于数据流（Dataflow-Based）**。数据流是一种系统架构。在本研究的语境下，数据流的核心思想是“让数据走向计算”（Data move to compute），即采用推模式（Push-based computation）。数据表的变动会主动沿着由关系代数算子（如 Join、Aggregation、Filter 等）构成的有向无环图向下游传播。 Jon 详细说明了数据流图的关键元素： - **依赖边（Edges）**：每条边代表数据依赖关系，例如 Join 算子依赖于其所有输入表，聚合算子依赖于它所聚合的上游数据源。 - **增量消息（Deltas）**：在数据流边缘上传播的消息被称为增量。一个 Delta 结构包含完整的行数据，并带有一个“符号”（Sign）——正号（`+`）或负号（`-`）。正号增量表示新增了一条记录（类似于向结果集中追加一行），负号增量表示对之前发出记录的撤销（类似于从结果集中删除一行）。 Jon 的研究正是依托这一数据流模型，在自己主导研发的最终一致性物化视图系统 **Noria** 中展开。 ```mermaid flowchart LR accTitle: 数据流增量消息传播机制 accDescr: 展示包含正负符号的 Delta 增量数据如何在计算算子间流动。 subgraph Tables["底层数据源"] T["votes 表"] end subgraph DataflowEdge["数据流依赖边"] D1["Delta: (+, vote_id=42, story_id=7)"] D2["Delta: (-, vote_id=42, story_id=7)"] end subgraph Operators["计算节点"] OP["关系算子 (如 Aggregation/Join)"] end T -->|"Push 写入"| D1 T -->|"Push 撤销"| D2 D1 --> OP D2 --> OP ``` --- ### [10:28](https://www.youtube.com/watch?v=GctxvSPIfr8&t=628s) 案例分析：Noria 中物化视图的构建示例 为了让抽象的数据流概念变得具体直观，Jon 举了一个典型的 SQL 视图构建示例。在示例中，系统需要构建一个名为 `StoryWithVC`（VC 即 Vote Count，点赞数）的物化视图： ```sql CREATE MATERIALIZED VIEW StoryWithVC AS SELECT stories.id, stories.title, COUNT(votes.id) AS vote_count FROM stories JOIN votes ON stories.id = votes.story_id GROUP BY stories.id; ``` 在 Noria 系统中，针对该查询会自动编译并生成对应的数据流图。底层的 `stories` 表和 `votes` 表位于数据流的顶端输入侧，当有新数据写入或更新时，增量数据会被推入流图中，依次经过 Join 算子关联对应文章信息、流经 Aggregation 算子进行增量票数统计，最终将保持最新状态的完整结果物化在叶子节点中，供应用程序进行极低延迟的高并发直接读取。这为后续深入探讨如何在算子内部支持“部分状态”奠定了架构基础。 ### [11:02](https://www.youtube.com/watch?v=GctxvSPIfr8&t=662s) 数据流图的构建与增量维护机制 关系型 SQL 查询在编译后会被映射为底层的数据流图（Dataflow Graph）。以包含聚合与连接的视图为例，查询中的 `COUNT` 聚合对应数据流中的 `SUM` 算子，并按照 `stories.id` 进行分组（该字段等同于 `votes.story_id`）；而表之间的关联则对应 `JOIN` 算子。值得注意的是，数据流图中的算子排布往往与直觉相反：连接算子并非直接连接原始的 `stories` 表与 `votes` 表，而是连接 `stories` 表与已完成票数统计的聚合算子节点。Jon Gjengset 指出：“Noria has decided that it's going to do the aggregation first for optimization purposes.”（Noria 出于查询优化的考虑，决定先执行聚合操作）。当应用层需要从物化视图 `StoryWithVC` 读取数据时，会发起带有动态运行时参数的查询（例如 `SELECT * FROM StoryWithVC WHERE id =?`），该参数直接作为查找键（Lookup Key），从物化视图中精准提取应用所关心的数据子集。 ```mermaid flowchart TD accTitle: Dataflow Graph and Incremental Update accDescr: An illustration of how an incoming vote generates deltas through count and join operators down to the materialized view. subgraph Inputs ["底层基础表与输入变化"] StoriesTable["stories 表"] VotesTable["votes 表\n(+1 票: story 7)"] end subgraph Pipeline ["数据流流水线处理"] CountOp["Count 聚合算子\n生成正负增量 (-7, 42) & (+7, 43)"] JoinOp["Join 连接算子\n查询 stories 表拼接完整属性"] end subgraph Views ["下游物化视图"] MV["StoryWithVC 物化视图\n(原票数 42 更新为 43)"] end VotesTable -->|"注入变化"| CountOp StoriesTable -.->|"数据补全"| JoinOp CountOp -->|"流动增量"| JoinOp JoinOp -->|"最终增量"| MV ``` 当下层基础表发生数据变更时，系统无需重新计算整张视图，而是采用增量流式更新（Incremental Streaming Update）。以故事 7 新增一张投票为例，Noria 会将这一变更注入到 `votes` 表对应的数据流节点中，并沿着图中的边向下游流动： - **生成正负增量（Deltas）：** 投票流经计数算子时，算子会将 `+1` 的原始投票转换为两个操作：旧计数的负增量与新计数的正增量（例如 `(-7, 42)` 与 `(+7, 43)`）。Jon Gjengset 用拟人化的口吻解释这条消息的含义：“It used to be that the count for story 7 was 42. Forget that, it is now 43”（故事 7 过去的票数是 42；忘掉它，现在是 43）。 - **拼接完整数据列：** 连接算子接收到上述增量后，为了满足下游视图对 `stories` 属性列的需求，会向 `stories` 表发起查找，补齐所需的全部列数据。 - **就地更新物化视图：** 最终拼接完成的增量流入末端的 `StoryWithVC` 视图进行就地修改（In-place Update）。此后针对该条目的读请求将直接读到最新的票数 43。 --- ### [14:08](https://www.youtube.com/watch?v=GctxvSPIfr8&t=848s) 部分状态（Partial State）的核心思想：学会遗忘 完整物化整张视图在实际生产中存在严重的资源浪费，而部分状态（Partial State）构成了本篇博士论文的核心创新。Jon Gjengset 将其精辟地总结为“学会遗忘（learning to forget）”。在真实的 Web 负载中，视图绝大多数条目极少被访问，陈旧冷门的故事常年滞留并白白占据大量内存。他质问道：“if no one ever reads story 7, why are we storing its result? Furthermore, why are we even computing, and keeping the results up to date, if no one reads them?”（如果从来没人读故事 7，我们为什么还要存它的结果？更进一步，如果没有人读，我们为什么还要耗费算力去持续计算并保持它的更新？）。 传统的物化视图缺乏精细剔除与按需加载的机制，总是尝试维护全局完整数据集。为此，本论文提出了三大核心学术贡献： - **物化视图中的缺失状态（Missing State）：** 允许系统显式将某些条目标记为“缺失”（Missing），彻底免去常驻内存开销。 - **上溯查询机制（Upqueries）：** 建立利用既有数据流图按需动态回填缺失状态的一整套通信范式。 - **系统实现与落地评测：** 在 Noria 数据流物化视图系统中完整实现部分状态并完成端到端性能评估。 --- ### [15:52](https://www.youtube.com/watch?v=GctxvSPIfr8&t=952s) 参数化视图定义与按需加载机制 为了让视图支持部分物化，系统必须消除“视图定义”与“外部查询”之间的语义鸿沟。传统做法中二者相互割裂，底层数据流无法获知应用层在运行时究竟会用什么主键做筛选。Noria 的方案是将查询参数直接融入视图本身的定义中，例如通过在视图语句中包含 `WHERE story_id =?`，将占位符 `?` 声明为视图的核心参数化索引键。应用执行读取时，直接带着具体的参数值（如故事 7）向 Noria 发起请求。 ```mermaid flowchart TD accTitle: Upquery Execution and Eviction accDescr: Showing how an upquery travels upward to retrieve missing state and how eviction works downstream. subgraph ClientLayer ["客户端读取"] ClientReq["客户端查询: story 7"] end subgraph FlowGraph ["Noria 数据流算子图"] JoinNode["Join 算子\n(无状态: 向上转发 Upquery)"] CountNode["Count 算子\n(含内部物化视图，命中缓存 42)"] StoriesData["stories 基础表"] end subgraph MatView ["末端部分物化视图"] ViewEntry["StoryWithVC 物化视图\n(故事 7 处于缺失状态 / 空心框)"] end ClientReq -->|"1. 请求读取"| ViewEntry ViewEntry -->|"2. 触发 Upquery (向上溯源)"| JoinNode JoinNode -->|"3. 递归向上转发"| CountNode CountNode -->|"4. 单消息回传当前状态 (向下顺流)"| JoinNode StoriesData -.->|"补全字段"| JoinNode JoinNode -->|"5. 沿既有流传递增量"| ViewEntry ViewEntry -->|"6. 填充空心框并响应"| ClientReq ``` 当请求到达物化视图时，系统若发现故事 7 对应的条目尚未物化（表现为图中的空心绿框），就会启动上溯查询（Upquery）流程： - **递归向上索取历史汇总：** 缺失状态的视图算子会向上游发出 Upquery，实质上是在要求上游重传该键过去的所有增量汇总。Jon Gjengset 形象地将其描述为下游算子在向上喊话：“tell me about 7 again, because I forgot all about it”（再告诉我一次关于 7 的信息吧，因为我把它全给忘了）。 - **递归穿透与算子内部缓存：** 连接算子本身是无状态的（Stateless），它会将 Upquery 递归转发至其具有状态的祖先节点——计数聚合算子。由于计数算子内部也维护着一份自己历史输出的“小物化视图”，因此它无需回溯到底层的 `votes` 原始表，即可直接命中故事 7 的当前统计值。 - **复用既有前向数据流通道：** 上游算子响应 Upquery 时，并没有开辟特殊的逆向通信信道，而是把该键的当前快照打包成一条普通的数据流增量消息，沿现有的前向流水线向下推送。流经连接算子补齐字段后，该消息抵达视图填补空心框，最终向应用返回查询结果。后续针对故事 7 的读取则直接由物化视图在内存中完成，无需重复溯源。 --- ### [20:25](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1225s) 内存驱逐策略与冷数据更新丢弃机制 动态填充状态的最终目的，是为了在条目变冷后安全地将其从内存中移除。当故事 7 逐渐失去热度并成为冷数据时，Noria 可以在任意内部节点对其执行逐出（Eviction）：既可以将其从底部的物化视图中剔除，也可以将其从中间计数算子的内部物化状态中抹去，将节省下来的内存让渡给新的热门条目。 更深远的影响在于计算资源的节约。假定故事 7 已被完全驱逐出内存，随后原始 `stories` 表修改了该故事的标题： - **阻断无效数据流更新：** 标题变更会触发一个下行更新增量流动至连接算子。 - **兄弟节点状态探测：** 连接算子试图联合聚合算子的状态以补全该更新时，发现聚合状态中关于故事 7 的记录同样处于缺失状态。 - **安全丢弃变更：** 只要发现兄弟算子中该键的状态缺失，通常就意味着下游物化视图同样没有物化该条目。既然下游无物化状态可更，连接算子便能直接安全地抛弃（Discard）这条更新，从而彻底规避无用计算。在完成部分状态机制的核心阐述后，演讲正式切入到相关工作（Related Work）的对比与讨论环节。 ### [22:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1327s) 相关工作对比：物化视图、自动化缓存与流处理系统 传统物化视图（Materialized Views）的设计目标与本研究所针对的场景截然不同。在传统数据库领域，物化视图通常服务于需要定期查看复杂报表的分析师。由于分析师极少执行这些耗时的大型查询，系统倾向于在后台持续维护视图，确保分析师调用时能瞬间返回结果。其重心完全偏向于写入侧的维护效率，因为写入吞吐量高、更新频繁，而读取频率极低；只要读取时的开销远低于从头执行全量查询，哪怕读取操作需要临时做一些处理也是可以接受的。此外，传统物化视图通常直接编译进程序或专用引擎，缺乏对动态按需查询的支持，更不具备状态淘汰（Eviction）机制，因为在整个分析师查询的视图中，并不存在某个子集比其他数据更为重要的概念。 工业界与学术界也涌现出许多自动化缓存系统（Automated Caching Systems），但它们往往针对特定的业务痛点进行深度定制，缺乏开箱即用的通用性。Jon Gjengset 指出：“What usually happens is some large company has a particular caching problem, they build a solution that works for them, but you can't just spin that up in your Ruby on Rails application.”（通常的情况是，某家大公司遇到了特定的缓存瓶颈，他们打造了一套专有方案，但你根本不可能把它直接搬到自己的 Ruby on Rails 应用里使用）。这些缓存系统大多只支持缓存失效（Invalidation）而无法做到增量就地更新（Incremental Updates），导致缓存命中率低下，频繁回源访问后端。同时，它们深度绑定于特定的 ORM 或开发框架，而 Noria 的目标则是面向通用 SQL，允许开发者像使用参数化预编译语句（Prepared Statements）一样灵活编写视图与查询。 流处理系统（Stream Processing Systems）与通用数据流系统虽然擅长处理增量更新，但它们同样将重点放在写性能和强一致性（Strong Consistency）上。强一致性往往以牺牲读延迟为代价，读取操作通常需要与写入数据流进行协同，甚至必须穿透到写入处理流水线中才能获取一致视图。相比之下，Noria 借助最终一致性（Eventual Consistency）模型，利用 Web 应用对轻度陈旧数据（Stale Data）的容忍度，实现了极低的读延迟。更重要的是，现有的流处理系统几乎不支持按需计算和局部数据淘汰；若想释放视图中的部分状态，通常只能直接终止整个计算任务。 - **传统物化视图局限**：针对低频分析师查询优化，侧重写入维护开销，缺乏淘汰机制与动态按需查询支持。 - **专有自动化缓存短板**：架构高度定制化且侵入性强（依赖 ORM），以失效淘汰为主，缺少针对通用 SQL 的增量就地维护。 - **传统流处理框架限制**：为追求强一致性而牺牲读延迟，读取与写入路径强耦合，无法对物化视图中的部分键进行细粒度按需淘汰。 --- ### [25:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1548s) 部分状态化的核心挑战：精确一次语义与并发更新 当系统从“全量计算”转向“部分状态物化”时，系统实现的复杂度急剧上升。Jon Gjengset 幽默地谈到了这种工程挑战带来的学术价值：“And unfortunately that's not the case. Although if it were, this thesis wouldn't be very valuable, and so I'm kind of glad that there are more challenges.”（不幸的是现实并非如此简单。不过如果真那么简单，这篇博士论文也就没什么价值了，所以我其实挺庆幸还存在更多挑战的）。在底层，系统必须严格保证基础表的数据变更在视图中生效“精确一次”（Exactly-once）。在传统数据库中，行数据通过索引扫描或全表扫描处理，除非出现系统 Bug，否则单次插入绝不可能被错误执行多次或无故丢失；但在 Noria 的数据流架构中，维持这一语义变得极为困难。 这种复杂性主要源于两个关键机制的相互交织： 1. **向上查询（Upquery）与流式更新（Update）的并发执行**：向上查询本质上是历史状态的快照聚合（例如查询第 7 号文章过去的所有增量状态）。当向上查询沿数据流向上回溯的同时，关于第 7 号文章的新更新可能正沿着数据流向下传播。系统必须保证快照与新数据不发生重叠计算或顺序倒退，防止数据被重复应用或旧数据覆盖新数据。 2. **提前丢弃（Early Discard）带来的陈旧风险**：为了节省不必要的状态维护成本，当算子发现兄弟节点缺失状态时，通常会选择尽早丢弃更新。然而，如果下游物化视图其实存在依赖于该更新的状态，这种过早的丢弃就会导致下游视图产生“永久性陈旧”（Permanently Stale），再也无法接收到正确的更新通知。 ```mermaid flowchart TD accTitle: Upquery and Streaming Update Hazard accDescr: Concurrency hazard between on-demand upqueries fetching past state and continuous streaming updates flowing downstream. subgraph BaseTables["基础存储层"] BT["基础表 (Base Table)"] end subgraph DataflowPipeline["数据流引擎"] UQ["向上查询 (Upquery)<br/>回溯拉取历史状态"] ST["流式更新 (Streaming Updates)<br/>实时下发数据变更"] OP["部分状态算子 (Partial Operator)"] end subgraph Views["物化视图层"] MV["部分物化视图<br/>(Materialized View)"] end BT -.->|"汇总历史数据"| UQ UQ ==>|"并发填充缺失值"| OP BT -->|"实时变更增量"| ST ST ==>|"并发推送更新"| OP OP -->|"必须满足 Exactly-Once"| MV ``` --- ### [27:48](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1668s) 不一致连接淘汰（Incongruent Join Evictions）的困境与权衡 在诸多潜在的状态危险（Hazards）中，Jon Gjengset 重点剖析了一个最具代表性的难题——“不一致连接淘汰”（Incongruent Join Evictions）。这是一个他自创的名词。所谓“不一致连接”（Incongruent Join），指的是视图查询所使用的键（Query Key）与连接操作本身的键（Join Key）不一致。例如在文章展示场景中，系统定义了一个 `StoriesWithAuthor` 视图，将 `stories` 表（包含 `id`、`author_id` 等）与 `users` 表（包含 `id`、`name` 等）进行连接。用户查询该视图时使用的是文章 ID（`story_id`，即查询键），但连接操作依赖的却是作者 ID（`author_id`，即连接键）。 在常规的向上查询流程中，这套机制能够正常运转：当客户端查询 7 号文章时，无状态的连接算子将向上查询转发给 `stories` 表；`stories` 表返回一条更新消息（例如文章 7 的作者是 42 号）；连接算子拿到后，向 `users` 表查找 42 号用户，成功查出作者姓名为 Lena；算子将两者拼接后发送给下游物化视图，填补了原本缺失的“空心方块”（Hollow Box）。 然而，当发生数据变更且伴随缓存未命中时，系统就会陷入两难境地。假设 7 号文章的作者发生了变更，数据流会产生一正一负两个增量：负增量（Negative Delta）用于删除旧作者的数据，正增量（Positive Delta）用于插入新作者的数据。当负增量到达连接算子时，它查找到旧作者 42（Lena）并向下游下发删除；紧接着正增量到达，要求连接算子查找新作者 43 的信息，此时如果 `users` 表发生未命中（例如 `users` 表本身是由更上游的数据流驱动的视图，其内部并不包含 43 号用户的状态），连接算子便无法组装出完整的输出行。 面对缺失状态的更新，连接算子陷入了死锁困境： - **方案 A（仅下发负增量，丢弃正增量）**：下游物化视图中关于 7 号文章的记录被彻底抹去。后续对 7 号文章的读取将返回空结果，产生严重的逻辑错误。 - **方案 B（整体验证失败，全部丢弃）**：下游物化视图将保留旧数据。后续读取仍会显示旧作者姓名，导致数据无法收敛，产生永久性陈旧。 - **方案 C（触发向上查询以同步填充缺失状态）**：直觉上，系统可以让算子挂起数据流，去向上查询 43 号用户的数据。但 Jon Gjengset 解释道：“Because we can't… we would have to hold up the dataflow at the join until that upquery finishes. And that might potentially take a long time.”（因为我们做不到……我们必须在连接算子处阻塞整个数据流，直到该向上查询完成为止。而这可能会耗费极长的时间）。如果上游视图十分复杂，长时间挂起核心管道将严重摧毁数据流引擎的吞吐能力。 | 处理策略 | 具体操作 | 产生的严重缺陷 | |:--- |:--- |:--- | | **仅下发负增量** | 下发旧数据的删除，丢弃无法填充的新数据 | 下游视图行记录直接蒸发，查询返回空数据（数据丢失） | | **全部丢弃更新** | 忽略本次作者变更产生的所有增量更新 | 下游视图保留过期的旧作者信息，陷入永久陈旧 | | **同步挂起阻塞** | 挂起连接管道，发起向上查询拉取 43 号用户 | 核心数据流被长时间阻塞，严重拖垮全流水线吞吐量 | ### [03:50](https://www.youtube.com/watch?v=GctxvSPIfr8&t=230s) 避免死锁与阻塞：用驱逐（Eviction）解决不协调 Join 在上游存在庞大数据流图的情况下，若一个 Join 节点为了处理更新而必须触发向上查询（Upquery），该 Upquery 可能需要耗费极长的时间才能完成。在此期间，Join 节点完全无法处理任何后续更新，整个数据流被迫停滞，写操作处理陷入僵局。更致命的是，系统中可能出现死锁：Join 节点必须等待 Upquery 返回才能继续处理更新，而该 Upquery 在上游的计算过程偏偏又依赖 Join 节点去处理后续的更新。“Where the join can't process more updates until the upquery finishes, but the upquery cannot finish until the join processes more updates. And now we're stuck.” Jon Gjengset 解释道。由于后续更新很可能存在逻辑依赖，系统无法简单地通过乱序处理更新来绕过死锁，当前更新必须先行完成。 针对这一困境，部分状态（Partial State）本身提供了一种优雅的逃生通道——主动驱逐（Eviction）。以故事（Story）与作者更新为例，既然 Join 节点此时不知道更新后故事 7 的作者到底是谁，它大可不必阻塞并强行发起 Upquery，而是直接向后游传递一条驱逐消息，把故事 7 从下游的物化视图（Materialized View）中剔除。后续若再有针对故事 7 的查询到达，Noria 只需通过常规且已被验证完全可行的 Upquery 流程按需把缺失状态补齐即可。更巧妙的是，Noria 能够静态检测数据流中哪些地方存在不协调 Join（Incongruent Join），仅在必要时才发送驱逐消息，而无需在所有 Join 节点上都采取这种重置策略。 ```mermaid flowchart TD accTitle: Eviction Resolution for Incongruent Join accDescr: 当不协调 Join 无法立即解析状态时，向下游发送驱逐信号，使后续读取按需触发 Upquery 回填。 subgraph JoinBlock["不协调 Join 场景"] J["Join 节点<br/>（缺少故事 7 的完整数据）"] E["向下游发送<br/>驱逐消息 (Eviction)"] MV["下游物化视图<br/>（剔除故事 7 缓存）"] J -->|"避免阻塞与死锁"| E E --> MV end subgraph Refill["后续按需回填"] Q["客户端查询<br/>Story 7"] UQ["触发标准 Upquery<br/>从上游拉取完整数据"] Q --> MV MV -->|"Cache Miss"| UQ end ``` --- ### [34:26](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2066s) 真实负载基准评测：Lobste.rs 业务模型与测试设计 为了验证内部机制如此复杂的部分状态物化视图是否真的实用、会不会因为过度复杂而彻底拖垮性能，Jon Gjengset 选取了一个高仿 Hacker News 的真实开源新闻聚合社区——Lobste.rs 作为评测对象。在 Lobste.rs 中，用户提交故事、点赞投票、发表评论并浏览各类最热榜单。选择它的核心考量有两点：其一是代码开源，能够直接提取各类页面请求实际执行的 SQL 查询；其二是该网站公开了详尽的运行数据统计指标（例如每秒请求总量、各页面访问比例、高频活跃用户与热门故事的访问分布等）。 依据这些真实统计分布，Jon Gjengset 构建了一个针对 Lobste.rs 的合成负载生成器（Workload Generator）。该工具支持人为调节并发压力以观察系统的极限承载能力，并且配备了可插拔的存储后端，能够直接对 MySQL 和 Noria 进行同台对比。此外，由于生成器直接对接数据库底层，测试完全绕过了网站原生的 Ruby on Rails 框架层，从而排除了前端脚本执行开销对真实存储后端吞吐能力的干扰。 --- ### [36:01](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2161s) 极限吞吐对比：MySQL、全量状态 Noria 与部分状态 Noria 在配备 16 核心 CPU 的 Amazon EC2 实例上进行的极限吞吐量测试展示了极为悬殊的性能差距： ```mermaid flowchart LR accTitle: System Throughput Comparison on Lobste.rs Workload accDescr: MySQL、无部分状态 Noria 与有部分状态 Noria 在 Lobste.rs 真实负载下的页面处理吞吐对比。 M["MySQL (反范式化)<br/>~400 pages/sec"] N1["Noria (无 Partial State)<br/>~4,500 pages/sec (瓶颈: 128GB 内存)"] N2["Noria (带 Partial State)<br/>~7,500+ pages/sec (18x MySQL, 瓶颈: Upquery 路径)"] M -->|"物化视图加速 (10x)"| N1 N1 -->|"部分状态驱逐节省内存 (+67%)"| N2 ``` - **MySQL 后端**：在核心全部跑满、延迟急剧飙升崩溃之前，系统吞吐量停留在约 400 pages/second。Jon Gjengset 特别指出，这已经是在高度反范式化（Denormalized）表结构下取得的成绩——Lobste.rs 开发者在应用层耗费心血将投票数等聚合数据作为“Hotness”列直接固化到 Stories 表中，从而省去了大部分查询时的聚合计算。如果直接使用未反范式化的纯净 SQL 规范模式，“the throughput for MySQL… it can't even keep up with a single page request per second.” - **无部分状态的 Noria（Without Partial State）**：物化视图的优势立刻显现，由于绝大多数读请求被转化为简单的键值点查，吞吐量提升了近一个数量级，达到了约 4,500 pages/second。然而系统此时撞上了新的硬瓶颈：机器并非 CPU 算力耗尽，而是 128 GB 物理内存彻底耗尽。随着时间推移物化状态不断膨胀，长时间运行甚至难以维持该吞吐量。 - **带部分状态的 Noria（With Partial State）**：吞吐量比无部分状态版本进一步提升了约 67%，达到 MySQL 的 18 倍以上。更关键的是，此时系统并没有跑满全部 CPU 核心，更没有耗尽内存。其承载上限受制于一条包含高频写入的数据流路径中的 Upquery 处理效率，依然保留了代码优化的空间。 - **内存消耗对比**：在无部分状态 Noria 接近崩溃的负载临界点上，无部分状态版本吃掉了超过 100 GB 内存，而引入了部分状态机制的 Noria 仅占用了其中的三分之一（约 30 多 GB）。 --- ### [39:13](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2353s) 与理想化 Redis 缓存的理论极限逼近 面对“如果开发者自己在应用层手写缓存，Noria 是否还有竞争力”的质疑，Jon Gjengset 指出，由于手写缓存的表现深度绑定具体业务逻辑与工作负载，很难一概而论。为此，他设计了一个高度理想化的极速缓存基准测试：无驱逐、零 Cache Miss、绝大多数请求均为只读且全部是单一的主键查询，查询语句仅保留最基础的故事与票数统计。测试选用了工业界常用的键值缓存 Redis 作为对照标杆。 在这一理想负载下，单线程运行的单核 Redis 跑出了近 100 万 requests/second 的极限成绩。为了公平对比 16 核服务器上的潜能，Jon Gjengset 将单核 Redis 的结果直接乘以 16，得出了一个假设 Redis 能在多核间做到绝对线性扩展的理论吞吐上限（Theoretical Maximum）。随后让 Noria 运行完全相同的负载：在保证完整 SQL 接口、全自动增量物化和无需任何应用层手写缓存维护逻辑的前提下，Noria 充分利用多核资源自动驱动读取、驱逐与视图更新，最终达成了逼近 Redis 理论上限二分之一以内的极佳成绩。 --- ### [41:18](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2478s) 未来演进方向与学术致谢 演讲最后，Jon Gjengset 探讨了 Noria 及部分状态技术尚未解决的局限与未来的拓展方向： - **高级查询算子缺失**：目前 Noria 无论是否开启部分状态，均不支持范围查询（Range Queries）、游标（Cursors）以及滑动时间窗口（Time-windowed）算子，这一领域有待深入探索。 - **对接现有数据源**：支持将 Noria 无缝挂载至 Postgres、MySQL 等用户现存的真实底层主数据库（Source of Truth）之上，而非必须完全托管底层表。 - **端到端响应式架构**：让物化数据流穿透服务端边界，将变更增量直接推送到移动端或浏览器前端展示子集视图，契合现代响应式编程（Reactive Applications）的发展潮流。 - **基于部分状态的容错自愈**：当数据流内部节点发生宕机崩溃时，系统无需复杂的恢复机制，只需将挂掉节点持有的状态直接标记为“缺失”，随后利用现成的部分状态与 Upquery 机制在运行中透明且按需地重构状态。 在总结致谢环节，Jon Gjengset 表达了对导师 Robert Morris 和 Frans Kaashoek 的感激。他坦言自己最初只有一些模糊的原型想法，是两位老师多年来不断提问施压、磨砺核心论据，才逼着他构建出如今严密的学术论证闭环。同时他也向课题组博士后 Malte 致谢，强调若没有 Malte 的关键贡献，“Noria wouldn't have SQL. It wouldn't have query optimization. It would essentially just be a dataflow system.” ### [44:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2647s) 致谢委员会、实验室成员、家人与伴侣 在结束研究内容的汇报后，Jon Gjengset 首先向论文委员会成员表示由衷的感激。他特别提到能够邀请到 Sam Madden 教授加入委员会是一件非常荣幸的事，因为这让他得以汲取深厚的数据库领域经验。Jon 带着系统研究者的幽默自嘲道：“Which is something that he has a lot more of us than us mere systems people.”（在这方面，他的经验远比我们这些纯粹做系统的人丰富得多）。紧接着，他向麻省理工学院并行与分布式操作系统（PDOS）实验室的全体成员致谢，称赞那里的伙伴们拥有永无止境的好奇心、深刻的学术洞察力和全方位的支持，正是这样的学术氛围将他塑造为今天的研究者，如果没有这些同伴多年来的陪伴与启发，他绝不可能走到今天这一步。 随后，现场的氛围转向温馨而感性。Jon 感谢了自己的父母和继父母，感激他们多年来始终如一地鼓励他追求自己的热爱与兴趣，无论这些追求在外人看来多么“极客”（geeky）。正是家人一路上的温柔推动，才让他最终站在这里，向大家呈现这场硬核的极客学术汇报，他相信家人看到今天的成果也会感到十分欣见与欣慰。最后，Jon 将深情留给了女友 Talia，感慨在撰写论文、进行实验评估以及准备答辩演示的漫长日子里，自己常常连续好几个小时将自己关在房间里闭关苦干，而 Talia 给予了难以置信的包容与陪伴。他动情地坦言：“I am so grateful and happy that I have her, and… I love you.”（能拥有她我感到无比感激与幸福，我爱你）。 - 委员会专家支持：吸纳了 Sam Madden 在数据库体系结构方面的深厚造诣，弥补了纯系统工程视角的局限。 - MIT PDOS 实验室：实验室充满求知欲与思辨的集体氛围，是本项研究得以持续推进并成型的重要支柱。 - 家庭与伴侣：家人的长期鼓励促成了其极客学术之路的坚持，伴侣 Talia 在冲刺阶段的宽容与支持则是最坚实的后盾。 ### [45:24](https://www.youtube.com/watch?v=GctxvSPIfr8&t=2724s) 博士论文总结与核心贡献 在答辩演讲的收尾环节，Jon Gjengset 用简练而坚定的语言提炼了整篇博士学位论文的核心价值与体系创新。他指出，该项研究的根本突破在于打破了传统物化视图与应用层缓存之间的壁垒，真正让物化视图（Materialized Views）能够作为系统级缓存直接投入生产环境使用。这一目标是通过引入“部分有状态物化”（partially stateful materialization）机制实现的，即系统允许物化视图中存在缺失状态，打破了必须全量物化的苛刻限制；当应用发起查询遇到缺失状态时，系统则通过创新的“向上查询”（upqueries）机制，在数据流内部按需动态填补缺失数据。 Jon 总结指出，整套体系从根本上改变了现代 Web 应用与读密集型系统的架构模式：“The resulting system provides automated caching for SQL queries, and reduces the need for complex, ad hoc caching logic.”（最终构建的系统为 SQL 查询提供了完全自动化的缓存支持，极大地减少了应用开发者对复杂、临时且易出错的应用层缓存逻辑的依赖）。这不仅让底层数据库系统具备了透明扩容和极低延迟读取的能力，也让开发者从维护一致性缓存的繁重泥潭中解脱出来。语毕，Jon 向在线聆听的所有评委与观众致谢，并邀请大家展开提问交流。 ```mermaid flowchart TD accTitle: Noria 核心机制与目标架构 accDescr: 展示部分状态物化视图通过向上查询按需补充缓存，进而替代复杂应用层缓存的流程 subgraph MV ["物化视图层（Materialized Views as Caches）"] PS["部分有状态物化<br/>(允许状态局部缺失)"] UQ["Upqueries 机制<br/>(按需沿数据流回填)"] PS -->|"遇到 Cache Miss"| UQ end subgraph Value ["系统价值与收益"] AC["SQL 查询透明自动缓存"] RC["消除应用层 Ad-hoc 缓存逻辑"] end UQ --> AC AC --> RC ``` - 核心架构转变：将物化视图转化为功能完备、可自动淘汰换入的透明动态缓存。 - 技术杠杆：通过部分状态存储（Partial State）降低内存消耗，结合向上查询（Upqueries）保障按需即时物化。 - 工程价值：为 SQL 提供内置透明加速，彻底终结了在应用侧编写 Redis/Memcached 胶水代码与维护双写一致性的痛苦。 - 答辩收尾：演讲结束并正式进入评审委员会与公众的 Q&A 提问环节。 ## Notable quotes > [22:07](https://www.youtube.com/watch?v=GctxvSPIfr8&t=1327s) What usually happens is some large company has a particular caching problem, they build a solution that works for them, but you can't just spin that up in your Ruby on Rails application. — Jon Gjengset ## Mentioned Jon Gjengset, Robert Morris, Frans Kaashoek, Sam Madden, Malte Schwarzkopf, Talia, Noria, MySQL, Redis, PostgreSQL, Memcached, Ruby on Rails, Lobste.rs, Hacker News, Amazon EC2, MIT PDOS ## Video description This is my PhD dissertation presentation, which I gave at MIT (virtually) on October 22nd, 2020. It was immediately followed by my thesis defense, which I passed subject to the typical bits and pieces of revisions the committee wanted to see. The person who introduces me in the video is Robert Morris, my thesis advisor. The Q&A has been cut out, as I want to edit it a bit and mix in questions from the public presentation I gave on YouTube the day before. I will link the Q&A video here once it is out. You can find the slides at https://jon.thesquareplanet.com/slides/thesis.pdf and at https://docs.google.com/presentation/d/1w2PlmqUIeue8VcNhBqOC0V3GTKQs9zBccrhd9tfAang/edit?usp=sharing. The thesis is available at https://jon.thesquareplanet.com/papers/phd-thesis.pdf. What follows is the thesis abstract: This thesis proposes a practical database system that lowers latency and increases supported load for read-heavy applications by using incrementally-maintained materialized views to cache query results. As opposed to state-of-the-art materialized view systems, the presented system builds the cache on demand, and evicts cache entries in response to a shifting workload. The enabling technique the thesis introduces is partially stateful materialization, which allows entries in materialized views to be missing. The thesis proposes upqueries as a mechanism to fill such missing state on demand using dataflow, and implements them in the materialized view system Noria. The thesis then discusses additional mechanisms needed to establish eventual consistency for partially stateful dataflow. Noria with partial materialization saves application developers from implementing their own ad hoc caching mechanisms to speed up their database accesses. Instead, the caching is built into the database, and is transparent to the application. Experimental results suggest that the presented system increases supported application load by up to 20x over MySQL and performs similarly to an optimized key-value store cache. Partial state also reduces memory use by up to 2/3 compared to traditional materialized views. [Source](https://www.youtube.com/watch?v=GctxvSPIfr8)

Source quotes

[22:07] Jon Gjengset: What usually happens is some large company has a particular caching problem, they build a solution that works for them, but you can't just spin that up in your Ruby on Rails application.

Source quotes

[14:08] Jon Gjengset: The observation here is that the chances are most entries in any given view are not accessed.

Original transcript

[0:00] Hey everyone! Hello. Welcome to Jon Gjengset's  thesis defense. And thank you for attending. [0:07] I want to say just a couple of words before handing over to Jon. [0:10] In his research life, Jon's been pursuing a really neat vision for how busy web sites ought to manage their data. [0:17] It's been exciting to watch him develop this vision  and impressive to see his skill in realizing it. [0:22] But in parallel with research, Jon's been  a hugely energetic contributor to all the [0:27] communities he touches. From his infinite patience  as a TA, to organizing graduate student events, [0:32] to live-streaming systems programming tutorials.  Jon's sure to be valuable and valued whatever he [0:38] sets his hand to. And assuming his committee lets  him go, many people at MIT are going to miss him. [0:44] I certainly will. [0:45] So with that, I'll hand over to Jon. [0:48] Thank you Robert, I appreciate that! [0:51] So, thank you everyone for coming, and welcome to  my doctoral dissertation presentation [0:57] where I'll be presenting my thesis on Partial State in Dataflow-Dased Materialized Views. [1:04] Now, my goal with this presentation is to try to summarize the  past six years of work or so in about 45 minutes. [1:11] And hopefully I will succeed. And at least,  hopefully, by the end, you will understand what [1:16] the words in the title mean. And why I think it  was worthwhile to spend six years doing this work. [1:22] Now, don't worry, this work was supervised. My  committee, Robert, who you just saw, but also [1:29] Frans, Sam, and Malte, have been working with  me in basically trying to figure out that this [1:35] work is worthwhile, and to make sure that what  comes out of it is something that is valuable. [1:41] So, I want to start this presentation with "Why are we here?". [1:45] And not in the existential sense of, like, "why are we all on this planet?". [1:48] But more in the sense of "Why am I here?" — "Why am I talking to you at all?". [1:53] I am here because I want to make databases better. [1:56] And in order to understand the way in which I want to do that, we first need to talk a little bit about what databases are, [2:02] in order to understand the problems that some applications have with them. [2:06] So let's do a little bit of database 101. [2:08] So here, in databases, you just sort of take some tables. In this case, we're going to work with a stories table and a votes table. [2:16] And these two tables hold stories and votes. [2:19] And then the idea is that, as an application, you can query these tables by issuing "queries". [2:25] And these queries might do all sorts of things, like they might aggregate and combine values, or they might [2:30] join different tables together, in order to produce some application [2:34] data that it might care about. And the  query operations are here shown in orange. [2:41] If you want to modify the  data, then you perform an [2:43] "insert" or an "update" or a "delete" directly  into the tables at the bottom. So here, if you [2:48] wanted to insert a new vote, then you just make  that insert operation directly to the votes table. [2:55] And even though inserts in SQL, and  updates and deletes, are "queries", [2:59] I will not be referring them as such in this talk.  Rather, I will be talking about queries as things [3:03] that read data. Think SELECTs. Whereas inserts,  updates, and deltes, are "writes" or "updates". [3:11] And now that we've looked at this picture, you  might see that there is a lot more orange here [3:16] than blue. And what this indicates is that if you  do a read, you have to do more work than if you're [3:21] doing a write. But this is unfortunate, because  in practice many applications, and in particular [3:26] web applications, are read-heavy. They do a lot  more reads relative to the number of writes. [3:32] And then it seems unfortunate that the  reads are also the most expensive operation. [3:37] And so, ideally we want some way to mitigate  this problem. Because it becomes pretty severe [3:44] once you look at applications that  issue many many read queries that are [3:48] either identical or similar, where there is  a lot of work that is a same in executing any [3:52] given query. And it'd be great if we didn't  have to do this repeated, unnecessary work. [3:58] And you might say, well Jon, this problem has been  solved: you just use a cache. And it's true that [4:03] caches are great. Caches are essentially a storage  system that you place in front of your database. [4:09] And the idea is that the queries look in the  cache, and if the result is there, then they just [4:14] return immediately, and the reads are now fast.  And then only if you miss in the cache — if the [4:19] result you're after is not there — you  issue a query to the backend database. [4:24] And it's true that this does make queries  fast. And there are some other similar schemes, [4:29] like denormalization where you store and  maintain derived values like the number [4:34] of votes for a story in the stories  table, that has a similar effect. [4:40] And it's true that caches are great, but  unfortunately they're also really hard to [4:43] get right. This diagram is an attempt to  summarize some of the things that you have [4:49] to get right in the application in order to use  this kind of a caching strategy correctly. So, [4:56] the cache is great, but as the data in the  tables changes, the cache becomes out of date. [5:02] And it needs to somehow be refreshed. So imagine  that we insert a new vote into the votes table, [5:07] the cached vote count is now wrong. And so the  path of the application that inserts this new vote [5:14] also needs to invalidate or somehow mark the cache  as being outdated, and maybe refresh that value. [5:21] Furthermore, even though it is easy to say that  if you miss in the cache you have to query, [5:25] it's hard to figure out how this should work  in practice. Imagine that 100,000 people want [5:31] to read a particular story, but that story is not  present in cache. Do all those application queries [5:37] all swarm the database, and all execute the  same query? That seems wasteful too. And [5:44] even if they do that, we still need some way to  fill the cache. If all of them read when they [5:49] miss, someone has to write that value back into  the cache. And orchestrating who should do that is [5:55] not entirely trivial. Beyond this, over time, the  cache is going to accumulate more and more values. [6:02] And we only have so many resources  on the server that's serving these [6:07] requests. And so we need some way to evict  from this cache, entries that are old or [6:12] unpopular. But then the question arises again:  who does this eviction, and how? And hopefully [6:18] this image gives you an idea of just all the  stuff that needs to be figured out by the [6:23] application developers in order to make databases  serve these kinds of read-heavy workloads. [6:28] And so in my research, I've been looking  specifically at this problem of automatic [6:33] database caching. Specifically, is there a  way that we can get all this cache logic to [6:38] not reside in the application, and instead  be provided by the database. And that is what [6:44] my thesis implements, and what we're going  to be looking at for the rest of the talk. [6:48] Now, the way we're going to do that is we're  going to be walking through the title of the [6:52] thesis. Which, to remind you, is partial  state in dataflow-based materialized views. [6:56] And what we're going to do is we're going  to parse the title from right to left. And [7:01] then move through the words and figure out  what they mean and how they fit together. [7:05] So let's start with materialized views. And in  particular, why they're useful in this context. [7:11] Materialized views have been around for a long  time; they were invented by the database community [7:15] in the early 1980s. And essentially they are  running the query and then remembering the result. [7:23] Which sounds like a fairly straightforward  thing — it sounds very much like a cache. [7:28] And the key question with materialized views,  just like with caches, is how to maintain that [7:33] materialization. What happens if the data in  the tables change? And so this is what is called [7:39] materialized view maintenance. And ideally we want  this maintenance to be incremental. We want it to [7:45] be so that we don't have to re-execute the query  that is materialized every time the underlying [7:50] data changes. For example, if some story has  100,000 votes, and then one vote more comes in, [7:57] we'd like to not have to count to 100,001, and  instead just take the current count of 100,000, [8:03] and have the system just realized it can  just increment that count by one rather [8:07] than recomputing the query from scratch. We also  have this questions when it comes to materialized [8:12] view maintenance of whether we maintain  on write, so proactively when a new change [8:17] happens to the underlying data. Or whether we do  it sort of lazily and on demand on later reads. [8:25] And this brings us to the next  part of the thesis title, which is [8:29] how we maintain these kinds of materializations.  And the title gives us a clue: dataflow-based. [8:35] Now, dataflow has a lot of meanings  in different parts of academia, [8:41] and in particular within Computer Science,  but essentially it is a systems architecture. [8:45] And in this talk, we're going to be talking about  dataflow as having data move to compute. The idea [8:51] here is that instead of code fetching data  from tables, you're going to have the tables [8:57] send data towards the compute. You can think of  this a little bit like push-based computation. [9:03] And these data changes are going to propagate  through a graph of operators. These are [9:10] relational operators like joins, aggregations,  and filters. And you can sort of think of them [9:15] as whatever operators you might use in SQL. This  might sound a little hard to get your head around, [9:22] and so I'm going to give an example  shortly of how this works out in practice. [9:26] And then each edge of the dataflow is going to  indicate a data dependency. So for example, a join [9:32] is going to depend on all of the inputs of that  join. An aggregation is going to depend on the [9:37] table, or the data, that it is aggregating over.  And then the messages that flow over the edges [9:43] of the dataflow are going to be deltas. A delta  here is a full row, it has columns just like the [9:51] rows that are coming out of the operator above,  but they also have a "sign" which is either [9:56] positive or negative. If a delta has a positive  sign, you can think of it as an addition, an [10:03] additional query row result to what came before.  If it's a negative, it's a revocation of some [10:09] result that was previously issued. You can think  of it as sort of "add this" or "remove this". And [10:17] in particular, we're going to be looking at this  whole dataflow model in the context of "Noria", [10:21] which is an eventually consistent materialized  view system that is built using dataflow. [10:28] So let's take a look at a concrete example of  how dataflow can be used to maintain materialized [10:33] views. So here on the left I show you a query,  and on the right, I show you the dataflow that [10:38] Noria constructs for that query. So the query  here creates a materialized view by the name [10:44] of StoryWithVC. VC for vote count here. And then  defines a query that does a join between stories [10:50] and votes on the story id. And then counts the  number of votes for each story. You can see it [10:56] groups by stories.id. And if you squint at  this, you can see how some of the parts from [11:02] the relational query appear in the dataflow graph.  For example, there's an aggregation here, a count, [11:08] indicated by the sum operator in the dataflow.  And it groups by the stories id, which we know [11:15] from the join clause is the same as the story_id  column of votes. Similarly, there's a join between [11:22] stories and votes, and that is represented  by the join operator in the dataflow graph. [11:26] You might notice here that these seem a little out  of order: the join is between stories and votes, [11:30] not stories and the vote count operator. And what  we see here is the effect of query optimization. [11:35] Noria has decided that it's going to do the  aggregation first for optimization purposes. [11:42] And now the question becomes: what if the  application wants to read from this view at [11:45] the bottom, StoryWithVC. Well what happens  is that the application issues a query [11:51] over that view. Which might look  something like this. So in this case [11:54] SELECT * FROM StoryWithVC WHERE id = ?. Where  question mark here means some parameter that [12:02] is input by the application at runtime. And that  parameter is essentially going to be a lookup key [12:08] into the materialized view to get out just  the subset that the application cares about. [12:16] Now imagine that some data changes in the  underlying tables. So imagine for example [12:21] that a new vote comes in for some story. What  Noria is going to do is take that input change [12:29] and inject it into the dataflow at the votes table  node in the dataflow graph. And then it's going to [12:37] stream that as an update through the  dataflow graph, along each of the edges, [12:42] down the dataflow, all the way down to  any materialized views we might have. [12:46] And the idea here is that the update here is  modified by the operators it passes through. [12:51] So for example, when the vote — let's say it's  for story 7 — passes through the count operator, [12:57] the count is going to replace, or convert, that  +1 vote into a negative of the old count — a [13:04] negative delta — and a positive delta of the  new count. So in this case, it'll be a -7, [13:09] the story id, 42, the old count, and a positive  7, 43 for the new count. You can think of this [13:16] message as communicating: "It used to be that  the count for story 7 was 42. Forget that, [13:21] it is now 43". These two deltas then flow along to  the join, and the join needs to convert that again [13:29] into some kind of delta that can be applied  to the downstream materialized view. [13:34] From the query, we know that the materialized view  has a bunch of additional columns that come from [13:38] the stories table. And so the join performs a join  by doing lookups into the stories table and then [13:44] stitching together the output deltas so that  they have the additional columns. Those deltas [13:50] then flow through the dataflow again, down to the  StoryWithVC materialized view where they update [13:56] that view in place. And now subsequent reads  from that materialized view are going to see [14:01] the updated result. The result that  has the count of 43 rather than 42. [14:08] Now that we've walked through dataflow-based  materialized views at a relatively high level, [14:13] let's start to look at the last  part — or first part — of the title: [14:16] partial state. And partial state is  the core contribution of this thesis, [14:22] and what we'll be looking at  for the rest of this talk. [14:24] So partial state can be summarized as  "learning to forget". The observation here [14:30] is that the chances are most entries in any given  view are not accessed. Old and unpopular stories [14:38] are just sitting there wasting memory; if no one  ever reads story 7, why are we storing its result? [14:44] Furthermore, why are we even computing, and  keeping the results up to date, if no one reads [14:48] them? Similarly, if we don't have the memory to  keep all the results for every story in there, [14:54] we might need to choose to only keep some of them.  Say, only the popular ones that speed up reads the [15:00] most. We want to trade off in favor of the most  popular and most frequently accessed things. [15:06] But traditional materialized views don't really  give us this opportunity. As we saw before, you [15:11] just have a query that gets all of the results,  and then you have to query over that view. [15:16] And what we need is some way to evict  old entries from materialized views, [15:21] and only add new ones on demand. Which brings me  to three of the main contributions of this thesis. [15:27] The first is the notion of missing  state in materialized views: [15:31] the ability to mark some state as not being there,  and not expending memory on it. The second is the [15:37] mechanism of upqueries, which allow populating  missing state using dataflow. And finally, [15:44] an implementation and evaluation of partial state  in the Noria dataflow materialized view system. [15:52] So in order to get at partial state,  one thing we first need to figure out [15:56] is this separation between the definition  of the view and the query over that view. [16:02] Because unfortunately this doesn't give us  quite enough information to make the view [16:06] partial. We don't know what key to use as the  basis for deciding whether a subset of the view [16:11] should be made missing or not. We don't know the  query key that the application is going to use. [16:17] And therefore, in partial state and  in partially materialized views, [16:20] what we're going to do is introduce the query  parameter into the view definition itself. So [16:26] instead of writing what you currently see  on screen, and having them be separate, [16:30] we can have a single view definition that also  includes this clause of where the story id equals [16:35] question mark. And then have the question mark  be a parameter for the view. And we're going [16:40] to use this key to determine if a given result is  present or missing. And then when the application [16:47] wants to query over this view, it's going to  execute that view without any additional query, [16:52] and just supply the parameters that are  identified by the question mark placeholders. [16:59] And what's neat about this is that when an  application wants to execute a given view, [17:03] let's say for story 7, that  gets sent as a request to Noria. [17:08] Which then receives it and looks up into its  materialized view, looks for the index for [17:12] story 7, and it might find that that entry is  missing, indicated here by a hollow green box. [17:19] Now when this happens, some mechanism needs  to be in place in order to fill that result, [17:24] that subset of the view, so that we can respond  to the application. The way we do this is using an [17:30] "upquery". And an upquery is, as the name implies,  a query that goes up the dataflow graph. In this [17:36] case, immediately to the join operator. And you  can think of an upquery as a request for a summary [17:42] of all the relevant past deltas to be  retransmitted through the dataflow. You can think [17:48] of it sort of as the downstream saying: "tell me  about 7 again, because I forgot all about it". [17:55] Now, the join in this case is stateless — it  doesn't have a way to send such a summary — and so [18:02] in order to support this, upqueries  can also recurse. In this case, [18:06] the join might choose to forward this upquery to  one of its ancestors, which might be stateful. [18:11] In this case, let's say it decides to forward  that upquery to the count operator on the right. [18:18] And you can think of this as sort of asking:  "can you tell me about 7 so that I can tell the [18:23] join — the downstream — about 7?". Now, a quick  aside here: we've only talked so far about state [18:29] in tables and in views. But there is other state  too. Remember how I mentioned that the count takes [18:35] a +1 vote and turns it into a negative for the  old count and a positive for the new count? Well, [18:40] in order to do that, it needs to  remember that the current count was 42. [18:44] And the way it does this is it also keeps its  own little materialized view internally. It's [18:49] a materialized view of its past output.  And so this might actually be state that [18:55] is present in the dataflow, and that  can be used to satisfy these upqueries. [18:59] In this case, it might be that story 7 is known  in that materialized state, and so we don't need [19:05] another upquery to recurse all the way back  to the individual votes in the votes table. [19:10] When the aggregation responds to the upquery,  it sends that upquery just directly through the [19:16] existing dataflow. And this is a key point: there  is no need for special operators or different [19:21] forward or backwards query processing in this  design. Instead, the response that gets sent [19:27] through the dataflow is just a single message  that holds the current state of the source for [19:32] the requested key. And it's processed just like  any other dataflow update. When that response [19:39] arrives at the join, the join does the same thing  it would have done for any other update: looks [19:44] up into stories, patches together the output, and  then forwards that back to the materialized view. [19:49] And that materialized view, when it receives this  upquery response, takes that and uses it to fill [19:55] in the hollow box because this represents the  answer for 7. At this point we now have enough [20:02] state to respond to the application query  for 7, so we can just send the response back. [20:07] What's nice about this is that  the state has now been populated. [20:11] So if we now get later queries for the same  value, 7, we can just serve them directly from [20:18] the same materialized view because that state  is no longer missing. What all of this enables, [20:25] and the sort of key feature of partial state,  is that at some point later, if story 7 falls [20:30] out of favor — becomes old — we can evict that  entry. In fact, we can evict any state we want [20:36] internally in the system related to that key.  So for example, we might choose a year later [20:42] to evict story 7 from both the aggregation  state and also from the materialized view. [20:47] And this lets us save memory that can then be used  to materialize other results that are popular. [20:54] I mentioned also that we might waste compute  to keep materialized view results up to date [20:59] that are no longer being accessed. And eviction  and missing state allow us to work around this. [21:03] Imagine that after evicting 7, some change  happens to the story table where say the title of [21:09] story 7 changes. This is going to introduce  a delta in the dataflow graph that changes [21:15] the story. And when that arrives at the join,  and the join does a lookup into the state of [21:21] the aggregation to figure out what the count  is, it's going to encounter missing state. [21:26] And when it does, we can safely evict that…  Sorry, we can safely discard that update to [21:34] the story. The reasons for this are a little  subtle, and the thesis goes into more detail, [21:38] but essentially if you observe missing state for a  given key in a sibling in the graph, it generally [21:44] also means that that state is missing downstream.  And therefore there is nothing to update — there [21:49] is no state for 7 downstream — and so don't need  to update it and can discard this update entirely. [21:55] At this point I've talked enough about  materialized views and dataflow and partial state [21:59] that I think it's time for an intermission  where we talk a little bit about related work. [22:03] And there's been a lot of related work in  this general area. And the first of course is [22:07] materialized view maintenance. So, materialized  views, in general, have traditionally been used [22:14] for a slightly different workload than what I'm  going for with this thesis work. In general, [22:20] materialized views are used for something  like an analyst that comes in to check [22:25] results occasionally. And it would be too slow  that complex query the analyst wants to run [22:31] those few times they come in. And therefore, over  time, we're just going to keep this materialized [22:36] view. And then when the analyst comes in they  can just open the view and it opens immediately. [22:40] And so the focus has more been on the maintenance  than the reads because the reads are infrequent. [22:46] Think of it as there is a high frequency and  volume of writes, and so we want to make sure that [22:51] the maintenance is as efficient as possible. But  it's okay if the read has to sort of do a bunch [22:57] of work when the analyst sits down as long as it's  much less than it would be to execute the query. [23:04] These systems also generally have  little or no support for on-demand [23:08] queries. The queries are often compiled  into a program, or something similar, [23:12] and it's not really built for the kind of dynamic  query setting that we often see in something [23:18] like a web application. And for similar reasons  these systems rarely have support for eviction, [23:25] because it's not really needed; the analyst's  query is what it is. That is the view. [23:29] And there's no subset of the view that  is more important than the others. [23:35] Another area of related work is automated caching  systems. We've seen a number of these come out of [23:41] both industry and academia. Unfortunately,  especially the ones out of industry, [23:45] these tend to be very tailored for a particular  purpose. They're not really general purpose things [23:52] that you can plug and play into your  own application. What usually happens [23:55] is some large company has a particular  caching problem, they build a solution [23:58] that works for them, but you can't just spin  that up in your Ruby on Rails application. [24:05] These systems also often only support  invalidation, and not incremental updates. [24:10] They just focus on evicting things from cache  that are related, and not updating them in place, [24:15] which has the downside that now you might miss  a lot and have to go the backend a lot more [24:20] than is necessary. Furthermore, these systems are  often limited to specific database interactions: [24:26] they require that you go through a framework or  an ORM. As opposed to what we're targeting here, [24:31] which is sort of general-purpose SQL where  you just write SQL queries, you write views, [24:35] and they just work similar to  parameterized prepared statements in SQL. [24:42] And finally, there's been a lot of work  on dataflow and stream processing systems. [24:46] And these systems are also usually focused on  write performance, similar to materialized views, [24:51] where there is a data pipeline and you want  to perform all these ongoing computations [24:56] over that data pipeline. These tend  to focus on strong consistency, [25:01] which usually comes at the cost of read latency.  The reads generally have to coordinated with the [25:07] data pipeline somehow; often the reads even  have to go through the write processing path in [25:13] order to give consistent results. Whereas with  Noria we can leverage the eventual consistency [25:19] to give much faster results by leveraging the  fact that the results are allowed to be stale. [25:26] These dataflow systems, and stream processing  systems, also tend to have limited support for [25:31] on-demand compute and eviction. Here, too,  you sort of set up some queries, and they [25:36] run for a while, and you can't evict partial  results from a given materialized view. If you [25:42] wanted to you would sort of have to terminate  the process, or something along those lines. [25:48] So now that I've talked to you for a bit  about what the system does, you might wonder: [25:52] well, are we done? Is everything you told me  everything I need to know, and I can just go [25:56] run this in my application. And unfortunately  that's not the case. Although if it were, [26:00] this thesis wouldn't be very valuable, and so  I'm kind of glad that there are more challenges. [26:05] Because it turns out that, in practice, things  are hard. In particular, we need to ensure that [26:10] data changes to the tables take effect exactly  once. For example, if you do an insert to the base [26:17] table, well that insert has to happen. It can't  just… The row you inserted can't just vanish. And [26:23] if the database applied the insert multiple times  so the table now contains that row multiple times, [26:28] that would also not be great. Now, this might  strike you as weird if you come from a traditional [26:33] database world, because the only way that could  really happen is through a bug. The database sort [26:38] of goes through and looks at indicies and scans  tables and such, and would only encounter any [26:42] given row once. But in this model, it's a little  bit harder. And the reason is because, well, [26:48] it's two-fold. First, upqueries are summaries of  past state. Things like all the state in the past, [26:55] all the deltas in the past, for story 7. But  upqueries can happen concurrently to updates that [27:00] flow through the dataflow graph. And those updates  might be for the same state. Imagine, for example, [27:05] there's an upquery for story 7 at the same time  as story 7 is being updated. We need to ensure [27:10] that these don't conflict with each other and  end up violating this sort of exactly once rule. [27:17] Similarly, we want the ability to discard updates  early to not maintain state unnecessarily. [27:23] However, if we discard things erroneously  — if we encounter missing state but there [27:28] is downstream state that actually depended  on the update that's flowing through the [27:33] graph — then that'd be really unfortunate:  that result would be permanently stale. [27:37] There are a lot of hazards that can cause these  kinds of problems, and the thesis goes through a [27:41] fair number of them, but in this talk I'm going  to focus on one just because of limited time. [27:48] The one we're going to focus on is incongruent  join evictions. And if you don't know what these [27:53] are, it's not that weird because it's  a term that I made up. But hopefully [27:57] you're going to see in a little bit  why I think the name makes sense. [28:01] So let's start then with "what is an incongruent  join?". What I'm showing you here is another query [28:06] and dataflow side by side. It's a different query  and dataflow from the ones we looked at before [28:12] even though they look kind of similar. Here,  we have a stories table like before, and then [28:16] we have a users table. And the idea is that the  stories table has an author id column. And in [28:22] order to display a given story we probably want  the author's name rather than just their user id. [28:28] And so we store a separate table that has the user  ids and various information about that user, such [28:34] as their name. And so in this StoriesWithAuthor  view we're doing a join between stories and users [28:41] which ends up combining the results such that the  output rows actually contain the author's name [28:46] pulled from the users table. What makes  this join incongruent is the fact that [28:51] query key is different from the join  key. The query key here is the story id, [28:57] whereas the join key is  the author id of the story. [29:00] That's what we end up looking into users  with. Now, in general this is not a problem. [29:06] Let's first work through the sort of correct  case of what happens when an upquery occurs. [29:11] Well let's say that someone queries this view as  well for story 7. An upquery goes to the join, [29:15] the join is stateless, it forwards to the  stories table. The stories tables looks up [29:20] the state for 7 and sends back a message along  the dataflow saying "here's story 7, the author [29:25] is 42". It might include some other columns  too, but let's just consider these for now. [29:30] The join then dutifully does the lookup into  the users table, and wants to look for the [29:34] user information for user 42. And let's  say it finds the name for user 42 is Lena. [29:41] Well in that case it takes that information,  it stitches it together with the update that [29:46] flowed in as a response to the upquery, and  then it forwards the response downstream to [29:51] the materialized view to fill the hollow box  — the missing state. So this includes 7, the [29:56] various columns from the stories table, and the  author name it fetched from users. So far so good. [30:03] But now recall this figure. Where if we encounter  missing state in a sibling, we end up just [30:08] discarding the update, assuming that there's no  state downstream that we might have to update. [30:13] This ends up causing us a problem in this  particular case. Let's consider what happens [30:18] if the author changes. So this would be  represented in the dataflow as two deltas: [30:23] one that removes the story with the old author,  and one that adds the story with the new author. [30:31] These two deltas flow down  through the dataflow graph, [30:34] and when they arrive at the join, the join  then needs to do the lookups as before. [30:40] So it first does a lookup for 42. It again finds  the state for Lena, and populates the author name [30:46] column for that in preparation for sending it to  the materialized view. And then it needs to do [30:51] a lookup for author 43 to do the same for the  positive delta. However, what if that lookup [30:57] misses? So the lookup misses in the users table,  and now we don't know what the author's name is! [31:04] Now, you might wonder: how could this happen if  users is a table? And there are two answers I can [31:09] give you to that. One is you could imagine that  the users table is, say, only partially stored in [31:15] memory, and 43 would have to be fetched from disk.  Now, Noria doesn't actually support this — keeping [31:20] materialized state in memory versus disk — but in  practice there are other ways that this can occur. [31:26] For example, here I've given you a simplified  view where users is just a table. But you could [31:31] imagine that users is actually a view in and of  itself, and has some large dataflow upstream. [31:36] And then there could totally be results in users  that are missing. Regardless of how this happens, [31:42] the join still now has a problem: it needs  to complete the processing of that update, [31:47] but it doesn't have the state that's required  to do so. So what do we do? We can't produce [31:52] the needed update. We cannot forward just the  negative, and just sort of discard the positive, [31:58] because if we did, the downstream materialized  view would now have no rows for story 7. And any [32:04] subsequent query for story 7 would get no results,  which is obviously not correct. We also can't just [32:10] drop the update altogether. Because if we did,  any subsequent read for 7 would now see the [32:16] old author name rather than the new one. And  this would also be a problem. So what do we do? [32:22] Well, your first instinct might be that we can  just fill the missing state. Right? We just have [32:28] the users table do an upquery — or something —  fill in the state for 43, and then everything is [32:33] great. And while this seems like an attractive  solution, in practice it doesn't work so well. [32:38] Because we can't… we would have to hold up the  dataflow at the join until that upquery finishes. [32:46] And that might potentially take a long time.  Remember, the users table might be a view that has [32:50] huge dataflow above it. And satisfying  that upquery might take forever. Well, [32:55] at least a very long time. And during that  time, the join can't process any more updates. [33:01] And we're sort of stuck just holding up  the dataflow — not processing more writes. [33:05] In fact, it turns out this is even worse. There  are cases — I won't go through them here — where [33:10] this might end up in deadlock. Where the join  can't process more updates until the upquery [33:15] finishes, but the upquery cannot finish until the  join processes more updates. And now we're stuck. [33:22] You might think: well, can the join just  process later updates to avoid this problem. [33:27] But we can't process them out  of order because there might be [33:30] later updates that depend on this one. And so  we need to finish processing this one first. [33:36] Okay, so that's not a viable solution. What do we  do instead? Well, partial state actually gives us [33:42] the mechanism to solve this problem, and that  is evictions. It's true that we don't know what [33:47] the author for story 7 now is, but we can just  communicate that downstream with an eviction. We [33:54] can evict story 7 from the downstream materialized  view. And now, all the application has… or, [34:01] all Noria has to do, is when a later query comes  in for 7, that's going to fill the required state [34:08] through the normal upquery flow, which we  already showed worked just fine. And it [34:14] turns out the system can actually detect when you  have incongruent joins, and only send evictions [34:20] in those cases where it's necessary. It  doesn't have to do it for every join. [34:26] So might wonder now: does all of this work?  Like, this seems like there's a bunch of [34:30] mechanism internally, does it end up just  killing performance — is this even worthwhile? [34:35] In order to evaluate that, we need a realistic  test subject. And for this thesis I chose [34:41] Lobste.rs, which is a Hacker News-like  news aggregator. Users submit stories, [34:47] the users can vote for and comment on those  stories, look at top lists of the most popular [34:52] stories, that kind of stuff. And I chose Lobste.rs  for two reasons. One is that it is open-source, [34:59] which allows us to see the queries that are  issued for different page requests. And the second [35:06] is that the data statistics for Lobste.rs  are available. This is stuff like how many [35:12] requests come in per second in general, how are  those requests distributed across different pages, [35:17] what users what stories are most popular and most  active. And ultimately all of this data allowed me [35:24] to build a workload generator for Lobste.rs  that can synthesize Loste.rs-like requests. [35:31] And the reason why we want a generator  here is so that we can change the load [35:35] of the system artificially, and  see whether the system keeps up. [35:40] The generator also has a pluggable backend so  that we can choose to run it against MySQL, [35:46] against Noria, and just see how they perform. It  also lets us bypass Ruby on Rails so that we can [35:52] benchmark the true backend performance rather  than the language that's serving the frontend. [36:01] So lets' first look at how MySQL does.  This is MySQL running on Amazon EC2. [36:07] It's a 16-core instance. And this is showing the  throughput that the workload generator can get to [36:13] before the system falls over. Before all  the cores on the machine are saturated [36:17] and the latency starts to spike. So  this gets to about 400 pages per second. [36:23] And this is across all the different  page types — it generates a sort of [36:27] mix of page requests. Now I want to point out  that this is already with a denormalized schema. [36:33] The Lobste.rs developers have done a decent amount  of work on their queries to make sure that things [36:38] like the vote count — or their equivalent of it  that they call story "hotness"­ — is actually a [36:43] column of the stories table. So they don't  generally have to join and aggregations in [36:47] their queries. Although their update paths in the  application have to do a lot of work to make sure [36:52] those values are kept up to date. If you don't  include this kind of manual denormalization [36:58] the throughput for MySQL… it can't even keep  up with a single page request per second. [37:06] Now let's contrast that with running Noria without  partial state. Noria without partial state already [37:12] does significantly better — this is about an order  of magnitude improvement. And this shows you the [37:16] power of materialized view. Especially in a case  like Lobste.rs where there's a majority of reads. [37:22] All those reads don't have to do joins; they're  essentially all just key/value lookups. Here, [37:28] however, we run into another bottleneck: we're  not CPU-bound, we're memory-bound. When Noria [37:36] without partial gets to about 4500 pages per  second, it runs out of the 128GB of memory [37:43] on this machine. And in fact, it gets  a little bit worse than that because [37:46] the memory use tends to increase over time,  and so if you ran the benchmark for longer [37:52] it might not even keep up with this load  for longer periods of time. And this is [37:57] already with some amount of optimizations within  Noria to make sure we only materialize requested [38:03] values. So if no one ever asks for a particular  query, we don't materialize results for it. [38:10] And now let's look at what happens if we run  Noria with partial state. It does significantly [38:16] better — this is about 67% over Noria without  partial, and about 18x MySQL. And here, there's [38:24] actually a little bit of room to grow. This  benchmark falls over not because of saturating [38:30] all the cores, and not because of memory. It falls  over because of processing upqueries. It turns [38:36] out that there's a particularly update-heavy  path through the dataflow that currently [38:40] bottlenecks Noria. And this might be somewhere  where additional optimizations could help. [38:46] And we can see how Noria with partial state gets  to this higher performance number by looking at [38:52] the memory use. So here I'm showing you the  memory use in GB for Noria without partial [38:57] and Noria with partial. At the capacity just  below where Noria without partial falls over. [39:04] You see that Noria without  partial uses over 100GB of memory, [39:08] and Noria with partial state  uses only a third of that. [39:13] And you might say well, Jon, forget about  MySQL, no one does that in practice. If I [39:17] implemented caching myself, is Noria really going  to keep up with that? Is Noria really a serious [39:22] sort of competitor for that? And this  is a really hard question to answer [39:27] because it depends on the implementation,  it depends on the application in question, [39:31] it depends on the workload. And so instead what  I did is construct a benchmark that is sort of [39:37] an idealized caching setup. This is one where  there are no evictions, there are no misses, [39:42] almost all requests are reads, almost all  requests turn into a single key lookup. [39:48] And there's only a single query in these  benchmarks, so this is not all of Lobste.rs, [39:51] but instead just the stories and vote count query  I showed you in the very beginning. And I ran this [39:58] against Redis, which is a popular key value story  that's often used to back things like caches. [40:05] And in this idealized workload, Redis gets to  just under a million requests per second. Which [40:12] might sound pretty good. However, Redis is  single threaded — it can only run on one core — [40:17] and so if we really wanted to compare these,  we have to assume that someone implemented [40:22] like perfect scalability across cores for Redis,  and so here's what I'm going to show you is 16 [40:27] times that number. This is not… the number on  the right here is not a real benchmark number, [40:32] it is just 16 times the number on the left. Think  of it as a theoretical maximum for what you could [40:38] get against Redis here. And then I ran the same  benchmark against Noria. Now before I show you [40:45] the result, remember that Noria provides  SQL, automatic maintenance of this cache, [40:51] and it doesn't have these requirements  of everything has to be implemented [40:55] in the application logic. Instead, Noria does it  automatically for you. And Noria here gets pretty [41:01] close to this theoretical maximum for Redis. Noria  uses as many cores as it needs to satisfy reads. [41:07] It handles all the eviction and caching  updating for you. And yet it gets within [41:12] a factor for two of what you could get with a  theoretical Redis deployment on this machine. [41:18] Now, I've been talking for  a while, and so I'm going to [41:22] start to wrap things up now. And I want to  start first by talking a little bit about [41:27] future work on this. Because Noria is  neither perfect nor complete. There [41:33] are a number of things that are missing  both from Noria without partial state, [41:36] and partial state itself. For example, there is no  support currently for things like range queries, [41:42] cursors, and time-windowed operators that might  be useful for applications, and is somewhere where [41:47] there's room for innovation both within Noria's  dataflow but also within partial state. It'd also [41:53] be really nice if there was a way to integrate  Noria with an upstream database. So imagine that [41:58] the tables in Noria were not stored in Noria  itself, but was stored in Postgres or MySQL [42:04] or some other source of truth database that the  user or application developer is already running. [42:11] Similarly, there's an attractive prospect here of…  because Noria uses dataflow to manage all of the [42:17] updates to materialized views, there's no real  reason it has to stop at the materialized views. [42:22] Imagine that the user, or the application  developer, also has client applications running on [42:28] devices that users are holding. Well it might be  that those are showing subsets of views that are [42:33] on the server. And you could imagine that the  deltas are allowed to flow all the way to the [42:37] end-user device and update the views there in  place. This is sort of reactive programming, [42:43] or reactive applications, that are becoming a  bit of a trend in web application development. [42:48] And finally, fault tolerance is something  that Noria has a somewhat weak story for. [42:53] But partial state might be able to help here.  The idea would be that if a given node goes away, [42:58] what we can do is just make the state that  that node held as missing, and then have the [43:03] partial state and upqueries mechanisms take  the role of trying to repopulate that state. [43:11] Now, before I end, I want to acknowledge the  influence of a couple of people on this work. [43:16] And I want to start off with the committee.  Robert and Frans have — over the years — just been [43:23] continuously asking and trying to make me build  a better story for Noria. And for partial. [43:30] And I think this is one of the reasons why the  work is where it is today. I think initially I had [43:34] these sort of hazy ideas for something that might  be cool, and I think the two of them have really [43:39] helped hone the story, hone the argument, for why  this is useful and what the work should focus on. [43:44] And this project wouldn't be anything like what it  is today without their invaluable input. Malte as [43:51] well was a post-doc in my group during many of the  years of Noria's development, and without Malte [43:57] Noria wouldn't have SQL. It wouldn't have query  optimization. It would essentially just be a [44:01] dataflow system. And his contributions have been  invaluable and without him this work would not be [44:07] in its current state. I'm also very glad that  I have Sam on my committee so that I can draw [44:12] from some of his database experience. Which is  something that he has a lot more of us than us [44:17] mere systems people. I also want to thank the  people of the parallel and distributed operating [44:23] systems group at MIT. The people there have  just been giving me… they just have this endless [44:32] curiosity and insight and support that  I think has made me the researcher I am [44:37] today. And I don't think I would be here without  having them surround me throughout the years. [44:44] I also want to thank my family —  my parents and step-parents — who [44:47] have always been encouraging me to pursue my  interests no matter how geeky they might be. [44:53] And I think they've sort of been nudging me along  all the way until I got where I am today — where [44:58] I'm now giving a very geeky presentation  — and I think they'd be happy with that. [45:03] I also want to thank my girlfriend Talia. I  am amazed that she's tolerated me just locking [45:09] myself in my room for hours on end working on  this work, on the evaluation, on the thesis, [45:15] on this presentation. I am so grateful and  happy that I have her, and… I love you. [45:24] To conclude: my thesis enables  materialized views to be used as [45:29] caches. It does so by allowing state  to be missing from materializations, [45:34] and using upqueries to populate missing state on  demand. The resulting system provides automated [45:40] caching for SQL queries, and reduces the  need for complex, ad hoc caching logic. [45:45] Thank you all for listening, and please  ask any questions you might have.