{"id":490217,"date":"2018-06-08T09:27:59","date_gmt":"2018-06-08T16:27:59","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=490217"},"modified":"2018-06-08T11:44:44","modified_gmt":"2018-06-08T18:44:44","slug":"microsoft-unveils-faster-key-value-store-large-state-management","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/microsoft-unveils-faster-key-value-store-large-state-management\/","title":{"rendered":"Microsoft Unveils FASTER \u2013 a key-value store for large state management"},"content":{"rendered":"<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-490247\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_BHeader_06_2018_1000x400.jpg\" alt=\"\" width=\"1000\" height=\"400\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_BHeader_06_2018_1000x400.jpg 1000w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_BHeader_06_2018_1000x400-300x120.jpg 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_BHeader_06_2018_1000x400-768x307.jpg 768w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><\/p>\n<p>At <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/sigmod2018.org\/\">SIGMOD 2018<\/a>, a team from Microsoft Research will be presenting a new embedded key-value store called FASTER, described in their paper \u201c<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/03\/faster-sigmod18.pdf\">FASTER: A Concurrent Key-Value Store with In-Place Updates<\/a>\u201d. As its name suggests, FASTER makes a major leap forward in terms of supporting fast and frequent lookups and updates of large amounts of state information \u2013 a particularly challenging problem for applications in the cloud today. For example, in scenarios such as Internet-of-Things, billions of devices report and update state such as per-device performance counters. In advertising platforms, user activity such as ad and search result clicks drive the creation and frequent update of per-user behavior models and per-ad statistics.<\/p>\n<p>Applications that maintain such state typically scale out on multiple machines for memory, severely underutilizing other resources such as storage and networking on the machine. FASTER takes a different approach; it leverages the temporal locality inherent in all these applications to control the in-memory footprint of the system and cache the frequently accessed values without maintaining any fine-grained statistics per record. FASTER is a single-node shared memory key-value store library that makes two important technical innovations:<\/p>\n<ul>\n<li>It proposes a cache-friendly and concurrent latch-free hash index designed to grow and shrink dynamically while maintaining logical pointers to records in a log.<\/li>\n<li>It proposes a new concurrent hybrid log record allocator abstraction backing the index that spans fast storage (such as cloud storage and SSD) and main memory.<br \/>\nThe FASTER hash index is an array of cache-line-sized hash buckets, each with 8-byte entries that hold hash tags and logical pointers to records that are stored separately in the hybrid log. All operations on the hash table are latch-free, using atomic compare-and-swap instructions for very high performance. Keys are not stored as part of the index structure in order to keep its memory footprint small.<\/li>\n<\/ul>\n<p>While traditional key-value stores have used log-structured record organizations, the hybrid log of FASTER seamlessly combines log-structuring with read-copy-updates (that are good for external storage) and in-place updates (that are good for in-memory performance). Specifically, the head of the hybrid log on storage uses a read-copy-update strategy for updating records, whereas the tail of the hybrid log in main memory uses in-place updates. In between these two regions lies a read-only region in memory that provides hot records a &#8220;second chance&#8221; to be quickly copied back to the tail. This record organization captures temporal locality of updates, allows records to spill to sequential storage efficiently and enables a natural clustering of hot records in memory for fast in-place updates. Maintaining this elegant design in a concurrent latch-free setting required solving new technical challenges and proposing an extended epoch-protection-based concurrent system design framework that is detailed in the paper.<\/p>\n<p>The result? FASTER can outperform even pure in-memory data structures such as the Intel TBB hash map when the working set fits in memory. Further, it outperforms today&#8217;s key-value stores and caching systems such as RocksDB and Redis by several orders-of-magnitude.<\/p>\n<p>To support failure recovery, FASTER incorporates a recovery strategy that can bring the system back to a recent consistent state at low cost, without blocking or having to create a separate &#8220;write ahead log&#8221;, a recovery mechanism used in traditional database systems. Researchers are currently working on writing a follow up paper that describes this innovation in more detail. They are also working on using the key-value store in systems at Microsoft, including within their previous research project, Trill (<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/aka.ms\/trill\">site<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/blog\/trill-moves-big-data-faster-by-orders-of-magnitude\/\">blog post<\/a>), a highly successful and widely deployed incremental stream analytics library.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>At SIGMOD 2018, a team from Microsoft Research will be presenting a new embedded key-value store called FASTER, described in their paper \u201cFASTER: A Concurrent Key-Value Store with In-Place Updates\u201d. As its name suggests, FASTER makes a major leap forward in terms of supporting fast and frequent lookups and updates of large amounts of state [&hellip;]<\/p>\n","protected":false},"author":37074,"featured_media":490250,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"categories":[194474],"tags":[],"research-area":[13563],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-490217","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-visulalization","msr-research-area-data-platform-analytics","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[957177],"related-projects":[473268],"related-events":[489563],"related-researchers":[],"msr_type":"Post","featured_image_thumbnail":"<img width=\"480\" height=\"280\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_Carosel_06_2018_480x280.jpg\" class=\"img-object-cover\" alt=\"\" decoding=\"async\" loading=\"lazy\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_Carosel_06_2018_480x280.jpg 480w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/06\/SIGMOD_DataViz_Carosel_06_2018_480x280-300x175.jpg 300w\" sizes=\"(max-width: 480px) 100vw, 480px\" \/>","byline":"","formattedDate":"June 8, 2018","formattedExcerpt":"At SIGMOD 2018, a team from Microsoft Research will be presenting a new embedded key-value store called FASTER, described in their paper \u201cFASTER: A Concurrent Key-Value Store with In-Place Updates\u201d. As its name suggests, FASTER makes a major leap forward in terms of supporting fast&hellip;","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/490217"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/37074"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=490217"}],"version-history":[{"count":4,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/490217\/revisions"}],"predecessor-version":[{"id":490277,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/490217\/revisions\/490277"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/490250"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=490217"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=490217"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=490217"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=490217"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=490217"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=490217"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=490217"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=490217"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=490217"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=490217"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=490217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}