endeavour 1 00

67 %
33 %
Information about endeavour 1 00

Published on November 21, 2007

Author: Kestrel



Telegraph: Ideas & Status:  Telegraph: Ideas & Status Overview:  Overview Folks Amol Deshpande, Mohan Lakhamraju, VijayShankar Raman Rob von Behren, Steve Gribble, Matt Welsh Kris Hildrum Hellerstein, Franklin, Brewer, Papadimitriou (ITR team) Roots “Regres” think-tank Carey, Hellerstein, Stonebraker, 1998-99 CONTROL project (Online Aggregation, etc.) UC Berkeley ‘96-present Query Scrambling Franklin & Urhan, UMD Inktomi experiences Jaguar (Welsh & Culler) Telegraph Goals:  Telegraph Goals Query all the data in the world ITR: internet sources and services Endeavour: sensors Also shared-nothing DBMS done better Unify and redesign storage engines DBMS, HTTP server, cluster-based FS Reject multi-threading in favor of event-flow state machines storage manager a “query plan” over events Cluster-centric recovery scheme Today:  Today Status on storage manager Event flow and state machines Simplified transactional API Experiences with Jaguar Status Continuously adaptive dataflow Eddies & Rivers Applications to event flow: storage mgr is a dataflow plan too Open Questions State Machines:  State Machines Web servers/proxies, cache consistency HW use FSMs Order 100x-1000x more concurrent clients than threads allow One thread per concurrent HW activity FSMs for multiplexing threads on connections Thesis: apply query plan technology to state machines We understand data flow Optimization = composition of FSMs MS Research “Pipeline Server” State machine gives better cache locality (old-fashioned DB batching of I/O on chip!) A theme in the TinyOS research too Gribble I/O Core (v6!!):  Gribble I/O Core (v6!!) buffer cache (fsm) lock mngr (fsm) SN_ Hashtable (fsm) SN_ Hashtable (fsm) HT “work” queue ‘stub’ ‘stub’ thread boundary thread boundary Mohan API for Xact Recovery:  Mohan API for Xact Recovery Lock Unlock Deadlock Detect Recoveryaction Readaction Updateaction Begin Commit Abort Read Update Scan Pin Unpin Flush Commit/Abort-action Jaguar:  Jaguar Two Basic Features Rather than JNI, map certain bytecodes to inlined assembly code Do this judiciously, maintaining type safety! Pre-Serialized Objects (PSOs) Can lay down a Java object “container” over an arbitrary VM range outside Java’s heap. With these, you have everything you need Inlining and PSOs allow direct user-level access to network buffers, disk device drivers, etc. PSOs allow buffer pool to be pre-allocated, and tuples I the pool to be “pointed at” Matt Welsh Storage Manager Status:  Storage Manager Status Working! Transactions and recovery too Gribble’s hashtable indexes currently don’t talk to Mohan’s stuff Complete version and numbers for VLDB 2000, mid-February Lessons Debugger support for state machine development needed Thinking about where to multiplex and queue in a state machine is NOT EASY (but we’re learning) Jaguar isn’t quite there yet e.g. GC control But we’re getting there Need to keep Welsh and Culler aboard Query Processing Challenges:  Query Processing Challenges The world is a messy place performance varies widely over time River lessons on NOW (NowSort experience) Internet MEMS for sure! performance metadata usually unavailable or wrong no “runstats” on the web Users are unpredictable want to get early answers, “control” queries as they run Plus Mariposa/Millenium-esque issues local autonomy, costs for access, etc. ITR Example Scenario:  ITR Example Scenario “What do the French think about farm subsidies?” How would you do this on the web today? Translate query into French via BabelFish Find a French search engine, restrict domains to .fr Fetch matches and translate back to English via BabelFish Feed to a text summarizer like NetSumm Behavior Along the Way:  Behavior Along the Way Speed changes Site that was fast suddenly slows down Behavior changes Site that was returning few answers starts returning lots (“selectivity”) Failures Site won’t respond. Choose an alternate server. Ordering affects answers summarize then translate? Or vice versa? Standard Query Engine Won’t Cut It:  Standard Query Engine Won’t Cut It Can’t adapt while running need a “continuous” query optimizer need to handle midstream failover Reload, alternate sites Uses the wrong QP algorithms Can’t produce incremental results need CONTROL-based dataflow algorithms Can’t understand cost/quality tradeoffs maybe I’d settle for something cheesier if it went faster -- e.g. use an English search engine in the US QP Framework: Eddies:  QP Framework: Eddies Need an adaptive query processor respond to changes mid-stream Eddy a pipelining object router works well with ops that have frequent moments of symmetry adjusts flow adaptively objects flow in different orders visit each op once before output simple policy for routing never give out a new object if there’s a used one Avnur & Hellerstein SIGMOD 2000 Simple Eddies Learn Input Rates:  Simple Eddies Learn Input Rates Two single-table, unchanging filters one fast, one slow both have same probability of output (selectivity) most tuples visit the fast op first policy + finite queues result in back pressure slow op almost always finds a used tuple from fast op fast op rarely finds a used tuple Simple Eddies & Output Rate:  Simple Eddies & Output Rate Again, two single-table static filters one low probability of output, one high equal costs Back-pressure slightly worse than random low-probability should be favored but it is more likely to find used tuples An Aside: n-Arm Bandits:  An Aside: n-Arm Bandits A little machine learning problem: Each arm pays off differently Explore? Or Exploit? Sometimes want to randomly choose an arm Usually want to go with the best If probabilities are static, dampen exploration over time Learning Eddies:  Learning Eddies Tuple routing is basically a bandit problem which operator should I choose next? Complicated by back pressure Bandit problems + queueing theory Lottery Scheduling implementation Each operator starts with k tickets When multiple operators request a tuple, hold a “lottery”; holder of winning ticket gets it When an operator takes a tuple, it earns a ticket When an operator produces a tuple, it is charged a ticket Works well in practice for some things Problems with delayed sources & joins Kris Hildrum studying formal proofs of convergence Ticket policy needs work. Mechanism looks robust. Open Eddy Questions:  Open Eddy Questions Eddy addresses the operator ordering problem Remaining problems: operator choice (hash join or index join?) source choice, overlap, failover: Ninja? delayed sources short jobs resource mgmt (memory allocation) distributed work and parallelism Sensor (i.e. sequence) operations What changes when data-ordering matters? What are the ops for sensors? Streaming media? Objects not discretely differentiated?? Putting it together:  Putting it together Current eddy/river in C Prototypes in Java, but not state machines Probably do a rewrite in state machine format Thesis: every piece of the system is a “query plan” Apply eddies to event routing in the storage manager? To network protocol? Cross-pollination:  Cross-pollination Telegraph QP and Ninja “Paths” DB, IStore, and OceanStore students looking at adaptive storage location OceanStore orthogonal to Telegraph storage manager? But let’s combine! DB and Istore efforts apply to clusters MEMS and sensors As soon as eddy/river rewrite done, we need to look at sensor apps and ops TinyOS Good state machine lessons at the boundary Data flow between the devices?? Negotiation Eddies and pricing fits into this! I.e. we have the infrastructure for dynamic pricing and re-routing on the way.

Add a comment

Related presentations

Related pages

Kalkhoff Endeavour 14-G (2015) ab 1.999,00 ...

Bereits ab 1.999,00 € Große Shopvielfalt Testberichte & Meinungen | Jetzt Kalkhoff Endeavour 14-G (2015) Trekkingrad günstig kaufen bei idealo ...
Read more

OcCre 14005 Endeavour 1:54: Spielzeug OcCre 14005 Endeavour 1:54. Gratis Versand durch Amazon ab einem Bestellwert von 29€.
Read more

Endeavour | Krimi Serie aus UK bei

Die britische Serie Endeavour zeigt das Leben und die Arbeit des jungen Inspector ... 3,00 von 5 bei 1 Bewertungen ... Endeavour - Series 1 bei ...
Read more

Amati Schiffsmodelle Endeavour 1934 Fertigrumpf ...

ENDEAVOUR Segelyacht. Dieser neue Baukasten der Endeavour liegt von der Größe her zwischen den beiden bisherigen Bausätzen im Maßstab 1:35 und im ...
Read more

Endeavour Silver Corp Aktie | Aktienkurs | Chart | A0DJ0N

Endeavour Silver Corp Aktie im Überblick: Realtimekurs, ... 1,00 USD. Performance 1 Monat-15,39 % Performance 1 Jahr +62,69 % Details zu Endeavour Silver.
Read more

Kalkhoff Endeavour - Preisvergleich (Preis ab € 1.999,00 ...

Kalkhoff Endeavour Preisvergleich ab € 1.999,00 (01.06.2016) Tests Bewertungen Bilder Beschreibungen Sparen Sie mit!
Read more

Monstercat 019 - Endeavour (Aspire Album Mix) [1 Hour of ...

Support Monstercat 019 - Endeavour: ... [1 Hour of Electronic Music] - Duration: 1:00:24. Monstercat 795,921 views. 1:00:24 Monstercat 017 ...
Read more

Endeavour - Microsoft Store

1. The Conqueror Mashima. Endeavour. 4:00 0,99 € 2. Fragments ... Endeavour. 5:24 0,99 ...
Read more

Endeavour (TV series) - Wikipedia, the free encyclopedia

Endeavour is a British television detective drama series. It is a prequel to the long-running Inspector Morse and, like that series, is set primarily in Oxford
Read more

Kalkhoff Online Shops & Outlets - Kalkhoff Angebote ...

1.034,00 € *: abhängig vom ... Impulse Jubilee Voyager Agattu Connect Lady Pro Connect City Glider Endeavour City Classic Image Tasman Blackwood Sahel ...
Read more