{"id":245675,"date":"2012-12-20T15:00:49","date_gmt":"2012-12-20T23:00:49","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=245675"},"modified":"2016-07-20T07:32:14","modified_gmt":"2016-07-20T14:32:14","slug":"hekaton-breaks-through","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/hekaton-breaks-through\/","title":{"rendered":"Hekaton Breaks Through"},"content":{"rendered":"

By Janie Chang<\/em><\/p>\n

In an online, on-demand world, the ability to respond quickly to requests for data has become a significant challenge. Take\u00a0bwin (opens in new tab)<\/span><\/a>, for example. In order to attract and retain customers, bwin, the world\u2019s largest regulated online gaming company, must deliver consistently positive user experiences. But the company\u2019s online gaming systems were bottlenecking at about 15,000 requests per second, and adding more hardware was not solving the problem.<\/p>\n

When Microsoft\u2019s SQL Server (opens in new tab)<\/span><\/a> team offered bwin an opportunity to test a new, in-memory technology, bwin expected to see its transaction throughput double, perhaps triple. Instead, the first test increased throughput tenfold; by the end of the trial period, tests had scaled to 250,000 transactions per second. Bwin is now running this new, enhanced version of SQL Server in production.<\/p>\n

Hekaton Accelerates Transaction Throughput<\/h1>\n

Microsoft first shared information about the technology behind these results in November during the Professional Association for SQL Server Summit (opens in new tab)<\/span><\/a> (PASS Summit 2012), during which the company announced the forthcoming release of Hekaton, its new in-memory technology, developed through a collaborative effort between Microsoft Research and the SQL Server product team. Hekaton is scheduled to ship with the next major release of SQL Server. The announcement\u2019s highlight was a demonstration that showed how SQL Server with Hekaton delivered a 30x performance increase without code changes to existing applications or hardware.<\/p>\n

\u201cThere are several in-memory database systems on the market,\u201d says David Lomet (opens in new tab)<\/span><\/a>, principal researcher and manager of the Database Group (opens in new tab)<\/span><\/a> at Microsoft Research Redmond (opens in new tab)<\/span><\/a>, \u201cbut what really sets Hekaton apart is that it will be integrated into SQL Server as part of Microsoft\u2019s suite of xVelocity in-memory technologies currently available in SQL Server 2012. Customers won\u2019t need to buy and manage a separate product.\u201d<\/p>\n

Lomet is referring to a strategic decision made during the Hekaton project. Although technically challenging and more expensive to develop, it was by far more preferable from a customer-usability point of view to integrate Hekaton into SQL Server. This approach enables existing applications to run without changes to code or hardware. But integration with SQL Server was feasible only after the project team had achieved its primary goal: to design a fast, main-memory database engine that could run efficiently on machines with hundreds of cores.<\/p>\n

Taking the Optimistic Approach<\/h1>\n

Since early 2009, Paul Larson, principal researcher with the Database Group, has been part of the Hekaton main-memory database project, which owes its genesis to Cristian Diaconu, Erik Ismert, Craig Freedman, and Mike Zwilling of the SQL Server team, along with Larson.<\/p>\n

\u201cIn traditional models, the assumption is that data lives on disk and is stored on disk pages,\u201d Larson explains. \u201cThis creates a lot of overhead when you try to access records. When data lives totally in memory, we can use much, much simpler data structures. Hekaton\u2019s index data structures and storage structures are optimized on the basis that when a table is declared memory-optimized, all of its records live in memory.\u201d<\/p>\n

\n
\"Members

Members of the Hekaton team: (front row, from left) Justin Levandoski, Sudipta Sengupta, Paul Larson, and David Lomet, and (back row, from left) Mike Zwilling, Adrian Birka, and Cristian Diaconu<\/p><\/div>\n

By late fall 2009, Larson and his colleagues had come up with a design and a simple prototype for an in-memory database engine that showed huge performance improvements. They had moved away from a partitioned approach, which essentially treated a multicore processor as a distributed system, to a latch-free, also called lock-free, design that focused on removing the barriers to scalability present in current systems.<\/p>\n<\/div>\n

Latches are synchronization mechanisms designed to avoid data corruption when multiple users try to modify a data structure concurrently. Unfortunately, latching frequently creates bottlenecks for high-performance software systems running on multicore processors. By preventing high processor utilization, latching defeats the performance benefits offered by multicore hardware.<\/p>\n

\u201cLatch-free techniques, while more subtle and difficult to program, can achieve both data integrity and high performance goals,\u201d Lomet comments. \u201cLatch-free techniques update in an \u201coptimistic\u201d way, never locking records or data structures. The challenge, of course, is to do this in a way that doesn\u2019t mess things up. Latch-free techniques have been around for a while, but using them pervasively in a major system has not been done before.\u201d<\/p>\n

The Hekaton team also found that multiversion concurrency control (MVCC) proved robust in scenarios with higher workloads and higher contention. Databases designed with single-version concurrency control handle updates by overwriting data with each change. MVCC techniques handle updates by marking old data as obsolete, then adding a newer version. At any time, there could be multiple versions of the data, but only one is the latest. The big benefit is that update transactions can add new versions without interfering with concurrent read activity.<\/p>\n

Hekaton implements an entirely new, optimistic MVCC approach that enables a transaction to be processed without blocking. The paper describing this work, High-Performance Concurrency Control Mechanisms for Main-Memory Databases (opens in new tab)<\/span><\/a>\u2014<\/i>by Larson; Spyros Blanas and Jignesh M. Patel of the University of Wisconsin-Madison; Diacon;, Freedman; and Zwilling\u2014was presented in August during the 38th International Conference on Very Large Databases (opens in new tab)<\/span><\/a>.<\/p>\n

A Better B-Tree<\/h1>\n

Beyond concurrency control mechanisms, there were even more improvements to come for Hekaton that further accelerated performance.<\/p>\n

Researchers from the Database Group and the Communication and Storage Systems Group had been developing an indexing system for high-speed access to data, which they called the Bw-tree. Adhering to the \u201clatch-free\u201d philosophy, the Bw-tree delivered far better processor-cache performance than previous efforts.<\/p>\n

\u201cWe had an \u2018aha\u2019 moment,\u201d Lomet recalls, \u201cwhen we realized that a single table that maps page identifiers to page locations would enable both latch-free page updating and log-structured page storage on flash memory. The other highlight, of course, was when we got back performance results that were stunningly good.\u201d<\/p>\n

The Bw-tree team first demonstrated its work in March 2011 during TechFest 2011, Microsoft Research\u2019s annual showcase of cutting-edge projects. The Bw-tree performance results were dazzling enough to catch the interest of the SQL Server product group.<\/p>\n

\u201cWhen they learned about our performance numbers, that was when the Hekaton folks started paying serious attention to us,\u201d researcher Justin Levandoski (opens in new tab)<\/span><\/a><\/span> says. \u201cWe ran side-by-side tests of the Bw-tree against another latch-free technology they were using, which was based on \u2018skiplists.\u2019 The Bw-tree was faster by several factors. Shortly after that, we began engaging with the Hekaton team, mainly Diaconu and Zwilling.\u201d<\/p>\n

\u201cA skiplist is often the first choice for implementing an ordered index, either latch-free or latch-based, because it is perceived to be more lightweight than a full B-tree implementation\u201d, says Sudipta Sengupta (opens in new tab)<\/span><\/a><\/span>, senior researcher in the Communication and Storage Systems Group. \u201cAn important contribution of our work is in dispelling this myth and establishing that latch-free B-trees can perform way better than latch-free skiplists. The Bw-tree also performs significantly better than a well-known latch-based B-tree implementation\u2014BerkeleyDB\u2014that is widely regarded in the community for its good performance.\u201d<\/p>\n

Zwilling supplied the Bw-tree team with a workload scenario exhibiting the \u201clast-page latch\u201d problem, in which all threads continually attempt to update a single page of a B-tree index\u2014the \u201clast page.\u201d This high contention scenario causes severe performance degradation when using latch-based approaches. On this workload, the Bw-tree performed better by a factor of 24 over another, well-engineered latch-based implementation. The Hekaton team decided to go with the Bw-tree.<\/p>\n

The Bw-Tree: A B-tree for New Hardware Platforms (opens in new tab)<\/span><\/a><\/i> by Levandoski, Lomet, and Sengupta will be one of the papers presented in April during the 29th IEEE International Conference on Data Engineering (opens in new tab)<\/span><\/a>.<\/p>\n

A Close Partnership<\/h1>\n

After four years working closely with the SQL Server product group, Larson values highly the collaboration experience, as well as its outcome.<\/p>\n

\u201cThe Hekaton team within the SQL Server product group is the most talented and ambitious product team I\u2019ve ever worked with,\u201d Larson says. \u201cThe key developers have deep technical knowledge and strong technical views, which sometimes lead to rather heated but always valuable discussions.\u201d<\/p>\n

The collaboration continues. Hekaton entered its next phase during PASS Summit 2012: private previews with a small set of customers. This group will help build, test, and validate the capabilities of the solution\u2014as well as validate the decision to incorporate Hekaton technology into the core of SQL Server, so that it accelerates performance with complete transparency.<\/p>\n","protected":false},"excerpt":{"rendered":"

By Janie Chang In an online, on-demand world, the ability to respond quickly to requests for data has become a significant challenge. Take\u00a0bwin, for example. In order to attract and retain customers, bwin, the world\u2019s largest regulated online gaming company, must deliver consistently positive user experiences. But the company\u2019s online gaming systems were bottlenecking at […]<\/p>\n","protected":false},"author":39507,"featured_media":0,"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,"_classifai_error":"","footnotes":""},"categories":[194475,194463],"tags":[206765,206750,201809,206762,206759,206753,206756,197291],"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-245675","post","type-post","status-publish","format-standard","hentry","category-database-data-analytics-platforms","category-systems","tag-29th-ieee-international-conference-on-data-engineering","tag-bwin","tag-hekaton","tag-multiversion-concurrency-control","tag-mvcc","tag-pass-summit-2012","tag-professional-association-for-sql-server-summit","tag-sql-server","msr-research-area-data-platform-analytics","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[199565],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[474786],"related-projects":[],"related-events":[],"related-researchers":[],"msr_type":"Post","byline":"","formattedDate":"December 20, 2012","formattedExcerpt":"By Janie Chang In an online, on-demand world, the ability to respond quickly to requests for data has become a significant challenge. Take\u00a0bwin, for example. In order to attract and retain customers, bwin, the world\u2019s largest regulated online gaming company, must deliver consistently positive user…","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/245675"}],"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\/39507"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=245675"}],"version-history":[{"count":8,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/245675\/revisions"}],"predecessor-version":[{"id":246068,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/245675\/revisions\/246068"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=245675"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=245675"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=245675"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=245675"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=245675"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=245675"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=245675"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=245675"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=245675"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=245675"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=245675"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}