{"id":1622,"date":"2013-11-02T18:07:00","date_gmt":"2013-11-02T18:07:00","guid":{"rendered":"http:\/\/www.syslog.cl.cam.ac.uk\/?p=1622"},"modified":"2013-11-02T22:15:15","modified_gmt":"2013-11-02T22:15:15","slug":"live-blog-from-ladis-2013","status":"publish","type":"post","link":"https:\/\/www.syslog.cl.cam.ac.uk\/2013\/11\/02\/live-blog-from-ladis-2013\/","title":{"rendered":"Live-blog from LADIS 2013"},"content":{"rendered":"<p>Several of us are attending the <a href=\"http:\/\/ladisworkshop.org\/\">LADIS workshop<\/a>\u00c2\u00a0in advance of <a href=\"http:\/\/sigops.org\/sosp\/sosp13\/\">SOSP<\/a> in Nemacolin Woodlands in colourful Pennsylvania today and tomorrow. We will cover some of the papers and keynotes in our live blog below.<\/p>\n<p><!--more--><\/p>\n<h2>Proforma<\/h2>\n<ul>\n<li>7th edition of the workshop, moving between conferences (theory and systems)<\/li>\n<li>Chairs alternate between the US and Europe<\/li>\n<li>36 submissions, 12 papers accepted<\/li>\n<\/ul>\n<p><em>icg: Ionel Gog<\/em><\/p>\n<p><em>ms: Malte Schwarzkopf<\/em><\/p>\n<p>&nbsp;<\/p>\n<h2>Keynote I: SDN for the Public Cloud: Windows Azure<\/h2>\n<p><em>Albert Greenberg, Microsoft<\/em><\/p>\n<ul>\n<li>Work of 100 engineers of several years<\/li>\n<li>Greenberg joined Windows Azure (WA) in 2010, and they worked on 'this' (SDN deployment, presumably) since then<\/li>\n<li>WA is Microsoft's SaaS offering; they are also moving their own sites and properties to it now<\/li>\n<li>Fairly rapid growth, fully geographically distributed<\/li>\n<li>IaaS offering: simply run your own Hyper-V VM (\u00c3\u00a0 la EC2)\n<ul>\n<li>What does IaaS require from the network?<\/li>\n<li>Would like to be able to bring private network to \"the cloud\"<\/li>\n<li>Need VPNs to extend into WA, which requires multiple secure overlay networks inside WA<\/li>\n<li>Microsoft's technology for this is called NVGRE (Network Virtualization ...)<\/li>\n<li>Challenge: scale; key insight: keep hardware oblivious of policy and implementation, and do this in software (... just the usual SDN sales pitch)<\/li>\n<\/ul>\n<\/li>\n<li><em>Q: What are the customers' requirements on ingress and egress latency in such a virtualized environment?<\/em><\/li>\n<li><em>A: Predictability is much more important to enterprise customers than ultimate performance.<\/em><\/li>\n<li>Goal: effect mapping of customer IP addresses (CAs) to provider addresses (PAs) of hosts running the VMs<\/li>\n<li>'Seperate the interface to specify a VNet from the interface to plumb mappings to programmable software switches in the host machines using the network controller'<\/li>\n<li><em>Q: Do you just supply connectivity or do you also offer a notion of QoS here?<\/em><\/li>\n<li><em>A: VMs are offered as parts of profiles, which include CPU, memory, network speed allocations. But currently only NIC speed is customer-selectable.<\/em><\/li>\n<li>Secure connectivity for intra-tennant VMs is done via packet encapsulation.<\/li>\n<li>However, to bridge a customer network in the WA data center with the rest of the customer's enterprise network, it needs a VPN gateway.\n<ul>\n<li>Key insight is that re-programmable L3 forwarding policies permit setting this up easily<\/li>\n<\/ul>\n<\/li>\n<li>VNet is a very successful product: &gt;40% of WA VMs use it now<\/li>\n<li><em>Q: How do you scale the controller to support many VNets?<\/em><\/li>\n<li><em>A: Refactored it a couple of times. Relies on directory service, which is already scalable. But at the bottom of this, they always have something like Paxos running.<\/em><\/li>\n<li><em>Q: &lt;missed&gt;<\/em><\/li>\n<li><em>Q: What state do the VMSwitches (host software switches) hold?<\/em><\/li>\n<li><em>A: Maintaining state is key to making all of this work, but cannot have state for all VMs in every VMSwitch. So have a learning\/caching approach backed by a directory service.<\/em><\/li>\n<li>When running most cloud services, load-balancing is another feature in demand<\/li>\n<li>Again, can solve this using SDN with an all-software approach: simply expose a virtual IP and remap the requests coming in to dedicated IPs\n<ul>\n<li>The load balancer runs in several VMs, and establishes stateless tunnels to the actual request handling VMs<\/li>\n<li>Responses are sent directly, rather than tunnelled through the LB VM<\/li>\n<\/ul>\n<\/li>\n<li>SDN is also useful for many other purposes: ACLs, billing, metering, etc.<\/li>\n<li>Obviously, the VMSwitch is kinda important in this whole scheme. It's a bit\/lot like an OpenFlow switch.<\/li>\n<li>Big bet on SDN seems to pay off for Microsoft.<\/li>\n<li>SDN is a great abstraction, but the implementation is not easy!\n<ul>\n<li>'Typed tables' in VMSwitch help -- they allow interactions between multiple tables for any flow (e.g. to get a load-balanced VNet, using multiple features)<\/li>\n<li>40G Ethernet makes it challenging to keep up with line rate, and the sheer scale of systems makes it necessary to build distributed\/partitioned controllers.<\/li>\n<li>Need to make VMSwitches request policies, rather than pushing a globally synchronous view; \"eventing\" supports this (looks like some kind of synch-RPC-callback scheme to me)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>-- (ms)<\/p>\n<h2>Session 1: Caching<\/h2>\n<h3>Cooperative client caching strategies for social and web applications.<\/h3>\n<p><em>Stavros Nikolaou, Robbert van Renesse and Nicolas Schiper (Cornell University).<\/em><\/p>\n<p>There are some advantages to trying to use client devices to cache popular web content. In this work, they look at what benefits leveraging social link information can have for such client caching. The clients are connected by a peer-to-peer network. The centralized backend service interacts with requesting clients, but only provides meta-data: it tells the client where to fetch an object from a client cache. The setting considered here is a social network one, where each content item is owned (uploaded) by an individual user.<\/p>\n<p>Different caching strategies are conceivable. In an opportunistic approach (widely used in CDNs and previous work, e.g. Maygh at EuroSys 2013), clients cache the objects that they request and maintains a cache managed under LRU policy. Another possible strategy is a proactive one, which aims to maximize client hit rate. This approach is based on the client relationship graph, where there is a higher probability of accessing content owned by neighbours than of random content. In this situation, it is beneficial if any first client in a community to obtain an object proceeds to then push it out to all of the clients in the same community. Yet, a third approach is a minimalistic one, where the goal is to minimize load on the back end service and thus to cache as many diverse objects as possible. This works like opportunistic caching, but allows a client only to cache an object if it is not already cached somewhere else.<\/p>\n<p>In their evaluation, they show that the local (with-community) client hit ratio for the proactive strategy is consistently the highest (60-70%), as one would expect. However, the opportunistic approach also achiaves around 50%, while the minimal approach achieves little over 10%. For the global hit ratio, there is no difference as soon as the number of clients is large. In terms of balancing the per-client bandwidth, the proactive approach is worst and the opportunistic one is best.<\/p>\n<p><em>Q: Evaluation is a little bit like cheating. You're assuming that the social graph is a good model\u00c2\u00a0for the client graph. However, this is only a good model if the users are Twitter\/Facebook users. Have you looked at other traffic patterns?<\/em><\/p>\n<p><em> A: No we haven't considered that yet. We don't have the data.<\/em><\/p>\n<p><em>Allen Clement: You said that the overheads were about 5KB\/s, but how much useful information is the client getting?<\/em><br \/>\n<em> A: It's interesting but we haven't studied that.<\/em><\/p>\n<p><em>Malte Schwarzkopf: You make the assumption that improving hit rate is always a good thing. However, that's not necesarily the case. I have a lot of friends that I am connected and they live in the US. That's not good because the system will end up caching data in the US and the transatlantic link is expensive. Have you considered if the social network is a good approximation?<\/em><br \/>\n<em> A: We would like to measure to what extent social-proximity is related to geo-location proximity.<\/em><\/p>\n<p>-- (icg)<\/p>\n<p>&nbsp;<\/p>\n<h3>Cache Provisioning for Interactive NLP Services.<\/h3>\n<p><i>Jaimie Kelley, Christopher Stewart (Ohio State), Yuxiong He and Sameh Elnikety (Microsoft Research).<\/i><\/p>\n<p>- Data is growing too fast to keep in main memory.<br \/>\n- Quality-Aware Cache management - for NLP evit data that will cause the least quality<br \/>\nloss.<br \/>\n- Quality loss - ideal vs real: the differences in the replies given by the NLP system.<br \/>\n- challenges: synonyms.<br \/>\n- Quality loss in NLP services - used Lucene with Redis and DiskSim.<br \/>\n- For the ideal NLP services the same processing without any latency bound.<br \/>\n- Query trace obtained from Google Trends.<br \/>\n- Tested quality loss on LRU.<br \/>\n- Tested quality with limit content. (i.e. remove some of the data) - quality loss rises<br \/>\nsharply when documents are removed from the data set.<br \/>\n- NLP services can remove some redundant content with little quality loss.<\/p>\n<p><em>Q: Synonym seemed to save you. Is there a relationship between the length of the queries and the reply?<\/em><br \/>\n<em> A: Yes, there's a strong connection.<\/em><\/p>\n<p><em>Q: Do you the temporal meta-data about the objects to evict them?<\/em><br \/>\n<em> A: You can do that with limited content methos. The method we used is very similar to that. You can also eliminate whatever happens to X after a timestamp.<\/em><\/p>\n<p>-- (icg)<\/p>\n<p>&nbsp;<\/p>\n<h3>GD-Wheel: A Cost-Aware Replacement Policy for Key-Value Stores.<\/h3>\n<p><i>Conglong Li and Alan L. Cox (Rice University)<\/i><\/p>\n<p>- Key-value stores support two basic operations: get and set.<br \/>\n- When full, KV use LRU for eviction.<br \/>\n- RUBIS: latency 240ms (for 4% of the request), 60-95ms (for 70% of the request).<br \/>\n- GD-Wheel - taking the cost into consideration in order to improve read access latency.<br \/>\n- Uses YCSB benchmark to evaluate.<br \/>\n- GD-Wheel - implementation of the GreedyDual algorithm<br \/>\n- Hierarchical cost wheel - a data structure used to reduce the time complexity of GreedyDual.<br \/>\n- Key-value pairs with different costs are stored in different queues.<br \/>\n- Implemented GD-Wheel in Memcached<br \/>\n- Cost input added to set requests. The cost is an abstract concept that doesn't have a unit.<br \/>\nIt could be time duration.<br \/>\n- FB workfloads: - most keys are no more than 32 bytes.<br \/>\n- values: median size 135 bytes, mean size = 954 bytes.<\/p>\n<p><em>Q: It may be worthwile to do a comparison to M3C? from CMU.<\/em><br \/>\n<em> A: MemC3 is a variation of Memcached. Our work is focused on reducing latency.<\/em><\/p>\n<p><em>Q: You've mentioned GreedyDual. Have you compared against it?<\/em><br \/>\n<em> A: GreedyRedual is a cost aware published &lt;missed rest&gt;<\/em><\/p>\n<p>-- (icg)<\/p>\n<p>&nbsp;<\/p>\n<h3>Towards a storage system for connected homes.<\/h3>\n<p><i>Trinabh Gupta, Amar Phanishayee, Jaeyeon Jung and Ratul Mahajan (Microsoft Research).<\/i><\/p>\n<p>- What are the right storage abstractions for home applications?<br \/>\n- Deployed\/existing applications (e.g. PreHeat, DigiSwitch, Energy Data Analytics,<br \/>\nDiginal Neighborhood Watch).<br \/>\n- Example of requirements: filtering based on tags, range queries over time,<br \/>\nsupport app specific location policies, confidentiality of data.<br \/>\n- BOLT - supports time-series data and provides privacy<br \/>\n- Design of Bolt<br \/>\n- stream based abstraction. (e.g. create new stream of data, read\/write to\/from stream of<br \/>\ndata). Specifies the location of the stream, where the stream should be located.<br \/>\n- append(tag, value). Followed by get(tag) to retrieve data.<br \/>\n- Approach: 1) specialized index on top of data<br \/>\n2) separate index from data<br \/>\n- Privacy of data stored on untrusted servers: 1) hash, encrypt the data<br \/>\n2) decentralize access<br \/>\n- Support app specific storage policies: 1) segment stream, location per segment<br \/>\n- Inefficiens: - overhead of storing a hash for each datavalue =&gt; group many datavalues into one check, hash and encrypt each chunking.<br \/>\n- reliance on metadata server: use quorom on metadata reads.<br \/>\n- Found that: - prefetching data (chunks) improves read throughput up to 3x for temporal range queries.<br \/>\n- bol segments are scalable. Around 3.6% overhead.<\/p>\n<p><em>Q: Broken devices may create bad data. Is there any way of retracting the data? The opposite of an append.<\/em><br \/>\n<em> A: We don't have any method of going back to delete some value.<\/em><\/p>\n<p><em>Q: Did you look at he IO behaviour of the streams you're generating? You had different ways at looking at the data. The index points to various places in your stream. If you're using the stream then your IO will be bad.<\/em><br \/>\n<em> A: It depends on how many tag you have.<\/em><br \/>\n<em> Q: Did you look at it?<\/em><br \/>\n<em> A: No.<\/em><\/p>\n<p>-- (icg)<\/p>\n<p>&nbsp;<\/p>\n<p>Smart home technology is becoming increasingly common, but there is no good storage solution for these sorts of distributed and connected applications yet. Various sensors will store current and historic data, and applications may need to run various types of queries and analyses over this. Indeed, multiple smart homes may collaborate by sharing sensor data, and data should be available even when sensors are offline.<\/p>\n<p>Cloud storage would be an obvious candidate here, but has trust issues. Various platforms exist (e.g. HomeOS), but do not support some of the desired features (range queries or tags); existing database systems are \"inefficient to run over untrusted storage servers\" (?); stream processing systems also do not fit the bill in terms of data retention. Bolt (their system) supports all of the needed features including secure and efficient sharing.<\/p>\n<p>Bolt's API is centred around streams with certain declarative properties (e.g. location, security, data size) and has operations corresponding to certain events (e.g. append()), and analysis features (get(), range queries, tag-based filtering etc.). The data storage layout is an append-only log, augmented with an index. Index entries are timestamped, and time-based range queries act on the index before retrieving the data from the log (assume that bulk data is much larger than the index). Integrity of the stored data is ensured by storing hashes of the data with each record entry in the index, and data values are encrypted. The index can be stored on untrusted service, too. Finally, Bolt offers declarative control for applications over the data storage locations.<\/p>\n<p>The problem of the index growing large due to the hashes is solved by batching multiple data values before hashing. There is also a metadata server (unclear to me where that lives), but Bolt tries to relax its reliance on its availability.<\/p>\n<p>Evaluation: consider storing data locally, on Azure (while trusted) or on Azure while untrusted. Prefetching improves throughput by 3x; the encryption overhead is negligible as the remote I\/O operations dominate. The segmentation of Bolt streams is beneficial and queries scale well.<\/p>\n<p><em>Q: Seems like you have a partitioned, distributed temporal database. How do you deal with clock skews between different homes, for example?<\/em><br \/>\n<em>A: Currently assume synchronized clocks.<\/em><\/p>\n<p><em>Q: How portable is this to other cloud providers?<\/em><br \/>\n<em>A: Very portable, only needs put\/get API.<\/em><\/p>\n<p><em>Q: Can the system support retraction of data?<\/em><br \/>\n<em>A: Yep, a delete() operation exists, although this is only at the granularity of a complete stream.<\/em><\/p>\n<p>-- (ms)<\/p>\n<p>&nbsp;<\/p>\n<h3>Tachyon: Memory Throughput I\/O for Cluster Computing Frameworks.<\/h3>\n<p><i>Haoyuan Li, Ali Ghodsi, Matei Zaharia, Eric Baldeschwieler, Scott Shenker and Ion Stoica (UC Berkeley).<\/i><\/p>\n<p>- RAM throughput increasing exponentially.<br \/>\n- Disk throughput slowly increasing.<br \/>\n- Problems: Data shared across jobs must be written on disk and disk scans are slow for read.<br \/>\n- One copy of data in memory (Fast).<br \/>\n- Upon failure, re-compute data using lineage (Fault tolerance).<br \/>\n- Challenges: lineage API, recomputation cost, recomputation resource allocation.<br \/>\n- Lineage - Binary program, configuration, input files, output files.<\/p>\n<p>-- (icg)<\/p>\n<p>&nbsp;<\/p>\n<p>In-memory computing is really important. RAM throughput is increasing exponentially (capacity doesn't, though), while disks don't scale at the same rate. Hence, memory locality is important (?). Many existing big data frameworks (e.g. Spark, Shark) already use in-memory data to accelerate computations, but they have to store the data to disk in between jobs. Tachyon fixes this problem by offering a caching distributed file system, and uses lineage information to recompute missing data and offer fault tolerance.<\/p>\n<p>Of course, this only works with some caveats: it requires immutable data, deterministic computation, the working set must fit into memory. Challenges: lineage API, ensuring that recomputation cost does not become ridiculous, balancing recomputation with other work going on in the cluster. Tachyon workers simply have a RAM-disk that they expose to jobs, so these can read at memory speed directly. For the lineage tracking to work, they need to keep track of binary, configuration, inputs\/outputs and dependencies (this is a lot like CIEL's data flow mechanisms).<\/p>\n<p>What is the re-computation cost? They reduce it by asynchronously checkpointing to the durable storage system every now and then. Some tweaks to checkpointing (latest result first, etc.) can improve performance.<\/p>\n<p>Evaluation: as one would expect, memory read\/write is much faster than disk.<\/p>\n<p><em>Q: Tachyon using RAM obviously takes this RAM away from working sets of running jobs. Have you thought about this trade-off?<\/em><br \/>\n<em>A: Not really. But RAM capacity is scaling exponentially, while core count is not, so memory will be plentiful in the future.<\/em><\/p>\n<p><em>Q: Is there anything that HDFS is still better on than Tachyon?<\/em><br \/>\n<em>A: It's more stable!<\/em><br \/>\n<em>Q: Here's an example: if you have a JOIN between two large relations that produces a tiny output, it's much better to pay the cost of replicating that than to re-run the jobs based on lineage information.<\/em><\/p>\n<p><em>Q: Have you tried increasing the number of dirty pages in the buffer cache to get a fairer comparison against HDFS?<\/em><br \/>\n<em>A: No, not tuned that parameter.<\/em><\/p>\n<p>-- (ms)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Several of us are attending the LADIS workshop\u00c2\u00a0in advance of SOSP in Nemacolin Woodlands in colourful Pennsylvania today and tomorrow. We will cover some of the papers and keynotes in our live blog below.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[30],"tags":[92,79],"_links":{"self":[{"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/posts\/1622"}],"collection":[{"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/comments?post=1622"}],"version-history":[{"count":10,"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/posts\/1622\/revisions"}],"predecessor-version":[{"id":1632,"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/posts\/1622\/revisions\/1632"}],"wp:attachment":[{"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/media?parent=1622"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/categories?post=1622"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.syslog.cl.cam.ac.uk\/wp-json\/wp\/v2\/tags?post=1622"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}