-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathall-about-eve-execute-verify-replication-for-multi-core-servers-osdi12.html
139 lines (125 loc) · 8.61 KB
/
all-about-eve-execute-verify-replication-for-multi-core-servers-osdi12.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=endge, chrome=IE8" />
<meta name="viewport" content="initial-scale=1.0, width=device-width, user-scalable=no" />
<title>All about Eve: Execute-Verify Replication for Multi-Core Servers @ OSDI'12 — Titleless Sights</title>
<!--[if lte IE 8]><script type="text/javascript" src="http://james0zan.github.io/theme/js/html5shiv.js"></script><![endif]-->
<link rel="stylesheet" type="text/css" href="http://james0zan.github.io/theme/css/skeleton.css" />
<link rel="stylesheet" type="text/css" href="http://james0zan.github.io/theme/css/theme.css" />
<link rel="shortcut icon" type="image/png" href="http://james0zan.github.io/favicon.png" />
<!--[if lte IE 8]><link rel="shortcut icon" type="image/x-icon" href="http://james0zan.github.io/favicon.ico" /><![endif]-->
<link rel="alternate" type="application/atom+xml"
title="Titleless Sights — Flux Atom"
href="http://james0zan.github.io/feeds/atom.xml" />
<style>
li {
margin: 10px 0;
}
</style>
<meta name="author" content="Mingxing Zhang" />
<meta name="keywords" content="replica, parallel, paper" />
<link rel="stylesheet" media="not print" type="text/css" href="http://james0zan.github.io/theme/css/pygments.css" />
</head>
<body>
<div id="page">
<header id="page-head">
<h1>
<a href="http://james0zan.github.io/index.html">Titleless Sights</a>
</h1>
</header>
<div id="page-body">
<article class="post" id="page-main" role="main">
<header class="post-header">
<h1>
<a rel="bookmark"
href="http://james0zan.github.io/all-about-eve-execute-verify-replication-for-multi-core-servers-osdi12.html"
title="Lien permanent vers «All about Eve: Execute-Verify Replication for Multi-Core Servers @ OSDI'12»">
All about Eve: Execute-Verify Replication for Multi-Core Servers @ OSDI'12
</a>
</h1>
<div class="meta">
<!-- includes/article_meta.html -->
On <time datetime="2013-05-02T00:00:00">Gio 02 Maggio 2013</time>
in <em><a href="http://james0zan.github.io/category/bookmark.html">Bookmark</a></em>
by <a href="http://james0zan.github.io/author/mingxing-zhang.html">Mingxing Zhang</a> <br />Tags: <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/replica.html">replica</a></span>, <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/parallel.html">parallel</a></span>, <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/paper.html">paper</a></span> </div>
</header>
<div class="post-content">
<p><em>URL:</em> <a class="reference external" href="http://dl.acm.org/citation.cfm?id=2387903">http://dl.acm.org/citation.cfm?id=2387903</a></p>
<p><a class="reference external" href="http://en.wikipedia.org/wiki/State_machine_replication">State machine replication (SMR)</a> is a powerful fault tolerance technique, it enforces replicas to deterministically process the same
sequence of requests so that they produce the same sequence of outputs.</p>
<p>But this technique doesn't suit for parallel systems, because if different servers interleave requests’ instructions in different ways, the states and outputs of correct servers may diverge even if no faults occur. As a result, most SMR systems require servers to process requests sequentially.</p>
<p>In contrast, Eve partitions requests in batches and allows different replicas to execute requests within each batch in parallel. After each batch, it speculates that whether the results of these parallel executions (i.e. the system’s important state and output at each replica) will match across enough replicas. If such a correct state/output can be identified, Eve makes those incorrect replicas issue an incremental state transfer request to other replicas (by leveraging a <a class="reference external" href="http://en.wikipedia.org/wiki/Merkle_signature_scheme">Merkle tree</a>). However, if too many replicas diverge so that the correct state/output cannot be identified, Eve guarantees safety and liveness by rolling back and sequentially and deterministically re-executing the requests.</p>
<p>Since diverges will seriously impair Eve's performance, it uses a <em>mixer</em> stage to apply
<strong>application-specific</strong> criteria to produce groups of requests that are unlikely to interfere.</p>
<p>As a side effect, Eve is especially useful in tolerating concurrency bugs. First, Eve’s
mixer reduces the likelihood of triggering latent concurrency bugs by attempting to run only unlikely-to-interfere requests in parallel; Second, Eve's execute-verify architecture allows Eve to detect and recover when concurrency causes executions to diverge.</p>
<p>In their experiments, Eve achieves a 2.6x ~ 6.5x speedup over traditional sequential execution replica and at most 4.7x speedup over the <a class="reference external" href="http://dl.acm.org/citation.cfm?id=1387601">Remus primary-backup system</a>. It also finds new concurrency bugs in H2 database.</p>
</div>
<footer class="post-footer">
<div class="meta">
<!-- includes/article_meta.html -->
On <time datetime="2013-05-02T00:00:00">Gio 02 Maggio 2013</time>
in <em><a href="http://james0zan.github.io/category/bookmark.html">Bookmark</a></em>
by <a href="http://james0zan.github.io/author/mingxing-zhang.html">Mingxing Zhang</a> <br />Tags: <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/replica.html">replica</a></span>, <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/parallel.html">parallel</a></span>, <span class="tag"><a rel="tag" href="http://james0zan.github.io/tag/paper.html">paper</a></span> </div>
</footer>
</article> <!-- /#page-main -->
<aside id="page-side">
<!-- begin includes/sidebar.html -->
<nav>
<h3>Pages</h3>
<ul>
<li><a href="http://james0zan.github.io/index.html">Home</a></li>
<li><a href="http://james0zan.github.io/category/blog.html">Blog</a></li>
<li><a href="http://james0zan.github.io/category/bookmark.html">Bookmark</a></li>
</ul>
</nav>
<nav>
<h3>Projects</h3>
<ul>
<li><a href="http://james0zan.github.io/AI.html">AI</a></li>
</ul>
</nav>
<nav>
<h3>Meta</h3>
<ul>
<li><a href="http://james0zan.github.io/archives.html">Archives</a></li>
<li><a href="http://james0zan.github.io/tags.html">Tags</a></li>
</ul>
</nav>
<nav>
<h3>Contacts</h3>
<ul>
<li><a href="mailto:[email protected]">Gmail</a></li>
<li><a href="https://github.com/james0zan">Github</a></li>
<li><a href="http://www.linkedin.com/profile/view?id=80873276">Linkedin</a></li>
</ul>
<h3>Feeds</h3>
<ul>
<li><a href="http://james0zan.github.io/feeds/atom.xml">Atom</a></li>
<li><a href="http://james0zan.github.io/feeds/blog.atom.xml">Blog Feeds</a></li>
<li><a href="http://james0zan.github.io/feeds/bookmark.atom.xml">Bookmark Feeds</a></li>
</ul>
</nav>
<!-- end includes/sidebar.html --></aside> <!-- /#page-side -->
</div> <!-- /#page-body -->
<footer id="page-foot">
<p>
Powered by <a href="http://pelican.readthedocs.org">Pelican</a>; Theme from <a href="http://blog.1flow.net/">1flow team</a>.
</p>
<p><a id="github-link" href="https://github.com/james0zan/james0zan.github.io">Fork me on Github</a></p> </footer>
</div> <!-- /#page -->
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-40495434-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script');
ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</body>
</html>