deletions | additions
diff --git a/bibliography/biblio.bib b/bibliography/biblio.bib
index b68063a..f49e11f 100644
--- a/bibliography/biblio.bib
+++ b/bibliography/biblio.bib
...
publisher = {USENIX Association},
address = {Berkeley, CA, USA},
}
@MISC{graph500,
key={Graph500},
title = {Graph 500},
year = {2012},
month = {July},
howpublished={\url{http://www.graph500.org/}}
}
diff --git a/rmd/paper.Rmd b/rmd/paper.Rmd
index f70f130..55f2e0b 100644
--- a/rmd/paper.Rmd
+++ b/rmd/paper.Rmd
...
Another way to reduce contention on a shared data structure is to synchronize hierarchically: first with a couple immediate neighbors, then possibly with more clusters of neighbors, and finally with the data structure itself. This is known as combining \cite{flatCombining,yew:combining-trees,funnels} in the multi-processing literature, and could be applied to contended records in our model just as well as to shared data structures where it originated.
# Evaluation {#eval}
To demonstrate the efficacy of leveraging commutative operations in transactions, we built a simple prototype key-value store, modeled after Redis, that supports complex data types for records, each with their own set of
available operations.
The transaction protocol employs
fairly standard two-phase
commit design, commit, and
uses two-phase
locking with retries to guarantee isolation. To support transactions with arbitrary data structure operations, each operation is split into two steps: *stage* and *apply*. During transaction execution, each operation's *stage* method attempts to acquire the necessary lock and may return a value *as if the operation has completed* (e.g. an "increment" speculatively returns the incremented value). When the transaction is prepared to commit, *apply* is called on each staged operation to actually mutate the underlying data structure. This allows operations to easily locking, more details can be
un-staged if the transaction fails to acquire all found in the
necessary locks, without requiring rollbacks. appendix (\autoref{apx:protocol}).
Commutativity comes into play in the locking scheme. Using the algorithms from \cite{Kulkarni:PLDI11} and our commutativity specifications, we design an abstract lock for each record type. Our `SortedSet`, for instance, has an `add` mode which allows all insertion operations to commute, but disallows operations like `contains` or `size`.
As a baseline, we implement a standard reader/writer locking scheme that allows all read-only operations to execute concurrently, but enforces that only one transaction may modify a record at a time.
...
**Microbenchmark: Set operations.** We first evaluate performance with a simple workload consisting of a raw mix of `Set` operations randomly distributed over 10,000 keys. We use both a uniform random distribution as well as a skewed Zipfian distribution with a coefficient of 0.6. In \autoref{stress_tput}, we see that commutative transactions perform strictly better, showing the most pronounced benefit over the more update-heavy, skewed workload.
```{r throughput, fig.cap="Throughput
on of social network workload
(Retwis). (Retwis) with 4000 users. Leveraging commutativity prevents performance from falling over even when
a posts spread virally
across the network (repost-heavy).\\label{tput}"}
d <- data(db("
select * from tapir where
generator_time is not null and total_time is not null
...
cc_scales(title='Concurrency\ncontrol:')
```
**Case study: Retwis.**
To understand performance of more typical of web workloads, we implemented a version of *Retwis*, a simplified Twitter clone designed originally for Redis. We use data structures such as sets to track each user's followers and posts, and keep a materialized up-to-date timeline for each user (represented as a sorted set). On top of Retwis's basic functionality, we also add a "repost" option that works like Twitter's "retweet". We simulate a realistic workload using a synthetic graph with power-law degree distribution and clients that randomly select between Retwis transactions including "add follower", "new post", and "repost", executing them as fast as they can. More about this workload is in
\autoref{apx:retwis}. the appendix (\autoref{apx:retwis}).
\autoref{tput} shows the results of this simulation. When most of the traffic is content consumption (reading timelines), both systems perform well enough. However, when we simulate a workload where clients repost popular posts from their timelines, we see a viral propagation effect, where a large fraction of the users get and share a post. As Twitter came to a standstill when Ellen Degeneres's Oscar selfie set a retweeting record, so too does our baseline fall over. But with commutativity, we see that performance continues to scale even under this arduous load.
# Appendix
## Transaction protocol {#apx:protocol}
Our protocol for executing transactions is fairly straightforward: two-phase commit, and uses two-phase locking with retries to guarantee isolation. We employ a number of standard optimizations, such as delaying acquiring locks for operations that don't return a value to the *prepare* step so that locks are held for as short a time as possible. However, there is one step that is non-standard in order to support complex data types where rolling back state changes would be non-trivial.
To support transactions with arbitrary data structure operations, each operation is split into two steps: *stage* and *apply*. During transaction execution, each operation's *stage* method attempts to acquire the necessary lock and may return a value *as if the operation has completed* (e.g. an "increment" speculatively returns the incremented value). When the transaction is prepared to commit, *apply* is called on each staged operation to actually mutate the underlying data structure. This allows operations to easily be un-staged if the transaction fails to acquire all the necessary locks, without requiring rollbacks.
## Retwis workload {#apx:retwis}
```{r}
df <- subset(db("select * from tapir where stat_following_counts is not null and name like '%v0.14%'"),
nclients == 32
& initusers == 4096
)
df$grp <- with(df, sprintf("%s\n%s\nmix:%s/%s,\n%s", name, ccmode, mix, alpha, gen))
histogram.facets <- function(df, measure, grp) {
d <- data.frame(x=c(),y=c(),version=c())
for (i in 1:nrow(df)) {
d <- rbind(d, df.histogram(df[i,measure], df[i,grp]))
}
return(d)
}
```
```{r followers, fig.cap="CDF of the number of followers for users generated by the Kronecker synthetic graph generator, matching the power-law degree distribution of natural graphs.\\label{followers}"}
d.follow <- histogram.facets(subset(df, initusers == 4096 & mix == 'geom_repost'), 'stat_follower_counts', 'grp')
ggplot(d.follow, aes(x=x, weight=y))+
stat_ecdf(color=c.blue)+
xlab('# followers / user (log scale)')+ylab('CDF (log scale)')+
scale_x_log10(breaks=c(1,10,100,1000))+scale_y_log10(breaks=c(0.1,0.5,1.0))+
theme_mine
```
```{r reposts, fig.cap="CDF of the number of times a post is reposted, matching traces from real workloads. Due to the power-law graph structure, if users tend to reposts popular recent posts on their timeline, it results in another power-law distribution. Note that that some posts are reposted to over a quarter of the graph (4000 total users).\\label{reposts}"}
d.repost <- histogram.facets(subset(df, initusers == 4096 & mix == 'geom_repost'), 'stat_repost_counts', 'grp')
ggplot(d.repost, aes(x=x, weight=y))+
stat_ecdf(color=c.blue)+
xlab('# reposts')+ylab('count')+
scale_x_log10(breaks=c(1,10,100,1000))+scale_y_log10(breaks=c(0.1,0.2,0.4,0.6,0.8,1.0))+
xlab('# reposts (log scale)')+ylab('CDF (log scale)')+
theme_mine
```
With our Retwis workload, rather than approximating the skew in real-world workloads with a Zipfian as many other systems do, we attempt to simulate the behavior of social networks with a realistic synthetic graph and a simple model of user behavior for posting and reposting.
For our synthetic graph, we use the Kronecker graph generator from the Graph 500 benchmark \cite{graph500}. This generator is designed to result in graphs with the same power-law degree distribution found in natural graphs. \autoref{followers} shows the cumulative distribution function (CDF) of the number of followers per user for the synthetic graph of approximately 4000 users, with an average number of followers of 16 (scale 12 with edgefactor of 16 in Graph500's terms) which we use in our performance results back in \autoref{eval}. Most users should have relatively few followers; we see that roughly 50% have fewer than 100 followers, while a very small number of users have over 1000 followers.
We use a simple model of user behavior to determine when and which posts to repost. Each time we load the most recent posts in a timeline for a random user (uniformly selected), they are sorted by the number of times they have already been reposted, and a discrete geometric distribution, skewed toward 0, is used to select the number of these to repost. This results in the "viral" propagation effect that is observed in real social networks. \autoref{reposts} shows the distribution of the number of times a post was reposted, which is again a power-law distribution. Note that a small number of posts are reposted so much that they end up on over a quarter of users' timelines.
