Albrecht Zimmermann
email: albrecht.zimmermann@insa-lyon.fr

Basketball predictions in the NCAAB and NBA: similarities and differences

Most work on predicting the outcome of basketball matches so far has focused on NCAAB games. Since NCAAB and professional (NBA) basketball have a number of differences, it is not clear to what degree these results can be transferred. We explore a number of different representations, training settings, and classifiers, and contrast their results on NCAAB and NBA data. We find that adjusted efficiencies work well for the NBA, that the NCAAB regular season is not ideal for training to predict its post-season, the two leagues require classifiers with different bias, and Naïve Bayes predicts the outcome of NBA playoff series well.

Introduction

Predicting the outcome of contests in organized sports can be attractive for a number of reasons such as betting on those outcomes, whether in organized sports betting or informally with colleagues and friends, or simply to stimulate conversations about who "should have won".

Due to wide-spread betting during the NCAAB playoffs (or "March Madness"), much work has been undertaken on predicting the outcome of college basketball matches. It is not clear how much of that work can be transferred easily to the NBA. Professional basketball shows several differences to college basketball:

1. Teams are typically closer in skill level, since re-cruiting and resource bases play a lesser role.

2. Teams play almost all other teams every season.

3. Teams play more games, particularly in the playoffs, where the NCAAB's "one and done" is in sharp contrast to the NBA's best-of-seven series.

To the best of our knowledge, it is not clear how those differences affect the task of learning a predictive model for the sports: the first point implies that prediction becomes harder, whereas the other two indicate that there is more and more reliable data. Most of the existing work in the field is more or less statistical in nature, with much of it developed in blog posts or web columns. Many problems that can be addressed by statistical methods also offer themselves up as Machine Learning settings, with the expected gain that the burden of specifying the particulars of the model shifts from a statistician to the algorithm. Yet so far there is relatively little such work in the ML literature.

We intend to add to the body of work on sports analytics in the ML community by building on earlier work [START_REF] Zimmermann | Predicting college basketball match outcomes using machine learning techniques: some results and lessons learned (originally in "MLSA13[END_REF], and evaluating different match representations, learning settings, and classifiers. We compare the results on NCAAB data to those on NBA data, with a particular focus on post-season predictions.

In the next section, we will discuss how to represent teams in terms of their performance statistics, followed by ways of performing prediction in Section 3. In Section 4, we discuss existing work on NCAAB and NBA match prediction. Sections 6 and 7 are given to the evaluation of different prediction settings on 1 NCAAB and NBA data, respectively, before we compare classifier behavior on those two types of data in more detail in Section 8.

Descriptive statistics for teams

In this section, we will discuss the different options for describing basketball teams via the use of game statistics that we evaluate later in the paper. We will begin by a recap of the state-of-the-art, afterwards discussing our own extensions and aggregate statistics over the course of the season.

State of the art

The most straight-forward way of describing basketball teams in such a way that success in a match can be predicted relate to scoring points -either scoring points offensively or preventing the opponent's scoring defensively. Relatively easy to measure offensive statistics include field goals made (FGM), threepoint shots made (3FGM), free throws after fouls (FT), offensive rebounds that provide an additional attempt at scoring (OR), but also turnovers that deprive a team of an opportunity to score (TO). Defensively speaking, there are defensive rebounds that end the opponent's possession and give a team control of the ball (DR), steals that have the same effect and make up part of the opponent's turnovers (STL), and blocks, which prevent the opponent from scoring (BLK). And of course, there are points per game (PPG) and points allowed per game (PAG).

The problem with these statistics is that they are all raw numbers, which limits their expressiveness. If a team collects 30 rebounds in total during a game, we cannot know whether to consider this a good result unless we know how many rebounds were there to be had in the first place. 30 of 40 is obviously a better rebound rate than 30 of 60. Similar statements can be made for field goals and free throws, which is why statistics like offensive rebound rate (ORR), turnover rate (TOR), or field goals attempted (FGA) will paint a better picture. Even in that case, however, such statistics are not normalized: 40 rebounds in a game in which both teams combined to shoot 100 times at the basket is different from 40 rebounds when there were only 80 scoring attempts. For normalization, one can calculate the number of possessions in a given game:

P ossessions = 0.96 * (F GA-OR-T O+(0.475 * F T A))
and derive teams' points scored/allowed per 100 possessions, deriving offensive and defensive efficiencies:

OE = P P G * 100 P ossessions , DE = P AG * 100 P ossessions (1)
It should be noted that the factor 0.475 is empirically estimated -when first introducing the above formulation for the NBA, Dean Oliver estimated the factor as 0.4 [START_REF] Oliver | Basketball on Paper[END_REF]. This is currently the most-used way of describing basketball teams in the NBA. When discussing complete teams or certain line-ups (five (or fewer) player groups), the phrase "points per 100 possessions" makes frequent appearance on sites such as fivethirtyeight.com, www.sbnation.com, and hardwoodparoxysm.com.

While such statistics are normalized w.r.t. the "pace" of a game, they do not take the opponent's quality into account, which can be of particular importance in the college game: a team that puts up impressive offensive statistics against (an) opponent(s) that is (are) weak defensively, should be considered less good than a team that can deliver similar statistics against better-defending opponents. For best expected performance, one should therefore normalize w.r.t. pace, opponent's level, and national average, deriving adjusted efficiencies:

AdjOE = OE * avg all teams (OE) AdjDE opponent , AdjDE = DE * avg all teams (DE) AdjOE opponent (2)
The undeniable success of those two statistics, pioneered by Ken Pomeroy [START_REF] Pomeroy | Advanced analysis of college basketball[END_REF], in identifying the strongest teams in NCAA basketball have made them the go-to descriptors for NCAA basketball teams. Dean Oliver has also singled out four statistics as being of particular relevance for a team's success, the so-called "Four Factors" (in order of importance, with their relative weight in parentheses):

Effective field goal percentage (0.4):

eF G% = F GM + 0.5 • 3F GM F GA (3)
Turnover percentage (0.25):

T O% = T O P ossessions (4)
Offensive Rebound Percentage (0.2):

OR% = OR (OR + DR Opponent ) (5)
Free throw rate (0.15):

F T R = F T A F GA (6)

Adjusted Four Factors

In an earlier work [START_REF] Zimmermann | Predicting college basketball match outcomes using machine learning techniques: some results and lessons learned (originally in "MLSA13[END_REF], we have introduced the idea of adjusting the Four Factors in the same way as efficiencies and evaluated their usefulness for predicting college basketball matches. While multi-layer perceptrons (MLP) achieved better results using the adjusted efficiencies, Naïve Bayes classifiers performed better using the adjusted Four Factors.

Averaging over the course of the season

To gain a comprehensive picture of a team's performance during the entire season, such statistics would have to be averaged over all games up to the prediction point in time. A simple average would give the same weight to matches that happened at the beginning of the season as to matches that happened the week before the prediction. Since teams' characteristics change over time -players get injured, tactics change -this is clearly undesirable. In addition, we want matches that are close in time to have approximately equal impact on the total average. In this paper, we therefore consecutively enumerate the days of a season -not the game days -and use them to weight contributions to the average. As an illustration, imagine a team that played on day 1, 3, 10, and 15 and we want to make a prediction for day 16. For TOR, for instance, we therefore average in the following way (we use superscripts to denote the day on which the statistic has been recorded): 10 + 15 • T OR 15 1 + 3 + 10 + 15 = 28

T OR avg = 1 • T OR 1 + 3 • T OR 3 + 10 • T OR
The impact of the most recent match is more than half in this case, whereas match 1 -two weeks ago -has very little impact. Enumerating game days would give the first match a quarter of the impact of the most recent one, instead.

Calculating adjusted statistics

Due to the averaging, each team's adjusted statistics are directly influenced by their opponents', and indirectly by those opponents' opponents. As an illustration, consider a schedule like the one shown in Table 1. To calculate T eam 1 's adjusted offensive efficiency after match 3, we need to know T eam 4 's adjusted defensive efficiency before the match (i.e. after match 2), which takes the form:

AdjDE 2 (T eam 4 ) = DE 1 (T eam 4 ) * avg all teams (DE) AdjOE 1 (T eam 3 ) + DE 2 (T eam 4 ) * avg all teams (DE) AdjOE 2 (T eam 2 )
We have left out the averaging weights for the sake of readability but as is obvious, we need to add equations estimating the adjusted offensive efficiency for T eam 2 and T eam 3 , and the further in the season we advance, the more teams are involved. We do not attempt to solve this set of equations analytically but instead use an iterative algorithm: 1) we use the current values of statistics of teams involved in the right-hand side of equations to calculate new values for teams in the left-hand side. 2) we update all teams' statistics and re-iterate. This is performed until values have stabilized.

Team Opponents

T eam 1 T eam 2 T eam 3 T eam 4 T eam 2 T eam 1 T eam 4 T eam 5 T eam 3 T eam 4 T eam 1 T eam 6 T eam 4 T eam 3 T eam 2 T eam 1 . . .

Table 1: Partial example schedule

In practice, we observe that this approach finds two stable solutions at some point, and flips among those two in succeeding iterations. To break this tie, we pick the solution for which the average absolute difference between AdjOE and AdjDE is smaller. Let us denote the set of all teams by T , and solutions as set of adjusted offensive and defensive efficiencies:

S i = {AdjOE i (T ), AdjDE i (T ) | ∀T ∈ T }
then our tie breaker takes the form:

arg min {S1,S2} 1 |T | ∑ T ∈T |AdjOE i (T ) -AdjDE i (T )|.
The same approach is followed when calculating the adjusted Four Factors.

Employing standard deviations

An important element of teams' performance is consistency. A team can collect an average adjusted offensive efficiency by alternating matches in which it scores much more than expected with ones in which it is virtually shut out. Especially against higherquality competition, we would expect one of the latter type of matches, and this information can therefore be relevant when trying to predict match outcomes. A straight-forward way of encoding consistency consists of adding the standard deviation of teams statistics over the course of the season.

Approaches to prediction

A wide-spread state-of-the-art way of using the derived statistics in predicting match outcomes consists of using the so-called Pythagorean Expectation, e.g.:

W in P robability = ((Adjusted) OE avg ) y ((Adjusted) OE avg ) y + ((Adjusted) DE avg ) y
to calculate each team's win probability and predicting that the team with the higher probability wins. More generally, ranking systems can by used by ranking the entire pool of teams and predicting for each match-up that the higher ranked team wins.

Many existing approaches are somewhat or even fully hand-crafted. This can be rather high-level, as in defining the transition probabilities in LRMC's Markov chain by hand (cf. Section 4), or it can go as far as Ken Pomeroy taking home court advantage into consideration by multiplying the home team's stats by 1.014. Also, especially the Pythagorean Expectation seems to be a rather simple model.

Machine Learning promises to address both of these issues: we would expect to be able to learn the relative importance of different descriptive measures, in particular if this importance changes for different numerical ranges, and to be able to learn their relationships, automatically making the model as difficult (or simple) as needed. We therefore turned to classification learners representing several different paradigms and evaluated their performance.

In a reversal of current practice, explicit prediction of match outcomes could be used to rank teams by predicting the outcome of all hypothetical pairings and ranking teams by number of predicted wins.

Concretely, we evaluate the WEKA [START_REF] Frank | Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations[END_REF] implementations of the Multi-Layer Perceptron (MLP), Random Forest (RF), and Naïve Bayes (NB) classifiers. The former two are run with default parameters, whereas for NB we activated kernel estimation.

Related Work

The use of the Pythagorean Expectation goes back to Bill James' work on baseball. It was adapted for the use in basketball prediction by numerous analysts, e.g. Daryl Morey, John Hollinger, Ken Pomeroy, and Dean Oliver. The difference between the different approaches comes down to which measures of offensive and defensive prowess are used and how the exponent is estimated. Dean Oliver also first introduced possession-based analysis formally in his book "Basketball on Paper" [START_REF] Oliver | Basketball on Paper[END_REF], although he acknowledges that having seen coaches use such analysis in practice. The same work introduced the "Four Factors".

The adjustment of efficiencies to the opponent's quality is due to Ken Pomeroy who uses them as input in his version of the Pythagorean Expectation to rank NCAAB teams and predict match outcomes. His is far from the only ranking system, however, with other analysts like Jeff Sagarin, Ken Massey or Raymond Cheung running their own web sites and giving their own predictions. Comparisons of the results of different ranking systems can for instance be found at http://masseyratings.com/cb/compare. htm or http://www.raymondcheong.com/rankings/ perf13.html. The worst accuracy for those systems is in the 62% -64% range, equivalent to predicting that the home team wins, the best ones achieve up to 74% -75%. The NCAAB itself uses the socalled Ratings Percentage Index to rank teams, a linear weighted sum of a team's winning percentage, its opponents' winning percentage, and the winning percentage of those opponents' opponents.

As an alternative approach, Kvam et al. have proposed a logistic regression/Markov chain model [START_REF] Kvam | A logistic regression/Markov chain model for NCAA basketball[END_REF]. In this method, each team is represented as a state in a Markov chain and state transitions occur if one team is considered better than its opponent. Logistic regression is used to estimate transition probability parameters from the data. The authors have proposed an updated version using Bayesian estimates [START_REF] Brown | An improved LRMC method for NCAA basketball predictions[END_REF], and recently published work in which they estimate their method's success in comparison to other ranking schemes [START_REF] Brown | Insights from the LRMC method for NCAA tournament predictions[END_REF].

In terms of NBA basketball, Loeffelholz et al. [START_REF] Bernard | Predicting NBA games using neural networks[END_REF] have trained a variety of neural networks for predicting NBA match outcomes. The highest accuracy that they report in the abstract is approximately 74%. Oh et al. [START_REF] Oh | Graphical model for basketball match simulation[END_REF] propose building graphical models from play-by-play data that can be used to simulate the flow of a match. They report on exploring counterfactuals: simulating different substitution patterns for particular matches, and observing the resulting outcomes. A similar idea is explored in [START_REF] Harish S Bhat | Learning stochastic models for basketball substitutions from play-by-play data[END_REF]: using NBA teams' substitution patterns and fiveman units' plus/minus, they combine Markov chains and ridge regression to predict the outcomes of the 2014/2015 playoff series, reporting training set accuracy of 68% (individual matches) and postseason accuracy (complete seasons) of 80%. Finally, Franks et al. have proposed exploiting the tracking data nowadays available for NBA matches to derive a new defensive statistic called "counterpoints" [START_REF] Franks | Counterpoints: Advanced defensive metrics for NBA basketball[END_REF].

Experimental setup

The goal of our experimental evaluation is to gain an understanding about which kind of information is most conducive for achieving high-quality predictions. This involves evaluating 1. different kinds of descriptive statistics,

training the classifier on all available data, or

only on a subset, and 3. using the preceding season's statistics as standin for the first game day's statistics.

We will elaborate those aspects in the following paragraphs. After having found good models, we will explore predictions in more detail in Sections 8 and draw conclusions related to the three differences described in the introduction.

Different statistics

We used WEKA's ChiSquared, GainRatio, InfoGain, and ReliefF rankers to explore the attributes described in 2, as well as season-level ones (e.g. win percentage), using the "cross-validation" option with ten folds. The results are rather consistent across rankers: the attributes shown in Table 2 are always highly ranked, as are location, and the adjusted efficiencies (adjOEff, adjDEff).

The (adjusted) Four Factors depend to a certain degree on the selected season: while effective field goal percentage (eFG%) is almost always highly ranked, offensive rebound (ORR), turnover (TOR), and free throw rates (FTR) can go from being ranked higher than field goal percentage to unranked and We encode matches with the team statistics of the two opponents, with the opponent with the lexicographically lower name coming first. In addition, matches are described by whether it is a away, home, or neutral court from the perspective of this first opponent, and by the date (name and day of the month). This could be particularly helpful in the case of NCAA basketball, where conference tournaments (in which the competition is of higher quality) occur later in the season.

Classifier evaluation and training data composition

We are using two assumptions for our experimental settings. The first is that there is a temporal aspect to basketball prediction. Using matches from later in the season (when trends may have stabilized) to predict matches from earlier could introduce a bias. We therefore do not perform a randomized cross-validation but instead always only train on data of matches that occurred before the matches to be predicted.

Second, however, we assume that it is desirable to have as fresh data as possible available for training. To achieve this, we therefore predict matches day by day, and add them afterwards to the batch of training data., for the prediction of the following day. As is known from Data Stream classification [START_REF] Gaber | A survey of classification methods in data streams[END_REF], however, data in a temporal relationship can become "stale". We therefore also evaluate whether limiting training to recent data has an effect.

Filling in first-day statistics On the first day of a season, we have necessarily no statistics for teams available yet are already faced with a prediction task. One way of addressing this consists of using the statistics the team exhibited at the end of the preceding season. Since teams change during the off-season, however -college players graduate/get drafted, NBA players get traded -the preceding season's statistics may be rather misleading. The alternative, i.e. not using the preceding season's statistics, essentially amounts to a coin flip (or more likely, predicting that the home team wins).

NCAAB predictions

The data for the experiments on ncaa basketball comes from Ken Pomeroy's page [START_REF] Pomeroy | Advanced analysis of college basketball[END_REF], and comprises the seasons 2007/2008-2012/2013. Since we cannot build a model to predict 2007/2008, we predict from 2008/2009 onwards. In earlier work [START_REF] Zimmermann | Predicting college basketball match outcomes using machine learning techniques: some results and lessons learned (originally in "MLSA13[END_REF], we have found that combining adjusted efficiencies with Four Factors did not give competitive results. Since our manner of calculating the adjustments and averaging have changed, however, we reprise our experiments with adjusted efficiencies and adjusted four factors.

In the first setting, shown in Table 3, we used only a single season's worth of data for training. This means in particular that every time a day's matches are added to the training set, the oldest day's matches are removed. Similarly to our earlier results, we find that the multi-layer perceptron performs better than Naïve Bayes, with the Random Forest classifier third. We also see that the adjusted efficiencies are superior to adjusting Four Factors, in terms of predictive accuracy. If we use all matches we have available as training data for the day to be predicted (Table 4), we can improve the results slightly. Even though the varying strength of opponents in NCAA basketball should lead to fluctuations in statistics, adding standard deviations to the description does not pay off, as Tables 5 and6 show. Similarly, we do not find any benefit to using the preceding season's statistics to fill in team statistics for their first match, an indicator that teams change too much in the off-season, and omit the results here. 7: in that setting, the classifier is trained on only the season preceding the one to be predicted. Furthermore, every time a game day is added to the training data, the oldest one is removed. In this manner, the model should always be based on the most recent information, without trends from older seasons acting in a distorting manner. We have evaluated three representations (in addition to teams' and matches' base statistics) -Adjusted Efficiencies (Ad-jEff), Adjusted Efficiencies and Four Factors (AdjEff-FF), and Adjusted Four Factors (AdjFF). The statistics of Teams on the first day of the season are not filled in.

All in all, this experiment indicates that Adjusted Efficiencies are the most effective encoding. Especially Naïve Bayes performs well on this representation (and outperforms the MLP -contrary to the results on the NCAA data). Interestingly, Random Forests recover in comparison to the MLP once representations involve the Four Factors -adjusted or not -those seem to be more useful to a tree model than the efficiencies. It is also remarkable that the order of seasons according to predictive accuracy changes -not only between classifiers but also between representations. In contrast to this, the order remained relatively stable for NCAA data. Given that the training data in this setting were limited, using more data might make a difference.

To explore this direction, and because it is not clear how to decide how many prior seasons to use for training, we keep all seasons' data for training in the setting that we show in Table 8.

In fact, MLP and RF profit from using more data, NB less so, while continuing to perform best on average. It is somewhat surprising to see a relative large negative change in its predictive accuracy for 2008/2009, AdjEff, since this is the season that was predicted with the model having the least amount of data. The impact of additional data is more pronounced for the representations that involve the Four Factors. Experiments with a single season of training data and standard deviations led to a deterioration, so we refrain from reporting them here. Instead, Table 9 shows what happens when we augment the preceding setting with standard deviations, indicating the consistency of teams' performance indicators.

The results can at best considered inconclusive but generally speaking, including standard deviations degrades predictive accuracy. At first, this is surprising, but given that team statistics are already only approximations (with adjustment and averaging potentially introducing errors), calculating standard deviations over a season (or several of them) might very well increase the effect of any errors.

Using the end-of-season statistics of the preceding season as fill-in for the statistics of the first match of teams has the potential to add some percentage points but can also misrepresent the actual strength of a team in the new season. Unfortunately, we have found that the latter effect seems to hold. We report only one setting (all seasons as training data, Table In light of our results, the accuracy reported in [1] (74.33%) is surprising. Unfortunately, we have not been able to access a full version of that paper but the abstract (where the accuracy is mentioned) notes that the authors performed extensive tuning of the neural networks used.

Comparing prediction curves

The numbers we have shown in tabulated form in the preceding sections summarize the accuracy of classifiers over the entire season. As we explained in Section 5, however, we classify each day's matches separately, before we relearn the classifier with that day's data added. We can therefore explore the development of predictive accuracy over the course of a season to gain better insight into classifier behavior.

We will use this information to explore the three aspects that we highlighted in the introduction. We begin by looking in more detail at the phenomen that a) professional teams play more games during a season than university teams, and b) the skill differential among professional teams is smaller than between university teams (and professional teams play all possible opponents at least once).

Concretely, professional teams play 82 games before the post-season, university teams only about 30. Since team statistics are averaged over all matches played before the test match, we would therefore assume that descriptors for professional teams are more representative than for university teams and predictions should therefore stabilize better. If, on the other hand, the skill differential has a larger impact, NCAAB predictions should be quicker to stabilize. spectively. 1 The x-axis is labeled with the number of games days -since not all teams play on the same day, there are siginificantly more game days per season than per team. In comparing the NB curves, we see that they stabilize much more quickly for NCAAB than for the NBA. For the NBA, the classifier need about half a season (41 games), whereas for NCAAB the classifier arrives at this point at about a third of the season (10 games).

Moving on to the MLP, we see the clear difference between a classifier with a strong bias, and one exhibiting strong variance. The neural network shows much bigger oscillations than the Naïve Bayes, occasionally outperforming NB at the same relative (early) point of the NBA season. But as in the case of the NB, predictions for the NCAAB stabilize more quickly. Additionally, the swings for the MLP are much smaller. This implies easier decision boundaries, i.e. the larger relative strength differential of which we wrote in the introduction.

Post-season predictions

Compared to the post-season, regular season matches are relatively easier to predict. In the post-season, teams will be mostly more similar in strength, in the 1 The end point of each curve corresponds to the results reported in Tables 8 and4. There are also differences in the number of teams involved in the post-season and the number of games played:

• In the NCAAB, 64 teams reach the post-season (in recent years 68, eight of which play in a "playin" weekend to complete the field). Each pairing of teams only play each other once, for a total of 61 games.

• In the NBA, 16 teams reach the post-season. Each pairing plays best-of-seven series, meaning that a team needs to win four times to move on to the next round. The whole post-season can therefore have between 60 and 105 games.

In both leagues, teams are ranked within a particular group (4 regions in the NCAAB, 2 conferences in the NBA) according to their performance during the regular season. Higher-ranked teams get rewarded by playing lower-ranked ones. Given the larger field in the NCAAB, a first-ranked, i.e. best, team in a region plays the 16th-best. In the NBA, the pairing is best and 8th-best. As a result of this, early rounds should still be easier to predict in the NCAAB than in the NBA. However, the one-shot nature of the NCAAB means that a higher-ranked team that slips up cannot recover -such upsets make up part of the attraction of the post-season. In the NBA, the format will typically favor the better team.

Post-season predictions are therefore affected both by the effects considered in the preceding section, and the different post-season formats.

The NCAAB post-season curves, shown in Figures 5 and6, show that with the exception of 2008/2009 (when notably all four first-ranked teams reached the semi-final round), the cumulative accuracy of postseason predictions are below the regular season accuracy. This is the case by a rather wide margin for NB, but still noticable for the MLP.

Of particular interest is the curve for the MLP for the 2010/2011 post-season. By day three, the 32 matches of the first round (which we expected to be easiest to predict) have been decided, i.e. more than half the total of the post-season, and the MLP boasts an accuracy of more than 80%. In the succeeding the cumulative accuracy deteriorates consistently, reaching the lowest point on day 11 before recovering slightly with the correct prediction of the final match. After the first round, the MLP was effectively not better than chance. This aligns with what They do, however, show much more variation than regular season curves, especially in the beginning. At one end of this is the 2012/13 season, a curve that starts out with 100% accuracy for the first two game days for either classifier. The first round that year saw two of the eight pairings won 4-0 by the higherseeded team, yet also featured an "upset" (sixth over third), bringing the cumulative accuray down. None of the higher-seeded teams lost its first (home) game in the first round. On the other end is the 2013/14 season, which saw three lower-seeded teams win their first-round series, as well as four higher-seeded teams needing seven games to win. In addition, in three of those series, the lower-seeded team won the first (away) game, another ingredient for the low early accuracy in the predictions for that season. We have written above that the best-of-seven format of the NBA playoffs allows the stronger team to recover from off-games. If that were the case, predictors should do well at a series level, i.e. predict the four wins of the eventual winner.

Table 11 shows for each season, how many play-off series each classifier predicted correctly. Notably, the ANN never predicts more than 33% correctly yet its cumulative post-season accuracies were much higher than that. The reason is that it actually manages to correctly predict wins by the eventual loser of a series, something that the NB has problems with. The latter, on the other hand, predicts 11/15 (73.33%) for three seasons.

Finally, there are the Finals series, offering a particularly attractive test case: they consist of at most seven matches, with the number of actually played games an indicator of the relative strength of the two teams. Table 11 lists for each season the number of finals games giving us an upper bound on the accuracy when always predicting the series winner as match winner.

Figure 9 shows that NB shows this behavior (correctly predicting the eventual champion's wins, incorrectly predicting the eventual series loser's) for

Discussion and perspectives

The experimental evaluation shows that the three phenomena we discussed in the introduction:

1. fewer matches in university basketball 2. wider skill spectrum during the regular season in the NCAAB, and 3. strongly differing post-season formats, have noticable effects on predicting the respective leagues. The skill difference means that accuracies in the NCAAB stabilize relatively quickly but combined with the smaller number of games available for estimating statistics, this handicaps the models when it comes to predicting the post-season. This problem is exacerbated by the fact that lower-ranked teams need only one win to upset a higher-ranked one.

A way of addressing this issue could be to train classifiers on a subset of available matches. Limiting training data exclusively to post-season matches seems too restrictive to us: for the 2008/2009 season, for instance, we would have only 61 games available. Alternatively, one could try and augment these data with all regular season matches between the eventual post-season participants. Since NCAAB teams play only around 30 opponents, however, there are not too many of those available. We have recently shown that one can use clustering [START_REF] Zimmermann | Exploring chance in ncaa basketball (originally in[END_REF] to identify clusters of approximately equally strong teams. This could be used to identify good training instances in the data, beyond matches of post-season participants.

The models trained on the NBA regular season transfer more easily to the post-season, since there are more games for estimating statistics, closer skill level, and encounters between all teams. As a result, post-season accuracies are more in line with overall ones, even though the post-seasons stays harder to predict than for college teams. At the level of series winner predictions, however, the best-of-seven format helps the NB classifier to do rather well.

Conclusions and future work

In this paper, we have compared predictions on NCAAB and NBA match data in terms of different representations, predictive settings, and used classifiers. We have found that the adjusted efficiencies used in predicting college matches can be transferred to the case of NBA basketball, and turn out to be the most useful representation for that data. Other statistics and augmentation, for instance with standard deviations, proved less effective.

The particularities of the NCAAB -fewer matches, wider skill distribution, different playoff formatmeans that its regular season is relatively easy to predict but is not an optimal training set for predicting the post-season. In the NBA, the model can be more easily transferred but the league remains somewhat harder to predict, at least on the level of individual games.

NCAAB data is more effectively modeled by a neural network, a learner with a weak bias that can fit any decision boundary, whereas on the NBA data, a learner with strong bias -Naïve Bayes -is more effective. This is particularly pronounced when predicting the winner of playoff series in the NBA, where NB easily outperforms MLP.

A general issue is that our experimental results do not show a single superior option for predictionneither in the case of the NCAAB nor in the case of the NBA. In fact, changes to the representation can change which seasons are predicted well, and which classifiers perform best. One possible future option consists of using these different models (derived from different representations and classifiers), as ensembles. This will require solving the question how to weight each model's input and how to avoid correlated errors. Preliminary results of research we are currently undertaking indicate a second direction: some models seem to perform better in the early season, whereas others need time to ramp up. Identifying the best point to switch would allow to combine models. A third option that we intend to explore is to generate counterfactual data, inspired by Oh et al., and using these data to train classifiers on larger sets of representative matches.

Finally, this study used cumulative accuracy as a performance measure to compare different options. In practical terms, the most immediate practical use of a predictive model would lie in helping to place sports bets. This requires that models be either a) better than betting odds set by sports books, or b) be close enough in accuracy that the times when the model is right and the odds wrong outweigh the times the opposite is true. Since this depends on the actual odds given, correctly predicting big upsets pays out more, evaluating predictive models in this manner requires additional data collection of closing odds for the matches under consideration.

Figures 1 and 2

 2 Figures 1 and 2 (3 and 4) show the cumulative accuracy over the course of a full season achieved by Naïve Bayes (MLP) for the NBA and NCAAB re-

Figure 1 :

 1 Figures 1 and 2 (3 and 4) show the cumulative accuracy over the course of a full season achieved by Naïve Bayes (MLP) for the NBA and NCAAB re-

Figure 2 :

 2 Figure 2: Accuracy on NCAAB data as a function of game days, NB

Figure 3 :

 3 Figure 3: Accuracy on NBA data as a function of game days, MLP

Figure 4 :

 4 Figure 4: Accuracy on NCAAB data as a function of game days, MLP

Table 2 :

 2 Base team statistics vice versa. We explore this phenomenon in more detail by evaluating different attribute combinations in the next sections.

	Statistic	Explanation
	Win Percentage	Number of Wins Number of Games played
	Margin of Victory (MoV)	PPG-PAG in Wins
	Possession-adjusted MoV OEff -DEff in Wins
	Possession-adjusted	OEff-DEff
	Point Differential

Table 3 :

 3 Predictive accuracies per season (NCAAB), one season worth of data, no filling in first-day statistics

Table 4 :

 4 Predictive accuracies per season (NCAAB), training on all preceding seasons, no first-day statistics

	Representation	Season	MLP	NB	RF
	AdjEff	2012/2013	0.7120 0.7024 0.6885
		2011/2012	0.7248 0.7155 0.6946
		2010/2011	0.7115 0.7052 0.6851
		2009/2010	0.7357 0.7318 0.7072
		2008/2009	0.7163 0.7061 0.6907
	AdjFF	2012/2013	0.6983 0.6942 0.6795
		2011/2012	0.7191 0.7076 0.6947
		2010/2011	0.7082 0.6933 0.6847
		2009/2010	0.7257 0.7086 0.7038
		2008/2009	0.7050 0.6850 0.6843

Table 5 :

 5 Predictive accuracies per season (NCAAB), one season worth of data, no filling in first-day statistics, standard deviations

Table 7 :

 7

	Representation	Season	MLP	NB	RF
	AdjEff	2014/2015	0.6209 0.6552 0.6056
		2013/2014	0.6133 0.6300 0.5997
		2012/2013	0.5906 0.6446 0.5799
		2011/2012	0.6210 0.6294 0.6201
		2010/2011	0.6148 0.6606 0.6003
		2009/2010	0.6189 0.6524 0.6204
		2008/2009	0.6433 0.6806 0.6312
	AdjEff-FF	2014/2015	0.6079 0.6430 0.6018
		2013/2014	0.5709 0.6187 0.5929
		2012/2013	0.5807 0.6476 0.6020
		2011/2012	0.5819 0.6313 0.6089
		2010/2011	0.6133 0.6522 0.6301
		2009/2010	0.5747 0.6418 0.6021
		2008/2009	0.6137 0.6586 0.6160
	AdjFF	2014/2015	0.5927 0.6369 0.6133
		2013/2014	0.5982 0.6255 0.6133
		2012/2013	0.5776 0.6416 0.6012
		2011/2012	0.5736 0.6238 0.5847
		2010/2011	0.6240 0.6491 0.6270
		2009/2010	0.6052 0.6402 0.6235
		2008/2009	0.6274 0.6532 0.6297

Predictive accuracies per season (NBA), one season worth of training data, no filling in first-day statistics

Table 8 :

 8

	Representation	Season	MLP	NB	RF
	AdjEff	2014/2015	0.6438 0.6598 0.5988
		2013/2014	0.6240 0.6384 0.6035
		2012/2013	0.6187 0.6499 0.6005
		2011/2012	0.6331 0.6378 0.6006
		2010/2011	0.6506 0.6636 0.6293
		2009/2010	0.6494 0.6456 0.6151
		2008/2009	0.6608 0.6677 0.6395
	AdjEff-FF	2014/2015	0.6346 0.6552 0.6323
		2013/2014	0.6315 0.6338 0.6065
		2012/2013	0.6134 0.6454 0.6058
		2011/2012	0.5857 0.6248 0.6071
		2010/2011	0.6392 0.6545 0.6186
		2009/2010	0.6159 0.6402 0.6349
		2008/2009	0.6251 0.6586 0.6129
	AdjFF	2014/2015	0.6262 0.6590 0.6140
		2013/2014	0.6414 0.6338 0.5914
		2012/2013	0.6050 0.6431 0.6134
		2011/2012	0.5903 0.6313 0.6071
		2010/2011	0.6323 0.6560 0.6369
		2009/2010	0.6319 0.6433 0.6067
		2008/2009	0.6274 0.6563 0.6251

Predictive accuracies per season (NBA), training on all preceding seasons, no filling in

Table 9 :

 9

	Representation	Season	MLP	NB	RF
	AdjEff	2014/2015	0.6499 0.6522 0.6178
		2013/2014	0.6323 0.6414 0.5883
		2012/2013	0.6286 0.6431 0.6073
		2011/2012	0.5978 0.6192 0.6257
		2010/2011	0.6278 0.6506 0.6270
		2009/2010	0.6463 0.6357 0.6220
		2008/2009	0.6327 0.6722 0.6335
	AdjEff-FF	2014/2015	0.6278 0.6491 0.6110
		2013/2014	0.6149 0.6323 0.6096
		2012/2013	0.5997 0.6377 0.6081
		2011/2012	0.6155 0.6229 0.6071
		2010/2011	0.6331 0.6506 0.6171
		2009/2010	0.6044 0.6357 0.6067
		2008/2009	0.6160 0.6525 0.6084
	AdjFF	2014/2015	0.6438 0.6560 0.6293
		2013/2014	0.5906 0.6384 0.5936
		2012/2013	0.6058 0.6431 0.5982
		2011/2012	0.5773 0.6145 0.5875
		2010/2011	0.6598 0.6506 0.6217
		2009/2010	0.6258 0.6319 0.6212
		2008/2009	0.6144 0.6593 0.6167

Predictive accuracies per season, training on all preceding seasons (NBA), no filling in, standard deviations 10), and while there are occasional improvements, the effect is not consistent.

Table 10 :

 10 Predictive accuracies per season, training on all preceding seasons (NBA), filled in first-day statistics

	Representation	Season	MLP	NB	RF
	AdjEff	2014/2015	0.6369 0.6659 0.6156
		2013/2014	0.6331 0.6331 0.5914
		2012/2013	0.6195 0.6499 0.5959
		2011/2012	0.6304 0.6341 0.6080
		2010/2011	0.6438 0.6697 0.6491
		2009/2010	0.6509 0.6425 0.6151
		2008/2009	0.6586 0.6700 0.6289
	AdjEff-FF	2014/2015	0.6178 0.6613 0.6301
		2013/2014	0.6080 0.6376 0.6073
		2012/2013	0.6081 0.6476 0.5974
		2011/2012	0.6024 0.6238 0.6145
		2010/2011	0.6201 0.6560 0.6423
		2009/2010	0.6136 0.6479 0.6303
		2008/2009	0.6274 0.6593 0.6304
	AdjFF	2014/2015	0.6293 0.6682 0.6171
		2013/2014	0.6209 0.6361 0.6080
		2012/2013	0.5951 0.6499 0.6172
		2011/2012	0.6080 0.6369 0.6127
		2010/2011	0.6461 0.6583 0.6293
		2009/2010	0.6410 0.6418 0.6341
		2008/2009	0.6456 0.6624 0.6411


Chun-Ho Ng
email: chng@cse.cuhk.edu.hk

Mingcao Ma
email: mcma@cse.cuhk.edu.hk

Tsz-Yeung Wong
email: tywong@cse.cuhk.edu.hk

Patrick P C Lee
email: pclee@cse.cuhk.edu.hk

John C S Lui

Live Deduplication Storage of Virtual Machine Images in an Open-Source Cloud

Keywords: Deduplication, virtual machine image storage, open-source cloud, file system, implementation, experimentation

Deduplication is an approach of avoiding storing data blocks with identical content, and has been shown to effectively reduce the disk space for storing multi-gigabyte virtual machine (VM) images. However, it remains challenging to deploy deduplication in a real system, such as a cloud platform, where VM images are regularly inserted and retrieved. We propose LiveDFS, a live deduplication file system that enables deduplication storage of VM images in an open-source cloud that is deployed under low-cost commodity hardware settings with limited memory footprints. LiveDFS has several distinct features, including spatial locality, prefetching of metadata, and journaling. LiveDFS is POSIXcompliant and is implemented as a Linux kernel-space file system. We deploy our LiveDFS prototype as a storage layer in a cloud platform based on OpenStack, and conduct extensive experiments. Compared to an ordinary file system without deduplication, we show that LiveDFS can save at least 40% of space for storing VM images, while achieving reasonable performance in importing and retrieving VM images. Our work justifies the feasibility of deploying LiveDFS in an open-source cloud.

Introduction

Cloud computing makes computing and storage resources available to users on demand. Users can purchase resources from commercial cloud providers (e.g., Amazon EC2 [1]) in a pay-as-you-go manner [START_REF] Armbrust | A View of Cloud Computing[END_REF]. On the other hand, commercial clouds may not be suitable for some users, for example, due to security concerns [START_REF] Ristenpart | Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds[END_REF]. In particular, from developers' perspectives, commercial clouds are externally owned and it is difficult to validate new methodologies for a cloud without re-engineering the cloud infrastructures. An alternative is to deploy a self-manageable cloud using open-source cloud platforms, such as Eucalyptus [START_REF] Nurmi | The Eucalyptus Open-source Cloud Computing System[END_REF] and OpenStack [START_REF]OpenStack[END_REF]. Such open-source cloud platforms can be deployed within in-house data centers as private clouds, while providing functionalities similar to commercial clouds. For example, Eucalyptus resembles the functionalities of Amazon EC2. Note that an open-source cloud can be deployed using low-cost commodity hardware and operating systems that are commonly available to general users [START_REF] Nurmi | The Eucalyptus Open-source Cloud Computing System[END_REF]. Similar to commercial clouds, an open-source cloud should provide users with virtual machines (VMs), on which standard applications such as web servers and file storage can be hosted. To make deployment flexible for different needs of users and applications, it is desirable for the open-source cloud to support a variety of versions of VMs for different types of configurations (e.g., 32-bit/64-bit hardware, file systems, operating systems, etc). A major challenge is to scale up the storage of a large number of VM images, each of which is a file that could be of gigabytes. Certainly, increasing the storage capacity for hosting VM images is one option. However, this also implies higher operating costs for deploying an open-source cloud under commodity settings.

One promising technology for improving storage efficiency of VM images is deduplication, which eliminates redundant data blocks by creating smaller-size pointers to reference an already stored data block that has identical content. One major application of deduplication is the data backup in Content Addressable Storage (CAS) systems [START_REF] Quinlan | Venti: a new approach to archival storage[END_REF], in which each data block is identified by its fingerprint computed from a collisionresistant hash of the content of the data block. If two data blocks have the same fingerprint, then they are treated as having the same content. Recent studies [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF][START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF] show that the VM images of different versions of the same Linux distribution generally have a high proportion of identical data blocks (e.g., about 30% of overlap in adjacent Fedora distributions [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF]). Hence, deduplication can actually enhance the storage utilization of VM images. On the other hand, to enable deduplication for VM image storage in a cloud, we need to address several deployment issues:

-Performance of VM operations. Existing studies mainly focus on the effectiveness of using deduplication to save space for storing VM images, but there remain open issues regarding the deployment of deduplication for VM image storage. In particular, it remains uncertain if deduplication degrades the performance of existing VM operations, such as VM startup. -Support of general file system operations. To make the management of VM images more effective, a deduplication solution should allow general file system operations such as data modification and deletion. For example, if an old VM version is no longer used, then we may want to purge the VM image file from the cloud for better maintenance. However, current deduplication techniques are mainly designed for backup systems, which require data be immutable and impose a writeonce policy [START_REF] Quinlan | Venti: a new approach to archival storage[END_REF] to prevent data from being modified or deleted. -Compatibility with low-cost commodity settings. Although there have been commercial file systems (e.g., SDFS [START_REF] Opendedup | NBU for vSphere[END_REF] and ZFS [START_REF]ZFS Dedup FAQ (Community Group zfs.dedup) -XWiki[END_REF]) that support efficient I/O operations while allowing deduplication, they are mainly designed for enterprise servers with a large capacity of main memory. Some deduplication systems [START_REF] Debnath | ChunkStash: Speeding Up Inline Storage Deduplication Using Flash Memory[END_REF][START_REF] Meister | dedupv1: Improving deduplication throughput using solid state drives (SSD)[END_REF] use flash memory to relieve the main memory requirement of deduplication. To make deduplication compatible with commodity settings, a deduplication solution should preserve the I/O performance with reasonable memory footprints and standard commodity hardware configurations.

In this paper, we present a live deduplication file system called LiveDFS, which enables deduplication storage of VM image files in an open-source cloud. In particular, we target the open-source cloud platforms that are deployed in low-cost commodity hardware and operating systems. LiveDFS supports general file system operations, such as read, write, delete, while allowing inline deduplication (i.e., on-the-fly deduplication is applied to data that is to be written to the disk). LiveDFS consists of several design features that make deduplication efficient and practical.

-Spatial locality. LiveDFS stores only partial deduplication metadata (e.g., fingerprints) in memory for indexing, but puts the full metadata on disk. To mitigate the overhead of accessing the metadata on disk, LiveDFS exploits spatial locality by carefully placing the metadata next to their corresponding data blocks with respect to the underlying disk layout. -Prefetching of metadata. LiveDFS prefetches deduplication metadata of the data blocks in the same block group into the page cache (i.e., the disk cache of Linux). This further reduces the seek time of updating both metadata and data blocks on the disk. -Journaling. LiveDFS supports journaling, which keeps track of file system transactions and enables crash recovery of both data blocks and fingerprints. In addition, LiveDFS exploits the underlying journaling design to combine block writes in batch and reduce disk seeks, thereby improving the write performance.

LiveDFS is POSIX-compliant, so its above design features are implemented in such a way that is compliant with the Linux file system layout. It is implemented as a Linux kernel-space driver module, which can be loaded to the Linux kernel without the need of modifying and re-compiling the kernel source code. To justify the practicality of LiveDFS, we integrate it into an open-source cloud platform based on OpenStack [START_REF]OpenStack[END_REF]. Thus, LiveDFS serves as a storage layer between cloud computing nodes and the VM storage backend. We conduct extensive experiments and compare LiveDFS and the Linux Ext3 file system (Ext3FS). We show that LiveDFS saves at least 40% of storage space for VM images compared to Ext3FS. Given that deduplication introduces fragmentation [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF], we also evaluate the performance overhead of LiveDFS in inserting and retrieving VM images in a cloud setting. To our knowledge, this is the first work that addresses the practical deployment of live deduplication for VM image storage in an open-source cloud.

The remainder of the paper proceeds as follows. In Section 2, we present the design of LiveDFS as a deduplication-enabled file system. In Section 3, we explain how LiveDFS is implemented and can be deployed in an open-source cloud based on Open-Stack. In Section 4, we present the empirical experimental results. In Section 5, we review the related work in applying deduplication in storage. Finally, in Section 6, we conclude this paper and present future work.

LiveDFS Design

LiveDFS is a file system that implements inline deduplication for VM storage and is deployed as a storage layer for an open-source cloud. It is designed for commodity hardware and operating systems. For commodity hardware, we consider the native 32bit/64-bit hardware systems with a few gigabytes of memory. Specifically, we seek to reduce the required memory capacity to reduce the hardware cost. For commodity operating systems, we consider Linux, on which LiveDFS is developed.

We make the following assumptions for LiveDFS design. LiveDFS is deployed in a single storage partition. It only applies deduplication to the stored data within the same partition, but not for the same data stored in different partitions. Nevertheless, it is feasible for a partition to have multiple storage devices, such that deduplication is applied in the file-system level, while data striping is applied in the storage devices and is transparent to the file system. In addition, LiveDFS mainly targets for VM image storage. We do not consider applying deduplication for other types of data objects, which may not have any content similarities for deduplication (e.g., encrypted files).

Primitives

We design LiveDFS as a branch of the Linux Ext3 file system (Ext3FS) [START_REF] Cao | State of the art: Where we are with the ext3 filesystem[END_REF]. LiveDFS supports general file system I/O operations such as read, write, and delete. It also supports other standard file system operations for files, directories, and metadata (e.g., changing directories, renaming a file, setting file attributes). Figure 1 depicts the file system layout of LiveDFS, which follows the layout of Ext3FS except that LiveDFS allows block sharing. In the following, we explain the major primitives of LiveDFS as a deduplication-enabled file system. Typical storage systems organize data into blocks, which could be of fixed size or variable size. Most CAS backup systems divide data into variable-size blocks, so as to exploit different granularities of duplicated contents and achieve a higher deduplication rate. The merits of using variable-size blocks in backup systems are studied in [START_REF] Zhu | Avoiding the disk bottleneck in the data domain deduplication file system[END_REF]. Nevertheless, we choose the fixed-size block implementation in LiveDFS with two reasons. First, most commodity CPUs (e.g., Intel x86) support fixed-size memory pages only. Thus, most mainstream file systems adopt the fixed-size block design to optimize the use of memory pages. Second, [START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF] shows that for VM image storage, the deduplication efficiencies of using fixed-size and variable-size blocks are similar. Hence, we define a block as a fixed-size data unit thereafter.

Similar to Ext3FS, LiveDFS arranges blocks into block groups (see Figure 1), each storing the metadata of the blocks within the same group. One advantage of using block groups is to reduce the distance between the metadata and their corresponding blocks on disk, thereby saving the disk seek overhead.

In Ext3FS, each file is allocated an inode, which is a data structure that stores the metadata of the file. In particular, an inode holds a set of block pointers, which store the block numbers (or addresses) of the blocks associated with the file. LiveDFS also exploits the design of an inode and uses block numbers to refer to blocks. In particular, if two blocks have the same content, then we set their block numbers to be the same (i.e., both of them point to the same block). This realizes the block-sharing feature of a deduplication file system. Note that a shared block may be referenced by a single or different files (or inodes).

To enable inline deduplication, LiveDFS introduces two primitives: fingerprints and reference counts. LiveDFS identifies each block by a fingerprint, which is a hash of the block content. If the fingerprints are collision-resistant cryptographic hash values (e.g., MD5, SHA-1), then it is practical to assume that two blocks having different contents will return two different fingerprints [START_REF] Quinlan | Venti: a new approach to archival storage[END_REF]. Since the fingerprint size is much smaller than the block size, we can easily identify duplicate blocks by checking if they have the same fingerprint. Also, to allow block modification and deletion, LiveDFS associates a reference count with each block, such that it keeps the number of block pointers that refer to the block. We increment the reference count of a block if a new block with the same content is written, and decrement it if a block is deleted.

We now describe how LiveDFS performs file system operations. Since LiveDFS is built on Ext3FS, most of its file system operations are the same as those of Ext3FS, except that LiveDFS integrates deduplication into the write operation. LiveDFS implements copy-on-write at the block level. If we update a block that is shared by multiple block pointers, then we either allocate a new block from the disk and write the updated content to the disk, or "deduplicate" the updated block with an existing block that has the same content. Note that the fingerprints and reference counts of the blocks are updated accordingly. If the reference count is decremented to zero, then LiveDFS deallocates the block as in Ext3FS.

To preserve the performance of file system operations when enabling deduplication, a critical issue is how to maintain the fingerprints and reference counts of all data blocks in a disk partition, such that we can search and update their values efficiently during deduplication. We elaborate this in Section 2.2.

Deduplication Design

To enable efficient search of fingerprints during deduplication, one option is to keep all fingerprints in main memory, but this significantly increases the memory cost. For example, if we use a block size of 4KB with 16-byte MD5 fingerprints, then 1TB of data will require 4GB of fingerprint space. As a result, we use an implementation that is similar to approaches in [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF][START_REF] Zhu | Avoiding the disk bottleneck in the data domain deduplication file system[END_REF] to manage the fingerprints. We introduce two components: a set of fingerprint stores and a fingerprint filter. We keep the full fingerprints in a set of fingerprint stores, which reside on disk. On the other hand, we use the fingerprint filter, which resides in main memory, to speed up the search of fingerprints. Specifically, we differentiate our work from [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF][START_REF] Zhu | Avoiding the disk bottleneck in the data domain deduplication file system[END_REF] by carefully placing fingerprints on disk based on the file system layout to further reduce the disk seek overhead during deduplication, as elaborated below. Overview. The main challenge of LiveDFS is about the writing of data blocks. Figure 2 shows how LiveDFS handles that issue. Whenever a data block arrives at LiveDFS (and we name such a block an incoming block thereafter), its fingerprint is generated. We use the fingerprint of the incoming block to determine if the incoming block is unique. The first checkpoint is the fingerprint filter ("FP filter" in Figure 2). The fingerprint filter is a memory-based filter that aims to determine if the incoming block can be deduplicated. If the incoming block is new to the file system, then it can be directly written to the disk. The design of the fingerprint filter will be detailed in later discussion.

Recalling that the fingerprint filter does not store any complete fingerprints, so the next step is to access the corresponding fingerprint store ("FP store" in Figure 2) on disk in order to confirm if the incoming block can actually be deduplicated. If the target fingerprint store does not contain the fingerprint of the incoming block, then it implies that the fingerprint filter gives a false-positive result and that the incoming block is unique; otherwise, the block is not unique and can be deduplicated.

In the following, we first elaborate the design of a fingerprint store, followed by that of the fingerprint filter. Fingerprint store. LiveDFS exploits spatial locality for storing fingerprints with respect to the disk layout of the file system. Our insight is that LiveDFS follows Ext3FS and organizes blocks into block groups, each keeping the metadata of the blocks within the same group. In LiveDFS, each block group is allocated a fingerprint store, which is an array of pairs of fingerprints and reference counts, such that each array entry is indexed by the block number (i.e., block address) of the respective disk block in the same block group. Thus, each block group in the disk partition has its corresponding fingerprint store. Figure 3 shows how LiveDFS deploys a fingerprint store in a block group. We place the fingerprint store at the front of the data block region in each block group. When LiveDFS writes a new block, we write the content to the disk and update the corresponding fingerprint and reference count for the block. A key observation is that all updates are localized within the same block group, so the disk seek overhead is minimized.

To quantify the storage overhead of a fingerprint store, we consider the case where each fingerprint is a 16-byte MD5 hash and each reference count is of 4 bytes. Note that in Ext3FS, the default block size is 4KB and default block group size is 128MB, so there are 32,768 blocks per block group. The fingerprint store will consume 655,360 bytes, or equivalently 160 blocks. This only accounts for 0.49% of the block group size. Hence, the storage overhead of a fingerprint store is limited.

Fingerprint filter. The fingerprint filter is an in-memory indexing structure that aims to speed up the search of fingerprints on disk. While there are many possible designs of indexing techniques (see Section 5), we explore a simple design that suffices for our requirements and is shown to work well according to our evaluation (see Section 4). Figure 4 illustrates the design of the fingerprint filter. The fingerprint filter is a twolevel filter. The first-level filter maps the first n prefix bits of a fingerprint called the index key, while the second-level filter maps the next k bits called the bucket key. We elaborate how n and k can be chosen in later discussion.

We initialize the fingerprint filter when LiveDFS is first mounted. The mounting procedure first allocates the index key table, which is an array of 2 n entries, each of which is a memory address that points to the head of a chain of buckets. Then LiveDFS will read through all fingerprint stores in different block groups, and retrieve the index key, the bucket key, and the block number associated with each disk block. We construct a bucket entry for each tuple (bucket key, block number) and store the entry in the correct bucket according to the index key. If a bucket is full of entries, then we create a new bucket, so a chain of buckets may be created. We sort the bucket entries in each bucket by the bucket keys, in order for us to efficiently search for a bucket entry using binary search. We emphasize that the initialization of the fingerprint filter is only a one-time process, which is performed when the file system is mounted. We evaluate the mount time using our experimental testbed (see Section 4). We find that the mount time is within 3 minutes for a 512GB harddisk partition that is fully filled with data. In general, the mount time varies linearly with the amount of data, and hence the number of fingerprints, being stored on disk.

We query the fingerprint filter whenever there is a new block to be written to the disk. If the fingerprint of the new block matches one of the "n + k"-bit prefixes stored in the filter, then the filter will return the corresponding block number. Note that there may be more than one fingerprint sharing the same "n + k" prefix bits, so the filter may return more than one block number. To eliminate false positives, LiveDFS will look up the corresponding fingerprint store based on each returned block number, and verify if the new block to be written matches the full fingerprint in the fingerprint store. Note that LiveDFS updates the fingerprint filter every time a block is written, modified, or deleted.

Performance impact of parameters. We now elaborate how we set the parameters for the fingerprint filter, which depends on the index key length n and the bucket key length k. These parameters in turn determine the trade-offs of different metrics: (i) the total memory size of the filter, (ii) the false positive rate of each fingerprint filter lookup, and (iii) the bucket chain length. Instead of deriving the optimal choices of the parameters, we consider a special setting which performs well in practice based on our experiments (see Section 4).

In the following, we consider a 1TB partition with of block size 4KB (i.e., 2 28 blocks in total). We employ the 16-byte MD5 hash algorithm to produce fingerprints. The system under our consideration adopts the 32-bit address space. We consider a special case where n = 19 and k = 24. Note that the following analysis can still apply to other parameter settings as well, e.g., 64-bit addressing.

We first evaluate the memory size of the fingerprint filter. For each data block, there is a 7-byte bucket entry, which stores a bucket key of k = 24 bits and a block number of 32 bits. Since there are a maximum of 2 28 blocks, we need 1.792GB of memory for all bucket entries. Also, each index key entry is a 32-bit memory address that points to the head of a bucket chain, so we need 2 19 × 4 = 2MB of memory for all index key entries. If we take into account internal fragmentation, then the fingerprint filter needs at most 2GB of memory, which is available for today's commodity configurations.

We emphasize that the memory footprint of LiveDFS is significantly less than those of ZFS [START_REF]ZFS Dedup FAQ (Community Group zfs.dedup) -XWiki[END_REF] and SDFS [START_REF] Opendedup | NBU for vSphere[END_REF], which assume 64GB and 8GB of memory per 1TB of data with block size 4KB, respectively. Although ZFS and SDFS use longer hashes (SHA-256 and Tiger, respectively) for fingerprints, the reason why they use significantly more memory is that they load the full fingerprints into memory. On the contrary, LiveDFS only loads the fingerprint prefixes into memory, and organizes the full fingerprints near their corresponding data blocks on disk so as to mitigate the disk seek overhead.

We next consider the false positive rate for each fingerprint filter lookup. Recall that there are 2 28 data blocks. For a given fingerprint x, the probability that there exists another fingerprint (or data block) that has the same n + k = 43 prefix bits as x is:

1 -1 -2 -43 2 28 -1 ≈ 2 -15 .
That is, on average every one out of 32,678 blocks will have a fingerprint mapped to more than one block number.

We also evaluate the bucket chain length. If the fingerprint value is uniformly distributed, then the average number of buckets associated with each index key is 2 28 /2 19 = 512 (for n = 19). Each bucket entry is of 7 bytes. If each bucket is stored as a memory page of size 4KB, then it can hold around 585 bucket entries, and the average bucket length is less than one bucket.

Prefetching of Fingerprint Store

Whenever LiveDFS writes a block, the fingerprint and the reference count of that block has to be updated. As a result, LiveDFS has to access the corresponding fingerprint store on disk every time LiveDFS is writing a data block. We improve the performance of our deduplication design by extending the notion of spatial locality for caching fingerprints in memory. Our key observation is that a VM image file generally consists of a large stream of data blocks. If a data block is unique and cannot be deduplicated with existing blocks, then it will be written to the disk following the previously written block. Thus, the data blocks of the same block group are likely to be accessed at about the same time.

In order to further reduce the number of disk seeks, LiveDFS implements a fingerprint prefetching mechanism. When LiveDFS is about to access the fingerprint store of a block group, instead of accessing only the target block (which contains the target fingerprint), LiveDFS prefetches the entire fingerprint store of the corresponding block group and store it into the page cache, the disk cache of the Linux kernel. Therefore, subsequent writes in the same block group can directly update the fingerprint store in the page cache. The I/O scheduler of the Linux kernel will later flush the page cache into the disk. This further reduces the disk seeks involved. We point out that the consistency of the data content between the page cache and the disk is protected by the underlying journaling mechanism (see Section 2.4). Note that the idea is also used in [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF][START_REF] Zhu | Avoiding the disk bottleneck in the data domain deduplication file system[END_REF], except that we apply the idea in accordance with the Linux file system design.

The following calculations show that the overhead of our fingerprint prefetching mechanism is small. Suppose that LiveDFS uses MD5 hashes as the fingerprints of data blocks. Then a fingerprint store in a block group consumes 160 blocks (or 640KB space). Today an ordinary 7200-RPM hard disk typically has a data rate of 100MB/s, so it will consume only about 6-7ms for prefetching a whole fingerprint store into memory (i.e., the page cache). This time value is close to the average time of a random disk seek, which can be around 8-10ms [START_REF]7200-RPM Drive Specification Comparison[END_REF].

Journaling

LiveDFS supports journaling, a feature that keeps track of file system transactions in a journal so that the file system can be recovered to a stable state when the machine fails, e.g., power outage. LiveDFS extends the journaling design in Ext3FS. In particular, we treat every write to a fingerprint store as the file system metadata and have the journal process modifications to the fingerprints and reference counts.

Figure 5 shows the pseudo-code of how LiveDFS updates a fingerprint store for a data block P to be written to the file system, while a similar set of procedures are taken when we delete a data block from the file system. Our goal is to update the fingerprint and the reference count associated with the block P. First, we obtain the handle that refers to the journal and perform the updates of metadata (e.g., indirect blocks, inodes) for P as in Ext3FS (Lines 1-2). If P is a new block that cannot be deduplicated with any existing disk block, then LiveDFS first loads the corresponding block that stores P's fingerprint into memory (Line 4), and notify the journal that the fingerprint block is about to be updated via the function ext3 journal get write access() (Line 5). After the fingerprint block is updated, we notify the journal that the modification is finished via the function ext3 journal dirty metadata() (Lines 6-7). Then, we update P's reference count similarly (Lines 9-12). When LiveDFS releases the journal handle (Line 13), the journal will update the fingerprint store on disk atomically. Not only can the journal improve the file system reliability, but it can also enhance the write performance. The journal defers the disk updates of each write request and combines multiple disk writes in batch. This reduces the disk seeks and improve the write performance. We demonstrate this improvement in Section 4.

LiveDFS Implementation and Deployment

LiveDFS is a kernel-space file system running atop Linux. We implemented LiveDFS as a kernel driver module for the Linux kernel 2.6.32, and it can be loaded to the kernel without requiring any modification or recompilation of the kernel source code. The deduplication logic is implemented by extending the virtual file system (VFS) address space operations. In particular, we perform fingerprint computation and determine if a block can be deduplicated in the function writepage() (in Linux source tree: fs/ext3/inode.c), which is called by a kernel thread and will flush dirty pages to the disk.

Since LiveDFS is POSIX-compliant, it can be seamlessly integrated into an opensource cloud platform that runs atop Linux. In this work, we integrate LiveDFS into OpenStack [START_REF]OpenStack[END_REF], an open-source cloud platform backed by Rackspace and NASA, such that LiveDFS serves as a storage layer for hosting VM images with deduplication. We point out that Eucalyptus [START_REF] Nurmi | The Eucalyptus Open-source Cloud Computing System[END_REF] has a similar architecture as OpenStack, so we expect that the deployment of LiveDFS in Eucalyptus follows a similar approach. OpenStack overview. OpenStack is built on three sub-projects Compute (named Nova), Object Storage (named Swift), and Image Service (named Glance). Figure 6 shows a simplified view of an OpenStack cloud, which consists of Nova and Glance only. Nova defines an architecture that uses several controller services that coordinate the VM instances running on different Compute nodes. Glance is a VM image management system that is responsible for registering, searching, and retrieving VM images. It provides APIs for accessing a storage backend, which could be Object Storage (Swift), Amazon S3, or a local server on which Glance is deployed. Note that OpenStack uses the euca2ools command-line tool provided by Eucalyptus to add and delete VM images.

Experiments

In this section, we empirically evaluate our LiveDFS prototype. We first measure the I/O throughput performance of LiveDFS as a disk-based file system. We then evaluate the deployment of LiveDFS in OpenStack-based cloud platform. We justify the performance overhead of LiveDFS that we observe. We compare LiveDFS with Ext3FS, which does not support deduplication.

I/O Throughput

We measure the file system performance of different I/O operations using synthetic workload based on LiveDFS and Ext3FS. In LiveDFS, we assume that the index key length n is 19 bits and the bucket key length k is 24 bits (see Section 2.2). Note that LiveDFS is built on different design components, including (i) spatial locality, in which we allocate fingerprint stores in different block groups (see Section 2.2), (ii) prefetching of a fingerprint store (see Section 2.3), and (iii) journaling (see Section 2.4). We evaluate different LiveDFS variants that include different combinations of the design components, as shown in Table 1, to see the performance impact of each component. When spatial locality is disabled, we simply place all fingerprint stores at the end of the disk partition; when prefetching is disabled, we bypass the step of prefetching a fingerprint store into the page cache; when journaling is disabled, we use alternative calls to directly write fingerprints and reference counts to the fingerprint stores on disk. Experimental testbed. Our experiments are conducted on a Dell Optiplex 980 machine with an Intel Core i5 760 CPU at 2.8GHz and 8GB DDR-III RAM. We equip the machine with two harddisks: a 1TB harddisk of Western Digital WD1002FAEX 7200RPM SATA for our benchmarking, and a 250GB harddisk for hosting our benchmarking tools and the operating system. Our operating system is Ubuntu 10.04.2 server 64-bit edition with Linux kernel 2.6.32. Evaluation methodology. We use Linux basic system calls read() and write() to measure the I/O performance. Each experimental result is averaged over 10 runs.

In each run, we use the system call gettimeofday() to obtain the duration of an operation, and then compute the throughput. At the beginning of each run, we clear the kernel page cache using the command echo 3 > /proc/sys/vm/drop caches so that we can accurately evaluate the performance due to disk accesses. Experiment A1: Sequential write. We first evaluate the sequential write performance of LiveDFS by writing a 16GB file with all unique blocks (i.e., all blocks cannot be deduplicated with others). The file size is larger than the 8GB RAM in our test machine, so that not all requests are kept in the kernel buffer cache.

Figure 7 shows the throughput of different LiveDFS variants and Ext3FS. First, considering LiveDFS-J and LiveDFS-SJ, we observe that LiveDFS-SJ has a higher throughput than LiveDFS-J by 16.1MB/s (or 37%). Thus, spatial locality by itself can improve the throughput, by putting the fingerprint stores close to their blocks on disk.

We note that LiveDFS-S (without journaling) has the lowest throughput among all variants. Specifically, LiveDFS-SJ increases the throughput of LiveDFS-S by 34.6MB/s (or 78.6%). Since journaling combines write requests and flushes them to the disk in batch (see Section 2.4), journaling can effectively minimize the disk accesses in addition to providing robustness against system crashes.

We observe that LiveDFS-all further improves the throughput of LiveDFS-SJ via prefetching (by 13.8MB/s, or 18%). Now, comparing LiveDFS-all and Ext3FS, we observe that LiveDFS-all is slightly less than Ext3FS's throughput by 3.7MB/s (or 3.8%), mainly due to the increase in the block group accesses. Because we introduce a fingerprint store to each block group, LiveDFS has fewer data blocks per block group than Ext3FS. However, we show that each design component of LiveDFS can reduce disk accesses and increase the throughput of LiveDFS close to that of Ext3FS. Experiment A2: Sequential read. In this experiment, we evaluate the sequential read performance of LiveDFS by reading the stored 16GB file created in Experiment A1. Figure 8 shows the results. LiveDFS and Ext3FS. We observe that all LiveDFS variants have almost the same throughput as Ext3FS, mainly because LiveDFS uses the same execution path as that of Ext3FS for reading data blocks. Experiment A3: Sequential duplicated write. In this experiment, we write another 16GB file that has the identical content to the one in Experiment A1. Figure 9 shows the results. We observe that all LiveDFS variants (except LiveDFS-S without journaling) significantly boost the throughput of Ext3FS by around 120MB/s. The reason is that LiveDFS only needs to read the fingerprints of data blocks and update the reference counts, without re-writing the same data blocks (with larger size) to the disk. We note that the write-combining feature of journaling plays a significant role in boosting the throughput of LiveDFS, as LiveDFS-S does not achieve the same improvement. Experiment A4: Crash recovery with journaling. In this experiment, we consider how deduplication affects the time needed for a file system to recover from a crash using journaling. We set the journal commit interval to be five seconds when the file system is first mounted. We then write a 16GB file with unique blocks sequentially into LiveDFS, and unplug the power cable in the middle of writing. The file system is therefore inconsistent. After rebooting the machine, we measure the time needed for our file system check tool fsck, which is modified from the Ext2FS utility e2fsprogs to recover the file system. We observe that LiveDFS ensures the file system correctness using journaling. However, it generally uses a longer recovery time than Ext3FS. On average (over 10 runs), LiveDFS uses 14.94s to recover, while Ext3FS uses less than 1s. The main reason is that LiveDFS needs to ensure that the fingerprints in the fingerprint store match the new data blocks being written since the last journal commit interval. Such additional fingerprint checks introduce overhead. Since system crashes are infrequent, we expect that the recovery time is acceptable, as long as the file system correctness is preserved.

OpenStack Deployment

We now evaluate LiveDFS when it is deployed in an OpenStack-based cloud. Our goal is to justify the practicality of deploying LiveDFS in a real-life open-source cloud for VM image storage with deduplication. Specifically, we aim to confirm that LiveDFS achieves the expected storage savings as observed in prior studies [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF][START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF], while achieving reasonable I/O performance of accessing VM images. System configuration. Our experiments are conducted in an OpenStack cloud platform consisting of three machines: a Nova cloud controller, a Glance server, and a Compute node. The Nova cloud controller is equipped with an Intel Core 2 Duo E7400 2.8GHz CPU, while both the Glance server and the compute node are equipped with an Intel Core 2 Quad Q9400 2.66GHz CPU. All machines are equipped with 4GB DDR-II RAM, as well as two harddisks: a 1TB 7200RPM harddisk for storing VM images and a 250GB harddisk for hosting the operating system and required software. All machines use Ubuntu 10.04.2 server 64-bit edition as the operating system. Furthermore, all three machines are inter-connected by a Gigabit Ethernet switch, so we expect that the network transmission overhead has limited performance impact on our experiments.

All VM images are locally stored in the Glance server. We deploy either LiveDFS or Ext3FS within the Glance server, which can then access VM images via the deployed file system using standard Linux file system calls. We also deploy Kernel-based Virtual Machine (KVM) as the default hypervisor in the compute node. By default, we assume that LiveDFS enables all design components (i.e., spatial locality, prefetching, and journaling).

Our cloud testbed consists of only one Compute node, assuming that in most situations there is at most one Compute node that retrieves a VM image at a time. We also evaluate the scenario when a Compute node retrieves multiple VM images simultaneously (see Experiment B3).

Dataset. We use deployable VM images to drive our experiments. We have created 42 VM images in Amazon Machine Image (AMI) format. Table 2 lists all the VM images. The operating systems of the VM images include ArchLinux, CentOS, Debian, Fedora, OpenSUSE, and Ubuntu. We prepare images of both x86 and x64 architectures for each distribution, using the recommended configuration for a basic server. Networked installation is chosen so as to ensure that all installed software packages are up-to-date. Each VM image is configured to have size 2GB. Finally, each VM image is created as a single monolithic flat file. Experiment B1: Storage efficiency. We first validate that LiveDFS can save space for storing VM images. Note that each VM image typically has a large number of zerofiled blocks [START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF]. One main source of zero-filled blocks, according to our created VM images, is due to the unused space of the VM. To reflect the true saving achieved by deduplication, we exclude counting the zero-filled blocks in our evaluation. Figure 10(a) shows the cumulative space usage of storing the VM images using LiveDFS and Ext3FS. Overall, LiveDFS saves at least 40% of space over Ext3FS (for non-zero-filled blocks). If we count the zero-filled blocks as well, then LiveDFS still uses around 21GB of space (as all zero-filled blocks can be denoted by a single block), while Ext3FS consumes 84GB of space for the 42 2-GB VM images. In this case, we can even achieve 75% of saving. Figure 10(b) shows the average space usage of a VM image for each Linux distribution. The space savings range from 33% to 60%. It shows that different versions of VM images of the same Linux distribution have a high proportion of identical data blocks that can be deduplicated. Therefore, our LiveDFS implementation conforms to the observations that deduplication is effective in improving the storage efficiency of VM images [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF][START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF]. We do not further investigate the deduplication effectiveness of VM images, which has been well studied in [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF][START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF]. Experiment B2: Time for inserting VM images. In this experiment, we evaluate the time needed for inserting VM images into our Glance server. We execute the commands euca-bundle-image, euca-upload-bundle, and euca-register1 to insert the VM images from the cloud controller to the Glance server (over the Gigabit Ethernet switch). We repeat the test five times and obtain the average. Our goal is to measure the practical performance of writing VM images using LiveDFS.

Figure 11(a) shows the average insert time for individual distributions (over five runs). Overall, LiveDFS consumes less time than Ext3FS in inserting VM images. The reason is that LiveDFS does not write the blocks that can be deduplicated to the disk, but instead it only updates the smaller-size reference counts. Figure 11(b) shows the average insert time for all 42 VM images using different LiveDFS variants as defined in Section 4.1. Although this time the differences among the different LiveDFS variants are not as significant as seen in Section 4.1, we observe that enabling all design components (i.e., LiveDFS-all) still gives the least insert time. Experiment B3: Time for VM startup. We now evaluate the time needed to launch a single or multiple VM instances. We assume that all VM images have been inserted into the file system. We then execute the euca-run-instances command in the Nova cloud controller to start a VM instance in the Compute node, which fetches the corre- sponding VM image from the Glance server. We measure the time from the command being issued until the time when the euca-run-instances command invokes the KVM hypervisor (i.e., when the VM starts running). Our goal is to measure the practical performance of reading VM images using LiveDFS. Figure 12(a) shows the time needed to launch a single VM instance for different distributions in the Compute node. We observe that LiveDFS has lower throughput performance than Ext3FS. The main reason is that deduplication introduces fragmentation [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF]. That is, in deduplication, some blocks of a file may be deduplicated with the blocks of a different file, so the actual block allocation of a file on disk is no longer in the sequential order as seen in the ordinary file system without deduplication. Fragmentation is an inherent problem in deduplication, as it remains an open issue to be solved [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF]. To see how fragmentation affects the practical performance, we note that in LiveDFS, its increase in VM startup time ranges from 3s to 21s (or 8% to 50%) for a VM image of size 2GB. Currently, the cloud nodes are connected over a Gigabit Ethernet switch. We expect that the VM startup penalty will become less significant if we deploy the cloud in a network with less available bandwidth (e.g., the cloud nodes are connected by multiple switches that are shared by many users), as the network transmission overhead will dominate in such a setting.

We now consider the case when we launch multiple VM instances in parallel. In the Compute node, we issue multiple VM startup commands simultaneously, and measure the time for all VM instances to start running. Figure 12(b) shows the time required for starting one to four VM instances in the Compute node. The overhead of LiveDFS remains consistent (at around 30%), regardless of the number of VM instances being launched. The observation conforms to that of launching a single VM instance.

Related Work

Existing deduplication techniques are mainly designed for backup systems. On the other hand, LiveDFS applies deduplication in a different design space and is designed for VM image storage in a cloud platform. Also, LiveDFS seeks to be POSIX-compliant, so its implementation details take into account the Linux file system layout and are different from existing deduplication systems. In this section, we review the related work in deduplication in more detail. Backup systems. Venti [START_REF] Quinlan | Venti: a new approach to archival storage[END_REF] is the first work of content addressable storage (CAS) for data backup. Foundation [START_REF] Rhea | Fast, inexpensive content-addressed storage in foundation[END_REF] is another CAS system built upon Venti, and improves Venti with the new compare-by-value mode. It uses the Bloom filter as an in-memory indexing structure to identify new or existing fingerprints. LiveDFS uses the fingerprint filter as an in-memory indexing structure. However, the fingerprint filter not only identifies the existence of fingerprints as in the Bloom filter, but it also specifies where the fingerprint is stored on disk. Data Domain [START_REF] Zhu | Avoiding the disk bottleneck in the data domain deduplication file system[END_REF] also uses the Bloom filter [START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] for in-memory indexing, and uses locality preserved caching to reduce random I/Os for duplicated data. Sparse Indexing [START_REF] Lillibridge | Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality[END_REF] trades deduplication opportunities for reduced memory usage in backup systems by only deduplicating data with a few of the most similar previous copies in different backup streams. Bimodal Content Defined Chunking [START_REF] Kruus | Bimodal content defined chunking for backup streams[END_REF] reduces the memory overhead of chunk indexing by using chunks with different granularities in different regions of a backup. Note that the above systems do not consider the scenario where data can be modified or deleted, while LiveDFS addresses this by associating a reference count with each data block in its deduplication design. Usage of flash memory. Dedupv1 [START_REF] Meister | dedupv1: Improving deduplication throughput using solid state drives (SSD)[END_REF] and ChunkStash [START_REF] Debnath | ChunkStash: Speeding Up Inline Storage Deduplication Using Flash Memory[END_REF] use flash memory and solid state drives (SSDs) to relieve the memory constraints of deduplication. They exploit the fast random I/O feature of flash memory by putting the fingerprints into the flash rather than in main memory. They show that they achieve competent I/O performance while requiring a small memory capacity. On the other hand, LiveDFS targets a commodity server that is not necessarily equipped with SSDs. Scalable storage. Extreme Binning [START_REF] Bhagwat | Extreme binning: Scalable, parallel deduplication for chunk-based file backup[END_REF], HydraFS [START_REF] Ungureanu | HydraFS: a High-Throughput File System for the HYDRAstor Content-Addressable Storage System[END_REF] and DeDe [START_REF] Clements | Decentralized deduplication in SAN cluster file systems[END_REF] are scalable storage systems that support data deduplication. Extreme Binning exploits file similarity rather than chunk locality. HydraFS is a file-system built atop HYDRAstor [START_REF] Dubnicki | Hydrastor: A scalable secondary storage[END_REF]. DeDe is a storage system that performs out-of-order deduplication. Their deployment platforms are based on a distributed environment, while LiveDFS is designed to be deployed on a single commodity server. Deduplication-enabled file systems. ZFS by Sun Microsystems [START_REF]ZFS Dedup FAQ (Community Group zfs.dedup) -XWiki[END_REF] and SDFS by Opendedup [START_REF] Opendedup | NBU for vSphere[END_REF] are file systems supporting inline deduplication. However, as stated in Section 2.2, they need a large memory capacity for enabling deduplication, mainly because they assume that the entire set of fingerprints is loaded into memory. In terms of deployment, ZFS and SDFS are mainly designed for enterprise-scale systems, while LiveDFS is designed as a kernel-space file system for commodity servers. Btrfs [5] is an open-source file system developed by Oracle that supports deduplication. While Btrfs is a Linux kernel module like LiveDFS, it only supports offline deduplication [19] instead of inline at the time of this writing. VM image storage. It has been shown [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF][START_REF] Jin | The effectiveness of deduplication on virtual machine disk images[END_REF] that deduplication can significantly save the storage space for VM images. However, there remain open issues of deploying deduplication in a VM storage system. Nath et al. [START_REF] Nath | Design Tradeoffs in Applying Content Addressable Storage to Enterprise-scale Systems Based on Virtual Machines[END_REF] evaluate a deployed CAS system for storing VM images. They mainly focus on storage efficiency and network load, but do not evaluate the read/write throughput of accessing VM images. Liguori et al. [START_REF] Liguori | Experiences with Content Addressable Storage and Virtual Disks[END_REF] deploy a CAS system based on Venti [START_REF] Quinlan | Venti: a new approach to archival storage[END_REF] for storing VM images, but its read/write throughput is limited by the Venti implementation. Lithium [START_REF] Hansen | Lithium: Virtual Machine Storage for the Cloud[END_REF] is a cloud-based VM image storage system that aims for fault tolerance, but it does not consider deduplication. To our knowledge, LiveDFS is the first practical system that deploys deduplication for VM image storage in a real cloud platform.

Conclusions and Future Work

We propose LiveDFS, a live deduplication file-system that is designed for VM image storage in an open-source cloud with commodity configurations. LiveDFS respects the file system design layout in Linux and allows general I/O operations such as read, write, modify, and delete, while enabling inline deduplication. To support inline deduplication, LiveDFS exploits spatial locality to reduce the disk access overhead for looking up fingerprints that are stored on disk. It also supports journaling for crash recovery. LiveDFS is implemented as a Linux kernel driver module that can be deployed without the need of modifying the kernel source. We integrate LiveDFS into a cloud platform based on OpenStack and evaluate the deployment. We show that LiveDFS saves at least 40% of storage space for different distributions of VM images, while its performance overhead in read/write throughput is minimal overall. Our work demonstrates the feasibility of deploying deduplication into VM image storage in an open-source cloud.

In this work, we mainly focus on deduplication on a single storage partition. Since a cloud platform is typically a distributed system, we plan to extend LiveDFS in a distributed setting (e.g., see [START_REF] Muthitacharoen | A low-bandwidth network file system[END_REF]). One challenging issue is to balance the trade-off between storage efficiency and fault tolerance. On one hand, deduplication reduces the storage space by removing redundant data copies; on the other hand, it sacrifices fault tolerance with the elimination of redundancy. We pose this issue as future work.

The source code of LiveDFS is published for academic use at http://ansrlab.cse.cuhk.edu.hk/software/livedfs.

Fig. 1 .

 1 Fig. 1. File system layout of LiveDFS, which is similar to the Ext3FS but supports block sharing.

Fig. 2 .

 2 Fig. 2. Every block written to LiveDFS goes through the same decision process.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Deployment of a fingerprint store in a block group.

Fig. 5 .

 5 Fig. 5. Pseudo-code of how LiveDFS updates the fingerprint store through the journaling system.

Fig. 6 .

 6 Fig. 6. LiveDFS deployment in an OpenStack cloud.

Fig. 7 .Fig. 8 .Fig. 9 .

 789 Fig. 7. Throughput of sequential write.

Fig. 10 .

 10 Fig. 10. Space usage of VM images (excluding zero-filled blocks).

Fig. 11 .

 11 Fig. 11. Average time required for inserting a VM image to the Glance server.

  Startup time for multiple VM instances using the Ubuntu distribution.

Fig. 12 .

 12 Fig. 12. Average time for VM startup.

Table 1 .

 1 Different LiveDFS variants evaluated in Section 4.1 ( √ = enabled, × = disabled).

Table 2 .

 2 The collection of virtual machine images involved in the experiments.

	Distribution	Version (x86 & x64)	Total
	ArchLinux	2009.08, 2010.05	4
	CentOS	5.5, 5.6	4
	Debian	5.0.8, 6.0.1	4
	Fedora	11, 12, 13, 14	8
	OpenSUSE	11.1, 11.2, 11.3, 11.4	8
	Ubuntu	6.06, 8.04, 9.04, 9.10, 10.04, 10.10, 11.04	14

Those euca-* commands come with euca2ools, the command-line tool of Eucalyptus for VM image management.

Acknowledgments

This work was supported in part by grant ITS/297/09 from the Innovation and Technology Fund of the HKSAR.