Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Polaris: Faster Page Loads Using Fine-grained D...

Polaris: Faster Page Loads Using Fine-grained Dependency Tracking

A paper published in NSDI'16. Presented by Liang Gong in Berkeley's group meeting.

Liang Gong

April 01, 2017
Tweet

More Decks by Liang Gong

Other Decks in Research

Transcript

  1. Presented by Liang Gong 2016 Spring Polaris: Faster Page Loads

    Using Fine-grained Dependency Tracking Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. Ravi Netravali, Ameesh Goyal, James Mickens, Hari Balakrishnan To appear in NSDI’16
  2. 2 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Overview • Motivation: Reduce web page’s loading time.
  3. 3 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Overview • Motivation: Reduce web page’s loading time. • Main Approach: • Analyze the dependency graph of resources loaded by the web page.
  4. 4 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Overview • Motivation: Reduce web page’s loading time. • Main Approach: • Analyze the dependency graph of resources loaded by the web page. • Use a dynamic scheduler to aggressively fetch resources to minimize waiting.
  5. 5 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Overview • Motivation: Reduce web page’s loading time. • Main Approach: • Analyze the dependency graph of resources loaded by the web page. • Use a dynamic scheduler to aggressively fetch resources to minimize waiting. • Evaluation: decreases page load time by 34% at the median. • top 200 websites ranked by Alexa
  6. 6 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Loading a Web Page • Modern browsers halt the parsing and rendering of the page when encountering a <script> tag.
  7. 7 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Loading a Web Page • Modern browsers halt the parsing and rendering of the page when encountering a <script> tag. – The evaluation of first.js may alter the downstream HTML.
  8. 8 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Loading a Web Page • Modern browsers halt the parsing and rendering of the page when encountering a <script> tag. – The evaluation of first.js may alter the downstream HTML. – first.js may define js state used by second.js.
  9. 9 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Loading a Web Page • Modern browsers halt the parsing and rendering of the page when encountering a <script> tag. – The evaluation of first.js may alter the downstream HTML. – first.js may define js state used by second.js. – Scripts are fetched synchronously.
  10. 10 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Motivation • If first.js and second.js do not modify mutually observable state, they can be downloaded and evaluated in any order.
  11. 11 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Motivation • If first.js and second.js do not modify mutually observable state, they can be downloaded and evaluated in any order. – GL: Sometimes people may want to control the order though. – GL: sounds like data-race detection in web.
  12. 12 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Approach Overview • Server Side: track dataflow by instrumentation  construct fine-grained dependency graph. • Client Side: A dynamic scheduler uses the dependency graph to reduce load time. Scout Polaris
  13. 13 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Dependency Graph (Tree) • Traditional dependency graph: lexical dependency
  14. 14 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Dependency Graph (Tree) • Traditional dependency graph: lexical dependency • CSS blocks JS script tags • JS code may read CSS style properties • JS script tags blocks HTML parsing • JS may change the downstream HTML • JS script tags block JS script tags • Two JS scripts may have data-race • CSS blocks CSS • If two css files update the same rule, the last writer wins.
  15. 15 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. More Accurate Dependency Graph • New dependency graph: data-race dependency • Write/Read, Read/Write, Write/Write
  16. 16 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Capture Dependency Via Instrumentation • Tracking JavaScript heap dependencies – Source-level instrumentation – Proxy API provided by browsers • Tracking DOM dependencies
  17. 17 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Tracking JS Heap Dependencies • Step 1: Rewriting Global variable references are changed to fully qualified name: x = 1  window.x = 1 But you cannot redefine the window object: window = Proxy(window, handler); Solution: (function () { var alias_window = Proxy(window, handler); return function () { alias_window.x = 1; … } })();
  18. 18 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Tracking JS Heap Dependencies • Step 1: Rewriting • Step 2: Recursive Proxying • each object is tagged with an integer id • When a proxy does get-field operation: – If return value is not a proxy, wrap it with proxy. – window.x.y.z will return a proxy object.
  19. 19 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Tracking DOM Dependencies • Step 1: Rewriting document  window.document • Step 2: Recursive Proxy • Intercept and create proxy for all objects queried from DOM. • Identifies DOM nodes by their paths in the DOM tree.
  20. 20 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Tracking DOM Dependencies • Each CSS tag can also modify the DOM (the style property of the DOM elements). • <link type="text/css" rel="stylesheet" href= "…" /> • Model each of those tags as reading all of the DOM nodes that are above it in the HTML and writing those DOM nodes with new style information. • Solution: insert inline script tags before each of those CSS tags • <script> … </script> • <link type="text/css" rel="stylesheet" href= "…" />
  21. 21 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Approach Overview • Server Side: track dataflow by instrumentation  construct fine-grained dependency graph. • Client Side: A dynamic scheduler uses the dependency graph to reduce load time. Scout Polaris
  22. 22 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Scheduler on the Client Side • Identify the dynamic critical path. Request objects in an order that minimize the total loading time. • Assumption: Each object’s loading time is a constant.
  23. 23 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Evaluation • round-trip time (RTT) is the length of time it takes for a signal to be sent plus the length of time it takes for an acknowledgment of that signal to be received.
  24. 24 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Limitations • Eval is not supported. • What about closure, how to instrument closure using web proxy? • Unknown native API? • Modify the behavior of Math.random to eliminate non-determinism • For each client devise, a separate dependency graph must be generated. – Since the page loading behavior maybe client-specific – Also dynamic webpage will generate content dynamically, according to user’s cookie and the content in database. It is impossible to run everything ahead of time. • On the client-side, polaris uses XMLHttpRequests to dynamically fetch objects. To evaluate a JavaScript file, the scheduler uses the eval function. • Assume each object’s loading time is a constant. All improvements obtained are based on that assumption.
  25. 25 Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. Motivation • If first.js and second.js do not modify mutually observable state, they can be downloaded and evaluated in any order. – GL: Sometimes people may want to control the order though. – GL: sounds like data-race detection in web. – GL: if second.js depends on a relative position of a HTML node. While first.js can change the position. It will not work.