Share
Embed
Architecting Immediacy: The Design of a High-Performance Portable Wrangling Engine
Talk at Strata San Jose, 2016, joint with Seshadri Mahalingam
Joe Hellerstein
March 31, 2016
Transcript
91 slides
-
Architecting Immediacy Joe Hellerstein and Seshadri Mahalingam The Design of
a High-Performance Portable Wrangling Engine PHOTON -
Wrangling and Immediacy Technical Challenges Architectural Context JavaScript and its
Discontents Photon: A Clean Slate Design Outline 1 2 3 4 5 -
Turn of the Century Data Transformation - Schemas and annotations
- Box-and-arrow programming - Batch execution -
Research Roots: Potter’s Wheel 2001 + Real data, sampled on
the fly + Menu-driven transforms + Immediate execution and feedback [Raman & Hellerstein, VLDB01] -
Research Roots: Open Source Data Wrangler, 2011 – Browser-sized data
sets + Predictive Transformation + Immediate feedback on multiple choices [Kandel, Heer & Hellerstein, CHI 11] -
2016: Data Wrangling and Immediacy DEMO Grown from research roots.
+ Deeper and broader Predictive Transformation + Sample-to-Scale with Intelligent Execution + Interactive Visual Profiling Multi-faceted immediacy! -
The Value of Immediacy Immediate, step-by-step feedback during data transformation
Understand options Confirm intent Assess progress -
The Value of Immediacy Miller ’68, Card ’91,
Nielsen ‘93 Elapsed Time (secs) 1 2 3 4 5 6 7 8 9 10 0 User attention User flow “Instantaneous” Batch processing is in conflict with these goals! -
Wrangling and Immediacy Technical Challenges Architectural Context JavaScript and its
Discontents Photon: A Clean Slate Design Outline 1 2 3 4 5 -
Technical Challenges Performance: Stay in the Flow Miller ’68,
Card ’91, Nielsen ‘93 Elapsed Time (secs) 1 2 3 4 5 6 7 8 9 10 0 User attention User flow Instantaneous -
Technical Challenges Scale Scaling the Unknown P NO PRECOMPUTING NO
SCHEMA NO INDEXES NO SUMMARIES -
The Dirty Details of Dirty Data 1 2 3 4
5 Technical Challenges Ambiguous Schemas 6 Heavy String Processing Ambiguous Types Noise & Exceptions Limited Filtering Rich Transforms -
This is the New World of Data Wrangling Stay in
the Flow Scale the Unknown Expect the Unexpected -
Wrangling and Immediacy Technical Challenges Architectural Context JavaScript and its
Discontents Photon: A Clean Slate Design Outline 1 2 3 4 5 -
Flexible Deployments Trifacta Wrangler App On Premises DSL Compiler Intelligent
Execution Hosted DSL Compiler Intelligent Execution AWS DSL Compiler Intelligent Execution -
Wrangling and Immediacy Technical Challenges Architectural Context JavaScript and its
Discontents Photon: A Clean Slate Design Outline 1 2 3 4 5 -
Why a JS Wrangling Engine? Stanford Wrangler team was deep
in JS JS runs in the browser Dynamically typed JS is the way people-centric data apps are built today! Easy to prototype & add new features Continued to attract top JS talent …and on the desktop too JS deals well with ambiguous types and structures found while in wrangling -
Why a JS Wrangling Engine? Stanford Wrangler team was deep
in JS JS runs in the browser Dynamically typed JS is the way people-centric data apps are built today! Easy to prototype & add new features Continued to attract top JS talent …and on the desktop too JS deals well with ambiguous types and structures found while in wrangling But does it perform? Does it scale? -
Jeff Heer’s Datavore Prototype Datavore can complete queries over million-element
data tables at interactive (sub-100ms) rates. in-memory column-oriented database -
Hard to extend, performantly You will have to modify the
guts of the engine to add new aggregate operators add new logic to the inner loop of the query processor (for both dense and sparse queries) -
Type ambiguity Inconsistencies with strongly typed execution engines Core engine
slows down switch (typeof inputValue) { case 'string': return inputValue; case 'number': return inputValue + ''; -
Code Generation is deceptively easy Function bodies can be analyzed:
Function.prototype.toString() Functions can be generated: new Function(functionBody) Inlining function calls brought ~15-20% speed up Difficult to maintain & debug. Modest wins don’t justify the maintenance cost. -
JavaScript runtime: fast, but not easily tamed Difficult to exploit
parallelism via multi-core processors Garbage-collected language pain points: Value copies, object allocation and garbage collection Small inputs easily blow up memory usage -
Escape from JS: A Study of Alternatives DSL COMPILER INTELLIGENT
EXECUTION Interaction via roundtrip to a server User-interface Server -
A Clean Slate Go for performance? Maybe write our own
C++/LLVM- based query engine! Java? Not viable in the browser Portability a primary concern Browser + Single-node Server But … portability? LLVM -
Surprise: What can’t a browser do these days? Native code
execution frameworks Chrome’s Portable Native Client (PNaCl) asm.js Upcoming: WebAssembly Run compiled C and C++ code LLVM No JIT overhead Dense data representations No unpredictable garbage collection -
Portable Native Client (PNaCl) LLVM-based, cross-compilation style toolchain https://developer.chrome.com/native-client We
went with Chrome’s PNaCl Plenty of ports for popular vendor libraries (webports) -
Wrangling and Immediacy Technical Challenges Architectural Context JavaScript and its
Discontents Photon: A Clean Slate Design Outline 1 2 3 4 5 -
Performance Requirements Low memory footprint % of dataset size Immediate
Feedback < 1 second response time -
Engineering Process Start by establishing “Speed of Light” Step 1
Then add features for functionality and extensibility Step 2 Compare to speed of light; compromise judiciously. Step 3 Iterate, back to step 1 Step 4 -
Inspiration & Reading ➔ Serializable & human-readable description of data
flow ➔ Partitioned (sharded) data flow ➔ Strategies for complex transformations ➔ Data locality maximization Impala HyPer Tupleware Spark -
PHOTON Architecture DSL COMPILER INTELLIGENT EXECUTION Router Cache Engine Execution
Nodes Scalar & Aggregate Functions -
In-memory data layout Table Metadata Row Metadata Column 0 Column
1 Column 2 Chunk 0 Chunk 1 Column Metadata Chunk 0 Chunk 1 Chunk 0 Chunk 1 Column Metadata Column Metadata -
In-memory data layout Row Batch Chunk 0 Row Metadata Row
Batch http://arrow.apache.org/ Chunk 0 Chunk 0 Chunk 1 Row Metadata Chunk 1 Chunk 1 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T0 T1 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer Row Batch 0 Row Batch 1 Row Batch 2 T0 T1 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer Row Batch 2 T1 Row Batch 1 T0 Row Batch 0 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer Row Batch 2 T1 Row Batch 1 T0 Row Batch 0 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer Row Batch 2 T1 Row Batch 1 T0 Row Batch 0 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer Row Batch 2 T1 Row Batch 1 T0 Row Batch 0 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer Row Batch 2 Row Batch 0 T0 T1 Row Batch 3 Row Batch 1 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T1 Row Batch 2 T0 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T1 Row Batch 2 T0 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T1 Row Batch 2 T0 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T1 Row Batch 2 T0 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T1 Row Batch 2 T0 Row Batch 3 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T0 T1 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T0 T1 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T0 T1 Row Batch 3 -
Execution Thread Pool Source Filter Map Agg Map Sink Producer
Pipe Pipe Pipe Barrier Consumer T0 Row Batch 3 T1 -
Development Toolchain CMake Handles cross-compilation toolchain for PNaCl & Desktop
Google C++ libraries Modern C++11/14 std::unique_ptr & std::shared_ptr simplify memory management Standard threading library New container classes LLVM Clang libraries ASAN Address Sanitizer TSAN Thread Sanitizer Useful for catching large classes of bugs googletest googlemock benchmark -
Experimental Setup 86 MB dataset ~250k rows MacBook Pro (mid
2014) Experimental Setup Use Cases -
Design Requirements What is your desired workload? Low memory footprint
% of dataset size Immediate Feedback < 1 second response time -
➔ The right engine for the right job ➔ Photon
is yet another payoff of (DSL + compiler + intelligent execution) ➔ Alongside Spark and Hadoop ➔ Photon specialized for UX: immediacy and scale ➔ Start by establishing speed-of-light ➔ Design to ensure it remains achievable as you grow ➔ Memory management with portability ➔ LLVM + toolchain form a powerful portability platform. ➔ Explicit memory management is critical for immediacy, even more so in-browser Lessons learned -
Part of Trifacta’s Intelligent Execution Alongside the distributed processing of
Spark and Hadoop Portability Browser, Desktop, Single-Node Server Lean usage of client memory Efficient and predictable. Photon performance preserves user flow No loss of context Immediate data wrangling Fluid UX with predictions, profiles, previews