Nicolas Anciaux

Luc Bouganim

Harold Van Heerde

Philippe Pucheral

Peter M G Apers
email: apers@ewi.utwente.nl

Data degradation: Making private data less sensitive over time

Keywords: H.2.7 [Database Administration]: Security, integrity, and protection Algorithms, Management, Security, Human Factors Privacy, limited retention, data degradation

come

INTRODUCTION

Personal digital trails are difficult to protect. As any data, they are exposed to accidental disclosures resulting from negligence or piracy. The personal details of 25 million UK citizens have been recently lost inadvertently and some of the data published by AOL about Web search queries of 657,000 Americans have been deanonymized. Even the most defended servers (including those of Pentagon, FBI and NASA) are successfully attacked. But more, personal digital trails are often weakly protected by obscure and loose privacy policies which are presumed accepted when exercising a given service. This fosters ill-intentioned scrutinization and abusive usages justified by business interests, governmental pressures and inquisitiveness among people. No one is sheltered because common events, like applying for a job or a credit, can suddenly make anybodies' digital trail of utmost interest for someone else. Companies like Intelius or ChoicePoint make scrutinization their business while others like ReputationDefender provide a lucrative service to destroy the sensitive part of personal digital trails subject to scrutinization.

We define trail disclosure as the leakage of data pertaining to a personal digital trail and resulting from negligence, attack or abusive scrutinization or usage. By definition, its occurrence assumes that all security mechanisms have been bypassed or that the ac-cess control policy has been defined too weakly. Promoted by most legislation protecting personal data, the limited data retention principle consists of attaching a lifetime to a data compliant with its acquisition purpose, after which it must be withdrawn from the system. The shorter the retention period is, the smaller the total amount of data needlessly exposed, reducing the impact of trail disclosure [START_REF] Agrawal | Hippocratic databases[END_REF]. Beyond the protection of personal data, the limited data retention principle is also a cornerstone of the ISO/IEC 27002:2005 recommendation for protecting enterprise information systems.

However, the limited data retention principle is difficult to put in practice. In some countries, minimal retention periods can be fixed for law enforcement or legal processes purposes (e.g., banking information in UK cannot be destroyed before 7 years). In this case, the same retention limit is used for privacy preservation purposes, for which such limits are usually to large. For the large amount of data not covered by law, the retention limit is supposed to reflect the best compromise between privacy preservation and application purposes reach. In practice, the same data item is likely to serve different purposes, leading to selecting the largest retention limit compatible with all purposes, as suggested in [START_REF] Agrawal | Hippocratic databases[END_REF]. Moreover, the purposes exposed in most privacy policies are fuzzy enough to defend very long retention limits (years or decades), denaturing the initial principle. As a consequence, retention limits are seen by civil rights organizations as a deceitful justification for long term storage of personal data by companies.

We propose a new approach which opens up an alternative to reason about and implement limited data retention. It is based on the assumption that long lasting purposes can often be satisfied with a less accurate, and therefore less sensitive, version of the data. The objective of the proposed approach is to progressively degrade the data after a given time period such that (1) the intermediate states are informative enough to serve application purposes and (2) the accurate state cannot be recovered by anyone after this period, not even by the server. To the best of our knowledge, this approach is the first attempt to implement the essence of the limited data retention principle, which is limiting the retention of any information to the period strictly necessary to accomplish the purpose for which it has been collected. Hence, if the same information is collected to serve different purposes, degraded states of this information and their respective retention limits are defined according to each application purpose.

By degrading attributes forming a quasi-identifier, kanonymisation [START_REF] Sweeney | K-anonymity: A model for protecting privacy[END_REF] shares some similarities with our data degradation model. However, both models pursue different objectives. k-Anonymisation transforms the database content such that the data of a single individual cannot be distinguished from the one of k-1 other individuals. Thus, no other purposes than statistics computa-tions can be satisfied. By contrast, our data degradation model applies to attributes describing a recorded event while keeping the identity of the user intact. Hence, user-oriented purposes are preserved.

The threat model considered by data degradation is the same as for limited data retention. It does the two following assumptions on the recording system (i.e., the DBMS): (1) the system implements without malice all security policies which have been defined (including retention control); (2) the system cannot prevent all forms of attacks, negligence or weakly defined policies which could expose, at any given time, the personal digital trail of a victim to an adversary.

In a trail disclosure resulting from a piracy attack, the adversary is a hacker or a dishonest employee breaking into the server with the objective to get access to a set of user's digital trails (e.g., for a lucrative purpose) and the victims are the targeted users (potentially all users of the system). In a trail disclosure resulting from a weak policy declaration, the adversary is anyone (e.g., an insurance or credit company, an employer, a governmental agency) having a particular interest to scrutinize the digital trail of an identified victim (e.g., a future client or employee, a suspect citizen). In a trail disclosure resulting from a negligence, the adversary is anyone getting access to the disclosed digital trails (e.g., could be internet user in the AOL disclosure scandal) and the victim can be anyone having a singular personal digital trail (e.g., user 4417749 identified as Thelma Arnold, a 62-year-old Georgian widow).

Data degradation however, as any data retention model, cannot defeat trail disclosures performed by an adversary spying the database system from its creation. To be effective, such attack must be repeated with a frequency smaller than the duration of the shortest degradation step. Such continuous attacks are much more easily detectable thanks to Intrusion Detection Systems and Auditing Systems. Besides, data degradation is complementary to any access control techniques.

An important question is whether data degradation can be reasonably implemented in a DBMS. Even guaranteeing that data cannot be recovered after a regular delete is not easy [START_REF] Stahlberg | Threats to privacy in the forensic analysis of database systems[END_REF]. Data degradation is a more complex process which includes physical data deletion but impacts more thoroughly the data storage, indexation, logging and locking mechanisms to deal with data traversing a sequence of states. As retention limits become shorter, the number of degradation steps increases and the performance problem arises. For more details we refer to [START_REF] Anciaux | InstantDB: Enforcing Timely Degradation of Sensitive Data[END_REF].

MOTIVATING SCENARIO

To illustrate our approach, we sketch here a concrete scenario where data degradation can be applied. It takes place in an organization which wants to provide new services to its employees, enabled by the analysis of employees' web activity. Each internet access is captured as one tuple in a personal trail containing four attributes: ID is the employee's identifier, URL is the resource locator of the visited page, TIME and DUR are respectively the date and the duration of the visit. Such personal trails are sensitive and may violate privacy if disclosed. Indeed, a full trail gives complete information about web activities (what, when and how long). Past timetables can be reconstituted simply from attributes ID and TIME. Moreover, the full trail may give sensitive information about any given employee such as the delay before starting a task (reactivity), the time taken to accomplish a task (productivity), the time spent on useless or extra work activities, etc. Notice that we consider "an organization" in this scenario, but the privacy invasion is even stronger when tracking people within the private sphere.

Examples of services enabled in such a context are: S1: Synchronous co-browsing. Employees can see the current web trail of colleagues. For example, people making a web survey to prepare a meeting may use this feature to search in parallel. S2: Asynchronous co-browsing. Each employee can retrieve the past web trails of other colleagues. This would enable people to suspend/resume investigations [START_REF] Morris | SearchTogether: An Interface for Collaborative Web Search[END_REF] S3: Passive co-browsing. Employees benefit from implicit feedback of colleagues, computed from their past trails. In particular, each link in visited web pages is complemented with statistics generated by colleagues having followed the link (e.g., name along with duration and frequency). S4: Profiling employees. HR department often requires employees' domains of expertise, e.g., to identify interesting trainings to be proposed or to find the correct person to which delegating the organization of an event (e.g., a seminar). Domains of expertise are obtained from web trails (e.g., MySQL experts most probably visit mysql.com often and extensively).

To fulfil its purpose, service S1 requires accurate recent histories (e.g., 1 day) to enable parallel investigations. S2 requires longer histories (e.g., 1 week) but with degraded attributes TIME and DUR: the date in days can replace the exact time in seconds; the exact duration can be degraded to a value from the domain Bi-nary_dur = {short; long}. S3 requires even longer trails (e.g., 1 month) and can be fulfilled with a TIME value expressed in weeks and a URL value degraded to its static part (i.e., the path without parameters, hence, no content generated based on users' inputs). S4 requires long term trails (e.g., 1 year) with TIME in months and URL reduced to the domain subpart (e.g., "MySql.com").

RESEARCH AGENDA

Data degradation strictly implements the limited retention principle, increasing privacy with respect to trail disclosures, without touching the ability for applications to reach its purposes. We already devised a simple and limited version of the degradation model [START_REF] Anciaux | InstantDB: Enforcing Timely Degradation of Sensitive Data[END_REF]. Current work aims at a better understanding of the impact of degradation on traditional database technology. In the next steps, we investigate necessary extensions of the model in terms of flexibility and usability, where users are better involved into the degradation process (e.g., personalized degradation policies given optins purposes), and where the content of the data influences the degradation.


Umberto Castellani

Aydın Ulaş

Vittorio Murino

Marcella Bellani

Gianluca Rambaldelli

Michele Tansella

Paolo Brambilla

Selecting Scales by Multiple Kernel Learning for Shape Diffusion Analysis

Keywords: multiple kernel learning, schizophrenia, heat kernel, spectral shape analysis, support vector machines

Brain morphological abnormalities can typically be detected by advanced geometrical shape analysis techniques. Recently, shape diffusion methods have proved to be very effective in providing useful descriptions for brain classification purposes. In particular, they allow the analysis of such shapes at multiple scales, but the selection of the correct range of scales remains an open issue heavily affecting the performance of methods, and it needs to be estimated adaptively for different classes of shapes. In this paper, we focus on the diffusion scale selection in order to define a robust shape descriptor for brain classification. To this end, geometric features are extracted for each scale and the best feature combination is selected by employing multiple kernel learning (MKL). In the presented experiments, we compare the shape of Thalamic regions in order to discriminate between normal subjects and schizophrenic patients. We demonstrate that MKL allows to obtain classifiers which are more accurate with respect to other competing algorithms for schizophrenia detection. Moreover, using the weights computed by the MKL algorithm, we can select at which scale the features are more effective for schizophrenia classification.

Introduction

Recent advances in geometric shape analysis have led to a larger diffusion of computational anatomy methods, aimed at characterizing or modeling the morphological variations of biological shapes. One of the typical applications is analyzing the anatomy of organs, known as being possibly affected by abnormalities due to a certain disease, of several persons in order to discriminate between normal and pathological subjects [START_REF] Giuliani | Voxel-based morphometry versus region of interest: a comparison of two methods for analyzing gray matter differences in schizophrenia[END_REF][START_REF] Agarwal | Update on the use of MR for assessment and diagnosis of psychiatric diseases[END_REF]. To this aim, effective shape analysis techniques are crucial to extract geometric features with high discriminant properties. A wide class of methods are based on the encoding of the deformation which aligns a pair of subjects, but such an approach requires the solution of a complex problem due to the non-linear registration between different shapes. More recently, new methods have been proposed to encode the shape geometric properties into a descriptor which compactly represents the whole shape, and performing the comparison by computing similarities in the descriptor space without any registration procedure. Among the shape analysis methods, diffusion geometry approaches are very promising since they are able to capture intrinsic characteristic of the shape. More specifically local geometric properties are encoded by the so-called Heat Kernel [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF] which exploits heat diffusion characteristics at a given scale. The general idea consists of gaining information about the neighborhood of a point on the shape by recording the dissipation of heat over time from that point onto the rest of the shape. The fixed time is very important since it allows to capture different kinds of information: local shape characteristics are highlighted through the behavior of heat diffusion over short time periods, and, conversely, global shape properties are observed while considering longer periods [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF][START_REF] Gebal | Shape analysis using the auto diffusion function[END_REF]. So doing, simply varying a single parameter (the time), it is possible to characterize the properties of a shape at different scales. In particular, the so called Heat Kernel Signature(HKS) [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF] has been proposed to encode simultaneously the contribution of local features for a fixed set of scales into a single shape descriptor. This general approach has been succesfully applied for object retrieval [START_REF] Bronstein | Shape Google: geometric words and expressions for invariant shape retrieval[END_REF] and brain classification [START_REF] Castellani | A new shape diffusion descriptor for brain classification[END_REF]. However, the choice of the range of the time periods to be evaluated (i.e., the scales) is critical and depends on the considered shape. In fact, for a particular shape, some scales may be highly discriminative, while some other scales should encode useless information. In this paper, we propose a new approach for integrating and selecting the contribution of geometric features collected at different scales by utilzing a Multiple Kernel Learning (MKL) approach. In general, MKL algorithms can learn a weighted combination of different kernel functions able to exploit information coming from multiple sources. In our case, the different sources are the features extracted at different scales. Therefore, several kernels are computed (i.e., one kernel per scale) and a set of weights are estimated for the kernel combination. In this fashion, we can choose the most discriminative scales by selecting those associated to the highest weights, and viceversa. Moreover, kernel combination leads to a new similarity measure which increases the classification accuracy. It is important to note that in our appraoch we aim at selecting the best shape characteristics for classification purposes, hence, our selection is driven by the performance of a Support Vector Machine (SVM) classifier. We have applied our method for brain classification in schizophrenic subjects: we have adopted a Region of Interest (ROI)-based method by analysing the shape of the Thalamic region, employing a volumetric-heat kernel computed for each voxel of the MRI scan at different scales, as described in our previous work [START_REF] Castellani | A new shape diffusion descriptor for brain classification[END_REF]. This paper improves [START_REF] Castellani | A new shape diffusion descriptor for brain classification[END_REF] for both methodological aspects, by proposing the automatic scale selection procedure and promising results. The rest of the paper is organized as follows. In Section 2, the basics on shape diffusion procedures are reported. Section 3 describes the Multiple Kernel Lerning strategy, and the proposed method is reported in Section 4. Results are shown in Section 5 and conclusions are finally drawn in Section 6.

Shape analysis by heat diffusion

Considering a shape M as a compact Riemannian manifold [START_REF] Bronstein | Shape recognition with spectral distances[END_REF], the heat diffusion on shape5 is defined by the heat equation:

(∆ M + ∂ ∂t )u(t, m) = 0; ( 1
)
where u is the distribution of heat on the surface, m ∈ M , ∆ M is the Laplace-Beltrami operator which, for compact spaces, has discrete eigendecomposition of the form ∆ M = λ i φ i . In this way, the heat kernel has the following eigendecomposition:

h t (m, m ) = ∞ i=0 e -λit φ i (m)φ i (m ), (2)
where λ i and φ i are the i th eigenvalue and the i th eigenfunction of the Laplace-Beltrami operator, respectively. The heat kernel h t (m, m ) is the solution of the heat equation with initial point heat source in m at time t = 0, and heat value in ending point m ∈ M after time t. The heat kernel is isometric invariant, it is informative, and stable [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF].

In the case of volumetric representations, the volume is sampled by a regular Cartesian grid composed by voxels, which allows the use of standard Laplacian in R 3 as the Laplace-Beltrami operator. We use finite differences to evaluate the second derivative in each direction of the volume. The heat kernel on volumes is invariant to volume isometries, in which shortest paths between points inside the shape do not change. Note that in real applications exact volume isometries are limited to the set of rigid transformations [START_REF] Raviv | Volumetric heat kernel signatures[END_REF], however, also non-rigid deformations can faithfully be modelled as approximated volume isometries in practice. It is also worth noting that, as observed in [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF][START_REF] Raviv | Volumetric heat kernel signatures[END_REF], for small t the autodiffusion heat kernel h t (m, m) of a point m with itself is directly related to the scalar curvature s(m) [START_REF] Raviv | Volumetric heat kernel signatures[END_REF]. More formally:

h t (m, m) = (4πt) -3/2 (1 + 1 6 s(m)). (3)
In practice, Equation 3 states that the heat tends to diffuse slower at points with positive curvature, and viceversa. This gives an intuitive explanation about the geometric properties of h t (m, m), and suggests the idea of using it to build a shape descriptor [START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF].

Multiple Kernel Learning

The main idea behind kernel methods [START_REF] Vapnik | Statistical learning theory[END_REF] is to transform the input feature space to another space (eventually with a larger dimension) where the classes are linearly separable. In particular, by employing the SVM classifier, the discriminant function after the training phase becomes f (x) = w, Φ(x) + b, where w and b are the parameters of the hyperplane which separates two classes, and Φ( • ) is the mapping function. Using the dual formulation and the kernel trick, one does not have to define this mapping function explicitly and the discriminant function can be written as

f (x) = N i=1 α i y i k(x i , x) + b (4)
where k(x i , x j ) = Φ(x i ), Φ(x j ) is the kernel function that calculates a similarity metric between data instances. More recently, MKL methods have been proposed [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF][START_REF] Lanckriet | Learning the kernel matrix with semidefinite programming[END_REF] for learning a combination k η of several kernels:

k η (x i , x j ; η) = f η ({k m (x m i , x m j ) P m=1 }; η) (5)
where the combination function f η forms a single kernel from P base kernels using the parameters vector (i.e., weights) η. Such new kernel must be a valid kernel 6 [9] and can be plugged in Equation 4for classification purposes. Different kernel functions correspond to different notions of similarity and instead of searching which works best, the MKL method does the picking for us, or may use a combination of kernels. MKL also allows us to combine different representations, possibly coming from different sources or modalities.

There is significant work on the theory and application of MKL, and most of the proposed algorithms differ among them by the optimization method employed to estimate the weights and by the used combination rule [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF][START_REF] Lanckriet | Learning the kernel matrix with semidefinite programming[END_REF][START_REF] Rakotomamonjy | SimpleMKL[END_REF]. In this paper we focus on linear -MKL methods [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF][START_REF] Lanckriet | Learning the kernel matrix with semidefinite programming[END_REF], whose general formulation is defined as:

k η (x i , x j ; η) = P m=1 η m k m (x m i , x m j ) (6)
with η m ∈ R. As a simplest combination approach, the so called fixed rules [START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-based Learning Methods[END_REF] use the combination function in Eq. ( 6) with all weights equally set to η m = 1.

Similarly, the mean-rule takes the mean of the kernels by setting all η m = 1/P . Indeed, in the most general case the weights η m are automatically estimated by a learning by example approach. More specifically, MKL methods search for a combination of kernels that maximizes a generalized performance measure (i.e, maximum margin classification errors [START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-based Learning Methods[END_REF]). To this aim, in the training phase, both MKL weights and SVM parameters are simultaneously estimated within the same optimization problem.

The Proposed Method

The proposed method can be summarized in the following main steps:

1. MRI data collection. MRI data collection. In order to employ a learning-by-example approach, we need a collection of samples for both healthy subjects and patients. Source data are MRI scans where shape information can be provided in terms of volumetric data.

Feature extraction at multiple scales. According to the shape diffusion analysis described in Section 2, for each subject geometric features are extracted at multiple scales: a set of time values (t 1 , t 2 , • • • , t n ) are defined, and the autodiffusion value is computed for each voxel m, leading to:

H ti (M ) = {h ti (m, m), ∀m ∈ M }.
Then, such values are accumulated into a histogram r i = hist(H ti (M )). In this manner, we obtain a set of n sources of shape representation {r 1 , • • • , r n }, each one encoding the global shape at a certain scale. The number of bins for each histogram is chosen as 100.

Learning weights and classifier by MKL. The contribution of geometric features extracted at each scale are combined by employing the MKL strategy as described in 3. Each shape representation r i is associated to a kernel k m by leading to n = P kernels. Indeed, both the weights (η 1 • • • η P ) and the SVM parameters are estimated. In order to obtain the best classification accuracy according to the max-margin paradigm an alternating approach is used between the optimization of kernel weights and the optimization of the SVM classifier. In each step, given the current solution of kernel weights, MKL solves a standard SVM optimization problem with the combined kernel. Then, a specific procedure is applied to update the kernel weights.

Scale selection and performance evaluation. Once the MKL procedure is completed, we obtain a two-fold advantage: i) we can select the best scale contributions by keeping only the scales associated to the highest weighs, and ii) we can compose a new kernel from the weighted contributions of the best scales, which can be evaluated for classification purposes.

Experiments

This section is organized in the following parts: i) data gathering, ii) experimental methodology, iii) results, and iv) discussion.

Data Gathering

Quantitative data collection and processing in MRI-based research implies to face several methodological issues to minimize biases and distortions. The standard approach to deal with these issues is following well-established guidelines dictated by international organizations, such as the World Health Organization (WHO), or codified by respected institutions, such as leading universities. All patients received a diagnosis of schizophrenia according to the criteria of the Diagnostic and Statistical Manual of Mental Disorders [START_REF]American Psychiatric Association: Diagnostic and statistical manual of mental disorders, DSM-IV[END_REF]. In this work, we employ a ROI-based approach [START_REF] Giuliani | Voxel-based morphometry versus region of interest: a comparison of two methods for analyzing gray matter differences in schizophrenia[END_REF], so only a well defined brain subpart has been considered in this study. More specifically, we focus our analysis on the left-Thalamus whose abnormal activity has been already investigated in schizophrenia [START_REF] Corradi-Dellacqua | Thalamic-insular dysconnectivity in schizophrenia: Evidence from structural equation modeling[END_REF]. ROIs have been manually traced by experts, according to well defined medical protocols. The data set used in this work is composed by MRI brain scans of 30 patients affected by schizophrenia and 30 healthy control subjects.

Experimental protocol

In our experiments, we apply leave-one-out (LOO) cross-validation to assess the performance of the technique. Since LOO is used as the cross validation technique, we do not report standard deviations or variances. We compare our results using k-fold paired t-test at p = 0.05. We collect geometric features at 11 scales generating different shape representations r 01 , • • • , r 11 . In practice, each representation r i is a feature vector x i which is plugged in the MKL framework. We employ the dot product as basic kernel function (i.e., linear kernel) since it avoids the estimation of free kernel parameters. Different strategies to combine the different shape representations have also been evaluated:

-Single Best Kernel (Single-best): an SVM is trained separately per each representation. Therefore, the performance of the classification are evaluated separately at each scale. So doing, we can evaluate the independent contributions coming from the different sources of information and select the best one.

-Feature concatenation (SVM-con): the contributions coming from the different sources are concatenated into a single feature vector. Then, a single SVM is employed for classification 7 . -Rule-based MKL (RBMKL): as baseline MKL approach, the so called rulebased method is evaluated: the kernels computed at each scale are combined by simply taking their average (i.e., ∀m, η m = 1/P ). -Simple MKL (SimpleMKL): a simple but effective MKL algorithm is employed [START_REF] Rakotomamonjy | SimpleMKL[END_REF] by addressing the MKL problem through a weighted 2-norm regularization formulation with additional constraint on the weights that encourages sparse kernel combination. It is a popular approach and its code is publicly available8 . -Group Lasso MKL (GLMKL): it denotes the group Lasso-based MKL algorithms proposed by [START_REF] Kloft | lp-norm multiple kernel learning[END_REF][START_REF] Xu | Simple and efficient multiple kernel learning by group Lasso[END_REF]. A closed form solution for optimazing the kernel weights based on the equivalence between group-lasso and MKL is proposed.

In our implementation, we used l 1 -norm on the kernel weights and learned a convex combination of the kernels.

Results

The first evaluation scores are shown in Table 1, which reports the single-best kernel accuracies for all feature representations. We can observe that the best performance is obtained at 78.33 % using r02 which is shown as bold face in the table. The entries marked with "*" show the accuracies which are statistically significantly less accurate than the best algorithm using k-fold paired t-test at p = 0.05. Second, concatenating the features in a single vector leads to 83.33 % accuracy.

Third, using the proposed three different MKL algorithms, we combined the eleven kernels by introducing the weights η m . Table 2 reports the results of the best single-kernel SVM, the accuracy of the concatenated feature set, and the three MKL-based algorithms trained. The values in parantheses show the percentage of controls classified as schizophrenia and the percentage of patients classified as healthy respectively. We achieve an accuracy of 86.67%, reached by combining eleven kernels with the SimpleMKL approach. This result is better than all other MKL settings and single-kernel SVMs. Further, GLMKL achieves 85% accuracy which is still higher than that reached by the feature concatenation method. We can also note that we cannot overcome SVM-con when we use RBMKL, as the latter gives equal weight to each kernel. In fact, if there are inaccurate representations in the given set, the overall mean combination accuracy may be less of that reached using the single best. Conversely, when the weights are automatically estimated, such as in SimpleMKL and GLMKL the selection of the most reliable information is carried out by the MKL procedure and the overal performance improves. In Figure 2, we plotted the weights of MKL for both SimpleMKL and GLMKL algorithms. Note that the estimated weights are coherent in the two algorithms. As expected, the best representation is r02, which has the highest weights. Although the other representations with high weights (r08, r11 and r05) do not provide much accurate single-kernel SVMs results, their contributions to the overall accuracy in the combination is higher than those given by the other kernels. This demonstrates that when considering combinations, even a representation which does not lead to very precise results may contribute to raise the overall combination accuracy. Moreover, we can also deduce that these four representations are the most useful in discriminating between healthy and schizophrenic subjects, and we may focus the attention on these properties only.

Using this information, we also performed the above pipeline using only these four representations, and we can observe the results in Table 3. Using this subset, we get the highest accuracy with SimpleMKL9 , reaching 88.33% of accuracy. We can also observe an increase in RBMKL.

Discussion

In this work, we have shown in general that MKL algorithms perform better than both single-best kernel SVMs and feature concatenation strategies. We have also observed that RBMKL (which does not compute weights while combining kernels) does not outperform the feature concatenatenation approach. Conversely, when the kernel combination is carried out by estimating proper weights, a drastic improvement is instead obtained. The kernel weights also allow us to extract useful information: it is interesting to observe that, for both MKL algorithms with the highest accuracy, four representations have the maximum effect (i.e., the highest weights), i.e., r02, r08, r11, and r05, with r02 being the best singlekernel. We use this information to select a smaller number of representations to reduce the costs of the feature extraction phase. Finally, we can also observe that by using such subset we can reach the best accuracy overall.

Conclusions

In this paper, we focus on scale selection for anatomical shape characterization. By employing a shape diffusion approach, we extract several shape descriptors at different scales in order to discriminate between healthy subjects and patients affected by schizophrenia. We have shown that machine learning techniques can be useful to improve the shape analysis in these (biomedical) contexts. We propose a Multiple Kernel Learning algorithm for the automatic estimation of the best feature representation for classification purposes. In this way, being driven by the training data, we are able to choose the scales of the heat kernel which are more suitable to describe our kind of shapes. In particular, in our experiments addressing the Thalamic region classification, we have shown that both small and high scales are crucial. Actually, the best accuracy is observed at r02 for which very local information are collected from the shape. Nevertheless, when also higher scales are considered the performance is further improved, meaning that also global shape information is relevant.

2 .

 2 Feature extraction at multiple scales. 3. Learning weights and classifier by MKL. 4. Scale selection and performance evaluation.

Fig. 1 .

 1 Fig. 1. General scheme of the proposed method.

Fig. 2 .

 2 Fig.2. Combination weights in MKL using the linear kernel. Top: using SimpleMKL, Bottom: using GLMKL.

Table 1 .

 1 Single-kernel SVM accuracies.

	r01 r02 r03 r04 r05	r06 r07 r08 r09 r10 r11
	75.00 78.33 76.67 76.67 73.33 *66.67 68.33 70.00 76.67 71.67 70.00

Table 2 .

 2 MKL accuracies (false positives and negatives are reported in brackets).

	Single-best	SVM-con	RBMKL	SimpleMKL	GLMKL
	*78.33 (10, 11.6) 83.33 (8.3, 8.3) *81.67 (10, 8.3) 86.67 (6.6, 6.6) 85.00 (8.3, 6.6)

Table 3 .

 3 MKL accuracies on the selected subset of representations (false positives and negatives are reported in brackets).

	SVM	SVM-con	RBMKL	SimpleMKL	GLMKL
	*78.33 (10, 11.6) *83.33 (6.6, 10) *83.33 (6.6, 10) 88.33 (6.6, 5) 85.00 (6.6, 8.3)

In this section, we borrow the notation from[START_REF] Sun | A concise and provably informative multi-scale signature based on heat diffusion[END_REF][START_REF] Bronstein | Shape recognition with spectral distances[END_REF]

The validity of the kernel depends by the combination function.

We use LIBSVM software[START_REF] Chang | LIBSVM: a library for support vector machines[END_REF] to train the SVM.

http://asi.insa-rouen.fr

Note that in principle the same result should have been obtained automatically from MKL algorithms on all representations. In practice, this is not the case in our experiment due to the fact that the estimated solution is trapped into a local minimum.

Acknowledgements

We acknowledge financial support from the FET programme within the EU FP7, under the SIMBAD project (contract 213250). We thank Dr. Mehmet Gönen for the implementation of the MKL algorithms.


Luc Bouganim
email: luc.bouganim@inria.fr

Björn Þór Jónsson

Philippe Bonnet
email: bonnet@diku.dk

uFLIP: Understanding Flash IO Patterns

Keywords: B.3.2 [Memory Structures]: Design Styles -mass storage (flash devices); B.8.2 [Performance and Reliability]: Performance Analysis and Design Aids Measurement, Performance, Experimentation Flash devices, benchmarking, methodology, uFLIP

Does the advent of flash devices constitute a radical change for secondary storage? How should database systems adapt to this new form of secondary storage? Before we can answer these questions, we need to fully understand the performance characteristics of flash devices. More specifically, we want to establish what kind of IOs should be favored (or avoided) when designing algorithms and architectures for flash-based systems. In this paper, we focus on flash IO patterns, that capture relevant distribution of IOs in time and space, and our goal is to quantify their performance. We define uFLIP, a benchmark for measuring the response time of flash IO patterns. We also present a benchmarking methodology which takes into account the particular characteristics of flash devices. Finally, we present the results obtained by measuring eleven flash devices, and derive a set of design hints that should drive the development of flash-based systems on current devices.

INTRODUCTION

Tape is dead, disk is tape, flash is disk [START_REF] Gray | Tape is dead, disk is tape, flash is disk, RAM locality is king[END_REF]. The flash devices that now emerge as a replacement for mechanical disks are complex devices composed of flash chip(s), controller hardware, and proprietary software that together provide a block device interface via a standard interconnect (e.g., USB, IDE, SATA). Does the advent of such flash devices constitute a radical departure from hard drives? Should the design of database systems be revisited to accommodate flash devices? Must new systems be designed differently to take full advantage of flash device characteristics?

In trying to answer these questions, a tempting short-cut is to assume that flash devices behave as the flash chips they contain. Flash chips are indeed very precisely specified, they have interesting properties (e.g., read/program/erase operations, no updates in-place, random reads equivalent to sequential reads), and many researchers have used their characteristics to design new algorithms [START_REF] Lee | Design of flash-based DBMS: An inpage logging approach[END_REF] [START_REF] Nath | Dynamic self-tuning database for NAND flash[END_REF] [START_REF] Wu | An efficient B-tree layer implementation for flash-memory storage systems[END_REF]. The problem is, however, that commercially available flash devices do not behave as flash chips. They provide a block interface, where data is read and written in fixed sized blocks and integrate layers of software that manage block mapping, wear-leveling and error correction. As a consequence, flash devices do not provide explicit erase operations, and there is, a priori, no reason to avoid in-place updates. In terms of performance, flash devices are also much more complex than flash chips. For instance, block writes directed to the flash devices are mapped to program and erase operations at different granularities and as a result the performance of writes is not uniform in time. It would therefore be a mistake to model flash devices as flash chips.

So, how can we model flash devices? The answer is not straightforward because flash devices are both complex and undocumented. They are black boxes from a system's point of view.

Understanding Flash Devices

A first step towards the modeling of flash devices is to have a clear and comprehensive understanding of their performance. The key issue is to determine the kinds of IOs (or IO sequences) that should be favored (or avoided) when designing algorithms and architectures for flash-based systems.

In order to study this issue, we need a benchmark that quantifies the performance of flash devices. By applying such a benchmark to current and future devices, we can start making progress towards a comprehensive understanding. While individual devices are likely to differ to some extent, the benchmark should reveal common behaviors that will form a solid foundation for algorithm and system design. In this paper, we propose such a benchmark. Defining a benchmark for flash devices is not a trivial task, however. Since the behavior of flash devices is determined by layers of undocumented software, we cannot make any safe assumptions. This has three main consequences. First, to capture the performance characteristics we must define a broad benchmark that casts light on all relevant usage patterns. Second, since the space of relevant usage patterns is large, we must focus on simple measurements that are easily analyzed. Last, the complex behavior calls for sound benchmarking methodology.

Recently, there has been increasing awareness of the importance of benchmarking activities in general, and benchmarking methodologies in particular (e.g., see [START_REF] Blackburn | Wake up and smell the coffee: Evaluation methodology for the 21st century[END_REF][13]). For example, it has been demonstrated that incorrect benchmarking methodology may lead to distorted benchmark results [START_REF] Blackburn | Wake up and smell the coffee: Evaluation methodology for the 21st century[END_REF] [START_REF] Trayger | A nine year study of file system and storage benchmarking[END_REF]. In this paper, we therefore put significant emphasis on devising a sound benchmarking methodology for flash devices.

Related Work

So far, only a handful of papers have attempted to understand the overall performance of flash devices. Lee et al. focused on benchmarking SSD performance for typical database access patterns, but used only a single device for their measurements [START_REF] Lee | A case for flash memory SSD in enterprise database applications[END_REF]. Myers measured the performance of database workloads over two flash devices [START_REF] Myers | On the use of NAND flash memory in highperformance relational databases[END_REF]. In comparison, our benchmark is not specific to database systems. We study a variety of IO patterns, defined as the distribution of IOs in time and space.

Ajwani et al. analyzed the performance of a large number of flash devices, but using ad-hoc methodology [START_REF] Ajwani | Characterizing the performance of flash memory storage devices and its impact on algorithm design[END_REF]. By contrast, we identify benchmarking methodology as a major challenge. It is indeed very easy to get meaningless results when measuring a flash device because of the non-uniform nature of writes. Huang et al. attempted an analysis of flash device behavior, but neither proposed a complete methodology nor made measurements [START_REF] Huang | The behavior analysis of flash-memory storage systems[END_REF]. There are thus no relevant flash device benchmarks.

Many existing benchmarks aim to measure disk performance (see [START_REF] Trayger | A nine year study of file system and storage benchmarking[END_REF] for an excellent survey and critique). None of those benchmarks, however, accounts for the non-uniform performance of writes that characterizes flash devices.

Contributions of the Paper

This paper makes the following three major contributions:

1. We define the uFLIP benchmark (Section 3), a component benchmark for understanding flash device performance. uFLIP is a collection of nine micro-benchmarks defined over IO patterns.

2. We define a benchmarking methodology (Section 4) that accounts for the complex and non-uniform performance of flash devices.

3. We apply the uFLIP benchmark to a set of eleven flash devices (Section 5), ranging from low-end to high-end devices. Based on our results, we discuss a set of design hints that should drive the development of flash-based systems on current devices.

We believe that the investigation of flash device behavior deserves strong and continuous effort from the research community; an effort that we instigate in this paper. Therefore, the uFLIP software and the detailed results (tens of millions of data points) are available on a web site (www.uflip.org) that we expect to be used and completed by the community.

FLASH DEVICES

The uFLIP benchmark is focused on flash devices-such as solid state disks (SSDs), USB flash drives, or SD cards-which are packaged as block devices. As Figure 1 below illustrates, flash devices contain flash chips and controllers whose role is to provide the block abstraction at the flash device interface. While the details of flash devices vary significantly, there are certain common traits in the architecture of the flash chips and of the block manager that impact their performance and justify our focus on IO patterns [START_REF] Gal | Algorithms and data structures for flash memories[END_REF]. In this section we review those common traits.

Flash Chips

A flash chip is a form of EEPROM (Electrically Erasable Programmable Read-Only Memory), where data is stored in independent arrays of memory cells. Each array is a flash block, and rows of memory cells are flash pages. Flash pages may furthermore be broken up into flash sectors.

Each memory cell stores 1 bit in single-level cell (SLC) chips, or 2 or more bits in multi-level cell (MLC) chips. MLC chips are both smaller and cheaper, but they are slower and have a shorter expected life span. By default each bit has the value 1. It must be programmed to take the value 0 and erased to go back to value 1. Thus, the basic operations on a flash chip are read, program and erase, rather than read and write.

Flash devices designed for secondary storage are all based on NAND flash, where the rows of cells are coupled serially, meaning that data can only be read and programmed at the granularity of flash pages (or flash sectors).Writes are performed one page (or sector) at a time, and sequentially within a flash block in order to minimize write errors resulting from the electrical side effects of writing a series of cells.

Erase operations are only performed at the granularity of a flash block (typically 64 flash pages). This is a major constraint that the block manager must take into account when mapping writes onto program and erase commands. Most flash chips can only support up to 10 5 erase operations per flash block for MLC chips, and up to 10 6 in the case of SLC chips. As a result, the block manager must implement some form of wear-leveling to distribute the erase operations across blocks and increase the life span of the device. To maintain data integrity, bad cells and worn-out cells are tracked and accounted for. Typically, flash pages contain 2KB of data and a 64 byte area for error correcting code and other bookkeeping information.

Modern flash chips can be composed of two planes, one for even blocks, the other for odd blocks. Each flash chip may contain a page cache. The block manager should leverage these forms of parallelism to improve performance.

Block Manager

In all flash devices, the core data structures of the block manager are two maps between blocks, represented by their logical block addresses (LBAs), and flash pages. A direct map from LBAs to flash pages is stored on flash and in RAM to speed up reads, and an inverse map is stored on flash, to re-build the direct map during recovery. There is a trade-off between the improved read performance due to the direct map and degraded write performance due to the update of the inverse map (updates of bookkeeping information for a page may cause an erase of an entire block).

The software layer responsible for managing these maps both in RAM (inside the micro-controller that runs the block manager) and on flash is called flash translation layer (FTL). Using the direct map, the FTL introduces a level of indirection that allows trading expensive writes-in-place (with the erase they incur) for cheaper writes onto free flash pages.

Each update on a free flash page, however, leaves an obsolete flash page (that contains the before image). Over time such obsolete flash pages accumulate, and must subsequently be reclaimed synchronously or asynchronously. As a result, we must assume that the cost of writes is not homogeneous in time (regardless of the actual reclamation policy). Some block writes will result in flash page writes with a minimum bookkeeping overhead, while other block writes will trigger some form of page reclamation and the associated erase. Assuming a flash device contains enough RAM and autonomous power, the flash translation layer might be able to cache and destage both data and bookkeeping information.

The density of NAND flash chips is doubling every year [START_REF] Shah | Microsoft in talks to speed up SSDs on Vista[END_REF]. As a result, the capacity of flash devices increases exponentially. This has a direct impact on the size of the direct map from LBAs to flash pages. If the direct map does not fit in RAM, then the cost of reads will also become non-uniform in time as portions of the map will need to be swapped in to complete a look-up. Conversely, the increase in storage capacity has no direct impact on the distribution of expensive writes as obsolete pages still must be reclaimed to guarantee constant flash capacity. Flash device constructors might be able to use a larger fraction of the storage space for bookkeeping, which can mitigate the need to reclaim pages.

Device State and IO Patterns

While the principles of the flash translation layer described above are well known, the details of the design decisions made for a given flash device, and the associated performance trade-offs, are typically not documented: Flash devices are black-boxes.

Since the physical layout of data on flash devices is stored and manipulated via the direct map data structure, which manages the devices at some fixed granularity, there is no direct correspondence between an arbitrary IO request to the flash device and its translation to a physical request to a flash chip. Instead, the physical request is based in a complex manner on the current state of the direct map, which in turn is based on the entire history of previous IO requests.

This circular dependency makes benchmarking flash devices particularly hard. The main factors that impact performance are thus the device state and the distribution of incoming IO requests in space (i.e., their LBA) and time, or IO patterns. The goal of the uFLIP benchmark is to characterize the relevant IO patterns and, given a well defined device state, how they impact performance.

THE uFLIP BENCHMARK

In this section we propose uFLIP, a new benchmark for observing and understanding the performance of flash devices.

The uFLIP benchmark is a set of micro-benchmarks based on IO patterns. In theory, IO patterns can be arbitrarily complex. In uFLIP, we focus on a set of potentially relevant IO patterns defined through a small set of baseline patterns, functions and parameters. These IO patterns are described in Section 3.1.

The IO patterns thus defined still cover a very large design space, some of which is not useful for analysis. We have therefore used three design principles to further narrow the uFLIP benchmark to a set of nine micro-benchmarks. The details of these nine microbenchmarks are given in Section 3.2.

We believe that the nine uFLIP micro-benchmarks together capture the characteristics of flash devices quite well. In Section 3.3 we further argue that they form a benchmark that fulfils key quality criteria defined in the literature.

Defining IO Patterns

The basic construct of uFLIP is an IO pattern, which is simply a sequence of IOs. In each pattern, we refer to the i th submitted IO as IO i . Each IO is (as usual) defined by four attributes: In theory, IO patterns can be arbitrarily complex, as arbitrary functions can be used to generate the four attributes. We define four baseline patterns as sequential reads, sequential writes, random reads, and random writes for consecutive IOs of a given size; these are the patterns typically used in practice. In order to increase the range of relevant patterns for our benchmark, however, we introduce a few simple parameterized functions:

•

The time, t(IO i ), is defined through one of three different functions: a) consecutive, where IO i+1 starts as soon as IO i finishes, as in the baseline patterns; b) pause(Pause), where a pause of length Pause is introduced in between all IOs; or c) burst(Pause, Burst), where a pause of length Pause is introduced between groups of Burst IOs.

Note that both the pause and consecutive functions can be defined using the burst function, as pause(p) = burst(1, p) and consecutive = burst(0, -). We feel, however, that the pause and consecutive functions are important enough to be considered separately.

• IOSize(IO i ) is simply defined as the identity function over the parameter IOSize.

•

The location of the IO, LBA(IO i ) is defined through one of four different functions: a) sequential; b) random; c) ordered(Incr), where a linear increment (or decrement) is applied to each LBA in the pattern, determined by the linear coefficient Incr; or d) partitioned(Partitions), where we divide the target space into Partitions partitions which are considered in a round robin fashion; within each partition IOs are sequential.

For each of these functions, the address is first computed assuming an alignment to IOSize boundaries, and relative to a specified target location on the flash device (TargetOffset). Additionally, we must specify the size of the target space of the IO pattern (TargetSize) and whether the IO is indeed aligned or not (IOShift).

• Lastly, Mode(IO i ) is a constant function yielding two values, read or write.

The uFLIP Micro-Benchmarks

Even with the restrictions that we have introduced, the space of potentially relevant IO patterns is far too large to be explored exhaustively. To further reduce the complexity of the benchmark, we adopt the following design principles:

1. An execution of a reference pattern against a device is called a run. For each run, we measure and record the response time for individual IOs1 and compute statistics (min, max, mean, standard deviation) to summarize it.

A collection of runs of the same reference pattern is called an experiment. To enable sound analysis of an experiment's results (set of computed statistics), we design each experiment around a single varying parameter. 22. We then define a micro-benchmark as a collection of related experiments over the baseline patterns. The experiments of the same micro-benchmark thus have the same varying parameter, and the same value for all other functions and parameters. This gives a total of nine micro-benchmarks, as follows:

Considering the basic pattern parameters (one of IOSize, IOShift, TargetSize, Partitions, Incr, Pause, or Burst) yields seven micro-benchmarks.

Since mixed patterns need parameters to control the mix, restricting to varying a single parameter allows us to mix only the baseline patterns. This leads to one more microbenchmark with six combinations of baseline patterns, controlled by a Ratio parameter.

Similarly, in order to focus only on one parameter, ParallelDegree, for parallel patterns, we choose to replicate only the four baseline patterns to implement parallelism.

3. Each micro-benchmark is based on the four baseline patterns, departing from the baseline patterns only to accommodate the particular parameter being varied.

We now define the nine uFLIP micro-benchmarks by describing informally the sets of reference patterns and the parameter that is varied. Table 1 fully specifies every micro-benchmark with a formula for the four IO attributes, as well as the name and range of the relevant parameters. In the table, we first give the formulas for the baseline patterns and then focus on the changes required to accommodate the varying parameter in each case. We present the micro-benchmarks by first considering location parameters, then parallel and mixed patterns, and end with the timing parameters.

Granularity (IOSize):

The flash translation layer manages a direct map between blocks and flash pages, but the granularity at which this mapping takes place is not documented. The IOSize parameter allows determining whether a flash device favors a given granularity of IOs. 2. Alignment (IOShift): Using a fixed IOSize (e.g., chosen based on the first micro-benchmark), we study the impact of alignment on the baseline patterns by introducing the IOShift parameter and varying it from 0 to IOSize.

SR RR SR RW SR SW RR SW RR RW SW RW 2 SR / 1 RR 3 SR / 1 RW 4 SR / 1 SW Mix Ratio (#1/#2) [2 0 , …, 2 6 ] 1 RR / 1 SW 2 RR / 1 RW 4 SW / 1 RW t(IO i ) t (IOi-1) + rt(IOi-1) + Pause Pause Pause [2 0 , …,

Partitioning (Partitions):

The partitioned patterns are a variation of the sequential baseline patterns. We divide the target space into Partitions partitions which are considered in a round robin fashion; within each partition IOs are performed sequentially. This pattern represents, for instance, a merge operation of several buckets during external sort.

Order (Incr):

The order patterns are another variation on the sequential patterns, where logical blocks are addressed in a given order. For the sake of simplicity, we consider a linear increase (or decrease) in the LBAs addressed in the pattern, determined by a linear coefficient Incr. We can thus define a) patterns with increasing LBAs (Incr > 1) or decreasing LBAs (Incr < 0), or b) in-place patterns (Incr = 0) where the LBA remains the same throughout the pattern.

These mapping are simple, yet important and representative of different algorithmic choices: for example, a reverse pattern (Incr = -1) represents a data structure accessed in reverse order when reading or writing, the in-place pattern is a pathological pattern for flash chips, while an increasing LBA pattern represents the manipulation of a pre-allocated array, filled by columns or lines.

6. Parallelism (ParallelDegree): Since flash devices include many flash chips (even USB flash drives typically contain two flash chips), we want to study how they support overlapping IOs. We divide the target space into ParallelDegree subsets, each one accessed by a process executing the same baseline pattern. We vary the parameter ParallelDegree to study how well the flash device supports parallelism, and thus how asynchronous IO should be scheduled and how parallelism should be managed.

Mix (Ratio):

We compose any two baseline patterns, for a total of six combinations. We vary the ratio to study how such mixes differ from the baselines.

8. Pause (Pause): This is a variation of the baseline patterns, where IOs are not contiguous in time. We use the pause function and vary the Pause parameter to observe whether potential asynchronous operations from the flash device block manager impact performance. 9. Bursts (Burst): This is a variation of the previous microbenchmark, where the Pause parameter is set to a fixed length (e.g. 100 msec). The Burst parameter is then varied to study how potential asynchronous overhead accumulates in time.

Discussion

Even though uFLIP is not a domain-specific benchmark, it should still fulfill the four key criteria defined in the Benchmarking Handbook: portability, scalability, relevance and simplicity [START_REF] Gray | The Benchmark Handbook for Database and Transaction Systems[END_REF].

Because uFLIP defines how IOs should be submitted, uFLIP has no adherence to any machine architecture, operating system or programming language: uFLIP is portable.

Also, uFLIP does not depend on the form factor of flash device being studied, and we have indeed run uFLIP on USB flash drives, SD cards, IDE flashes and SSD drives: uFLIP is scalable.

We believe uFLIP is relevant for algorithm, system and flash designers because the nine micro-benchmarks reflect flash device characteristics as well as the characteristics of the software that generates IOs. It is neither designed to support decision making nor to reverse engineer flash devices.

Whether uFLIP satisfies the criteria of simplicity is debatable. The benchmark definition itself is quite simple, and indeed we have reduced an infinite space of IO patterns down to nine microbenchmarks that define how IOs are submitted using very simple formulas and parameters.

On the other hand, our decision to measure response time for each submitted IO means that the benchmark results are very large and analyzing those results is not straightforward. We felt, however, that requiring such analysis is fundamental to achieving our goal of understanding the flash device performance. We have therefore designed a visualization tool that facilitates interactive result analysis.

Furthermore, benchmarking flash devices is inherently far from simple, e.g., due to the impact of the device state on the performance of individual operations. The methodology we present in the next section addresses this issue.

In summary, we believe that uFLIP is as simple as possible, given the complexities of flash device benchmarking, and that further simplifications would lead to loss of understanding. We note that we have achieved this simplicity by following strictly the three design principles outlined in Section 3.2.

BENCHMARKING METHODOLOGY

Measuring flash device performance is very challenging. First, as discussed in Section 2, the state of the device impacts its performance. Second, because response time is not uniform, each experiment must be long enough to capture the performance variations of the device under study. Third, consecutive microbenchmark runs should not interfere with each other. In the remainder of this section, we discuss these challenges in detail.

Device State

In our experiments, we have observed that ignoring the state of a flash device can lead to meaningless performance measurements; we now describe the most striking example. Out-of-the-box, the Samsung SSD (see Section 5 for details) had excellent random write performance (around 1 msec for a 16KB random write, compared to around 8 msec for other SSDs). After randomly writing the entire 32GB of flash, however, the write performance decreased by almost an order of magnitude and became comparable to the other SSDs.

In order to obtain repeatable results we should run the microbenchmarks from a well-defined initial state, which is independent of the complete IO history. Since flash devices only expose a block device API, however, we cannot erase all blocks and get back to factory settings. And, because flash devices are black boxes, we cannot know their exact state. We therefore make the following assumption for the uFLIP benchmark: Writing the whole flash device completely yields a well-defined state. The rationale is that following a complete write of the whole flash device, both the direct and indirect maps managed by the FTL are filled and well-defined.

We therefore propose to enforce an initial state for the benchmark by performing random IOs of random size (ranging from 0.5KB to the flash block size, 128 KB) on the whole device. The advantage of this method is that it is quite stable, as only sequential writes disturb the state significantly. In order to limit the impact of sequential writes, we direct them to distinct target spaces (specified by TargetOffset) when running the microbenchmarks. The main disadvantage of our method is that it is slow, but since it is typically only done once this is acceptable.

The alternative, performing a complete rewrite of the device using sequential IOs of a given size, is faster but may be less stable for many devices. The reason for the increased instability is that random writes, badly aligned IOs, or IOs of different sizes, impact a sequential state much more significantly than a random state.

Studying in detail the impact of the initial state on performance is, however, a topic for future work.

Start-up and Running Phases

Consider a device where the first 128 random writes are very cheap (400 µsec), and where the subsequent random writes oscillate between very cheap (400 µsec) and very expensive (27 msec). Now, say that we run the random write baseline pattern with IOCount = 512, which would seem to be long enough. In this case, the measured time will be about 25% lower than it should be; with shorter experiments the difference is even more pronounced. As another example, running the Mix microbenchmark on Random Read and Write patterns with an IOCount of 512 will lead to entirely meaningless results when Ratio is higher than 4 (more than 4 reads for every write), as then our measurements only capture the initial, very cheap random writes. If we are not careful, in fact, we might even conclude that a readmostly workload can absorb the cost of the random writes.

We propose a two-phase model to capture response time variations within the course of a micro-benchmark run. In the first phase, which we call start-up phase, response time is cheap. Such a start-up phase can occur when expensive operations are delayed, e.g., due to buffering or lazy garbage collection. In the second phase, which we call running phase, response time is typically oscillating between two or more values.

We thus characterize each device by two parameters: start-up, which defines the number of IOs for the start-up phase, and period, which defines the number of IOs in one oscillation in the running phase. In order to measure start-up and period, we run all four baseline patterns (SR, RR, SW and RW) with a very large IOCount. By plotting the IO costs, we can then identify the two phases for each pattern and derive upper bounds across the patterns for start-up and period (note that the start-up phase may not be present, in which case start-up = 0). Furthermore, we can determine the variability in the IO times.

The impact of this two-phase model on the benchmarking methodology is twofold. First, for each experiment we must adjust IOCount to capture both the start-up phase and the running phase (a sufficiently large number of periods). Second, we must ignore the start-up phase when summarizing the results of each run, so that we can use a statistical representation (min, max, mean, standard variation) to represent the response times obtained during the running phase. We therefore select IOIgnore as long enough to cover the start-up phase and IOCount as long enough to cover a sufficient number of periods to allow for convergence to the correct average response times.

Note that the value of IOCount has a direct impact on the time it takes to run an experiment and on the flash size involved in this experiment. As we saw in the previous sub-section, we must limit the portion of flash impacted by each experiment in order to avoid resetting the initial state too often during the course of benchmarking. Overestimating IOCount thus leads to a waste of time. Underestimating IOCount, on the other hand, leads to decreased precision and possibly incorrect results. Defining a method for automatically finding an appropriate IOCount value is a topic for future work.

Once IOCount is set to an appropriate value for each experiment, we define a benchmark plan that defines a sequence of state resets and micro-benchmarks, where those experiments involving sequential writes are delayed and grouped together in such a way that their allocated target space does not overlap, meaning that state resets are inserted only when the size of the accumulated target space involved in sequential write patterns is larger than the size of the flash device. Note that for the large flash devices (32 GB) the state is in fact never reset.

No Interference

Consecutive benchmark runs should not interfere with each other. Consider a device that implements an asynchronous page reclamation policy. Its effects should be captured in the running phase defined above. We must make sure, however, that the effect of the page reclamation triggered by a given run has no impact on subsequent, unrelated runs.

To evaluate the length of the pause between runs, we rely on the following experiment. We submit sequential reads, followed by a batch of random writes, and sequential reads again. We count the number of sequential reads in the second batch which are affected by the random writes. We then use this value as a lower bound on the pause between consecutive runs. Note that when benchmarking a device with unknown properties, this is only an educated guess, and therefore we propose to significantly overestimate the length of the pause.

Another type of potential interference is due to the file system, the operating system and the device drivers on the server hosting the flash device under study. Those layers of software introduce complexity and thus tend to complicate the analysis of the benchmark results. We thus use direct IO in order to bypass the host file system and synchronous IO to avoid the parallelism features of the operating system and device drivers.3

FLASH DEVICE EVALUATION

In this section, we report on our experimental evaluation of a range of flash devices, using the uFLIP benchmark. In Section 5.1 we describe our benchmark preparation following our methodology laid out in Section 4. In Section 5.2 we present and analyze the benchmark results. Finally, in Section 5.3, we discuss a set of design hints that can be drawn from our results.

Benchmark Preparation

We ran the uFLIP benchmark on an Intel Celeron 2.5GHz processor with 2GB of RAM running Windows XP. We ran each micro-benchmark using our own FlashIO software package (available at http://www.uflip.org/flashio.html). Each experiment was run three times. As the differences in performance were typically within 5%, we report the average of the three runs.

It was quite difficult to select a representative and diverse set of flash devices, as a) the flash device market is very active, b) products are not well documented (typically, random write performance is not provided!), and c) in fact, several products differ only by their packaging. We eventually selected the eleven different devices listed in Table 2, ranging from low-end USB flash drives or SD cards to high-end SSDs 4 . While we ran the entire uFLIP benchmark for all the devices, we only present results for seven representative devices indicated with an arrow in Table 1. Detailed information and measurements for all eleven flash devices can be found at http://www.uflip.org/results.html. Random State Enforcement: As prescribed in Section 4, we first filled each device with random writes of random size to enforce a random state. The time required for this varied significantly, ranging from 5 hours for the Memoright SSD to 35 days for the Corsair USB flash drive! Although this is a significant time, it is still more efficient than enforcing a sequential state. Indeed, state enforcement is much faster with sequential state but the state also deteriorates faster as more workloads impact the state. Thus, the overall running time is longer with sequential state enforcement. In fact, sequential state enforcement on the Memoright SSD required a total formatting time of 17 hours, while a single format of 5 hours was sufficient for random state enforcement.

Start-up and Running Phases:

As also prescribed in Section 4, we then ran the baseline patterns with large IOCount to measure start-up and period for each device. Figures 3 and4 show two very representative traces from these measurements. In both figures, the x-axis shows the time in units of IO operations, while the y-axis shows the cost of each operation in msec (in logarithmic scale). 4 At the time of writing, we were still waiting for the twelfth device, the recently released Flash PCI card from Fusion-IO, advertised as reaching throughput of 600MB/s for random writes. The benchmarking results will be published on uFLIP web-site. In Figure 3, which presents the RW baseline pattern for the Mtron SSD, we can easily distinguish between the start-up phase and the running phase. The start-up phase is about 125 IOs, while the period is quite short (tens of IOs). The dashed line represents the running average of response time, including the startup phase measurements, while the solid line represents the running average of response time, excluding the start-up phase measurements. As expected, excluding the start-up phase measurements resulted in a faster and more accurate representation of response time. In Figure 4, on the other hand, which presents the SW baseline pattern for the Kingston DTI USB flash drive, there is no startup phase and the period is about 128 operations.

With respect to start-up and running phases, we can basically divide the set of tested devices into two classes. The Memoright and Mtron SSDs both have a startup phase for random writes followed by oscillations with a very small period. They do not show startup for SR, RR and SW. For these devices, care should be taken when running experiments that involve a small number of RW, especially Mix patterns, since the startup phase should be scaled-up according to the number of RW IOs.

The other nine devices have no startup phase but show small oscillations for RR, larger ones for SW and sometimes large oscillations for RW (with some impressive variations between 0.25 and 300 msec). For simplicity, we used the following rules for setting IOIgnore and IOCount. We set IOIgnore = 0 for all devices (no start-up) except the Memoright and Mtron SSDs. For the latter, we used the values 30 and 128, respectively, for experiments involving random writes and 0 for all other experiments. For the SSDs, we set IOCount to 1,024 for SR, RR and SW (very small oscillations) and to 5,120 for RW (large oscillations). We set the IOCount to 512 in all cases for slow and/or small devices (USB drives, IDE module, and SD card). Note that the values of IOIgnore and IOCount are automatically scaled by the FlashIO tool when considering mixed workloads.

Pause between Experiments: Finally, we must measure the pause required between experiments, by running a pattern of sequential reads, followed by random writes, and sequential reads again. Figure 5 shows the result of this experiment for the Mtron SSD. As before, the x-axis shows the time in units of IO operations, while the y-axis shows the cost of each operation. As Figure 5 shows, the lingering effect of the random writes lasts for about 3,000 sequential reads, corresponding to about 2.5 seconds. For this device, we therefore overestimate the pause to 5 seconds.

For all the other devices, including the other SSDs, there was no lingering impact from the random writes. The sequential reads immediately performed as well after the batch of writes as they did before the batch of writes; we therefore set the pause to 1 s (to be conservative).

Benchmark Results

Having set the stage for our benchmarking effort, we now turn to the results of the actual uFLIP micro-benchmarks. As mentioned above, we focus on the results from the seven flash devices indicated in Table 2, as they are very representative for the set. In this section, we cover the most interesting results of our analysis.

Effect of Granularity:

We first consider the performance on the Granularity micro-benchmark where IOSize is varied. We generally expect reads to be cheaper than writes because some writes will generate erase operations, and we also expect random writes to be more expensive than sequential writes as they should generate more erases.

Figure 6 shows the response time (in msec) of each IO operation for the Memoright SSD. Three observations can be made about this figure. First, all reads and sequential writes are very efficient; their response time is linear with a small latency (about 70 µsec for SR/SW and 115 µsec for RR). Second, for rather large random writes, the response time is much higher, at least 5 msec; note that, similar to Figure 3, the cost of random writes alternates between cheap writes (of similar cost to sequential writes) and extremely expensive erase operations (tens of ms). Third, small random writes are serviced much faster; apparently due to caching as four writes of 4KB take about as much time as two writes of 8KB and one write of 16KB.

In comparison, Figure 7 shows the response time for the Kingston DTI USB flash drive. In this figure, the response time of random writes is omitted, as it is a rather constant value around 260 msec.

As the figure shows, for this device the cost of sequential writes is affected strongly by the IO granularity, as smaller writes incur a significantly higher cost than writes of 32KB. Comparing the two devices, we observe that while random writes are up to a factor of five times slower than the other operations on the Memoright SSD, they are one or two orders of magnitude slower for the Kingston DTI USB flash drive. This is undoubtedly due to more advanced hardware and FTL on the Memoright SSD (Figure 1 shows that the Memoright SSD includes an FGPA, 16 MB of RAM and a condenser!).

The remaining experiments were run with IO sizes of 32KB. Furthermore, since the performance of reads is excellent, we focus largely on the performance of (random) writes. 8 shows the response time of random writes (relative to sequential writes) as the target size grows from very small (local) to very large (note the logarithmic x-axis). Our expectation was that doing random writes within a small area might improve their performance. The figure verifies this intuition, as random writes within a small area have nearly the same response time as sequential writes. The figure shows, however, that the exact effect of locality varies between devices, both in terms of the area that the random writes can cover, and in terms of their relative performance. Note that some low end USB devices (e.g., Kingston DTI) do not show any benefit by focusing random IOs in a reduced area.

Locality does not affect performance of sequential writes, until the area becomes so small that the writes become in-place writes (see below for the effect of in-place writes).

Key Characteristics:

We now turn our attention to Table 3, which succinctly summarizes some key results from several experiments. In fact, it can be argued that the results in the table describe the key characteristics of the devices, and could be used as the basis for a course classification or categorization. In the following, we will discuss the result columns from left to right. First, SR, RR, SW, RW indicate the cost of a corresponding IO operation of 32KB. These columns show that there is a large difference in performance between the USB flash drives and the other devices, but also between low-end and high-end SSDs. For the high-end SSDs, even the random write performance is quite good. In fact, as we explore more results, the high-end SSDs distinguish themselves further from the rest.

The fifth column of Table 3 indicates the effect of the Pause micro-benchmark on the random write baseline pattern. No value indicates that this had no effect, which in turn indicates that no asynchronous page reclamation is taking place. For the high-end SSDs, however, inserting a pause improves the performance of the random writes to the point where they behave like sequential writes. Interestingly, however, the length of the pause when that happens is precisely the time required on average for a random write. Thus, no true response time savings are seen by inserting this pause, as the total workload takes the same overall time regardless of the length of the pause. A similar effect is seen with the Burst micro-benchmark.

The sixth column of Table 3 summarizes the effect of Locality on random writes, which we already explored with Figure 8; it shows the size of "locality area" for random writes in MB and, in parentheses, the maximum cost of random writes within that area relative to the average cost for sequential writes.

The seventh column of Table 3 summarizes a similar effect for the Partitioning micro-benchmark. The goal of that experiment was to study whether concurrent sequential write patterns over many partitions degrade the performance of the sequential writes. The column shows the number of concurrent partitions that can be written to without significant degradation of the performance, as well as the cost of the writes relative to sequential writes to a single partition. Note that when writing to more partitions than indicated in this column, the write performance degrades significantly.

The last three columns of Table 3 investigate the Order microbenchmark. The eighth and ninth columns show the cost of the reverse (Incr = -1) and in-place (Incr = 0) patterns, respectively, compared to the cost of sequential writes. As the columns show, the effect of the in-place pattern, in particular, varies significantly between devices, ranging from time savings of about 40% for the Samsung SSD, to important performance degradation for the Kingston DTI USB flash drive. The final column shows the impact of large increments (gaps from one 1 MB to 8 MB) compared to the cost of random writes. As the column shows, for high end SSDs and for the Transcend IDE Module, the cost is twice or four times the cost of a random writes. Other Results: To give a short outline of the results of the remaining micro-benchmarks, which we have not covered in detail, we observed the following:

• Unaligned IO requests result in significant performance degradation for some devices. For instance, on the Samsung SSD, random IOs should be aligned to 16 KB, as otherwise the response time increases from 18 msec to 32 msec.

•

The Mix patterns did not affect significantly the overall cost of the workloads. This behavior is very different from hard disks, where combinations of workloads significantly affect their performance.

• Finally, we did not observe any performance improvements from submitting IOs in parallel. In fact, parallel execution with a high degree can cause multiple sequential write patterns to degenerate to random write patterns (more precisely to partitioned write patterns), with the corresponding increase in cost.

Discussion

The goal of the uFLIP benchmark is to facilitate understanding of the behavior of flash devices, in order to improve algorithm and system design against such devices. In this section we have used the uFLIP benchmark to explore the characteristics of a large set of representative devices. From our results, we draw three major conclusions.

First, we have found that with the current crop of flash devices, their performance characteristics can be captured quite succinctly with a small number of performance indicators shown in Table 3.

Second, we observe that the performance difference between the high-end SSDs and the remainder of the devices, including lowend SSDs, is very significant. Not only is their performance better with the basic IO patterns, but they also cope better with unusual patterns, such as the reverse and in-place patterns. Unfortunately, the price label is not always indicative of relative performance, and therefore designers of high-performance systems should carefully choose their flash devices.

Finally, based on our results, we are able give the following design hints for algorithm and system designers:

Hint 1: Flash devices do incur latency. Despite the absence of mechanical parts, the software layers incur some overhead per IO operation. Therefore, larger IOs are generally beneficial, even for read operations.

Hint 2: Block size should (currently) be 32KB. Based on the first hint, large block sizes are beneficial for writes, while an application of the famed five minute rule [START_REF] Graefe | The five-minute rules twenty years later, and how flash memory changes the rules[END_REF] says 4KB pages are beneficial for reads, based on prices and capacities of the high-end devices we studied. We therefore believe that 32BK is a good trade-off for those high-end devices.

Hint 3: Blocks should be aligned to flash pages. This is not unexpected, based on flash characteristics, but we have observed that the penalty paid for lack of alignment is quite severe.

Hint 4: Random writes should be limited to a focused area. Our experiments show that, for most devices, random writes to an area of 4-16MB perform nearly as well as sequential writes. Random writes to larger areas are typically expensive and should be avoided; again, however, the high-end SSDs perform much better in this regard.

Hint 5: Sequential writes should be limited to a few partitions. Concurrent sequential writes to 4-8 different partitions are acceptable; beyond that performance degrades to random writes.

Hint 6: Combining a limited number of patterns is acceptable. In the same vein, concurrent access from a few patterns does not appear to affect the performance of the individual patterns.

Hint 7: Neither concurrent nor delayed IOs improve the performance. Due to the absence of mechanical components, IO scheduling is not improved through abundance of pending asynchronous IOs. Furthermore, introducing pauses does not affect total response time.

CONCLUSION

The design of algorithms and systems using flash devices as secondary storage should be grounded in a comprehensive understanding of their performance characteristics. We believe that the investigation of flash device behavior deserves strong and continuous effort from the community: uFLIP and its associated benchmarking methodology should help define a stable foundation for measuring flash device performance. By making available online (at www.uflip.org) the benchmark specification, the software we developed to run the benchmark, and the results we obtained on eleven devices, our plan is to gather comments and feedback from researchers and practitioners interested in the potential of flash devices.

There are many avenues for future work. First, we would like to facilitate benchmarking efforts, e.g., through (semi-)automatic tuning of experiment length to ensure that the start-up period is omitted and the running phase captured sufficiently well to guarantee given bounds for the confidence interval, while minimizing the IOs issued. Similarly, (semi-)automatic methods for generating benchmark plans would be useful. Second, we are already working on a visualization interface to facilitate the analysis of benchmark results. Third, we plan to improve the uFLIP web-site, to allow the research community to submit benchmark results. And last, but not least, there are many opportunities for using the knowledge gained from the uFLIP benchmark for algorithm and system design for flash devices.

Figure 1 :

 1 Figure 1: Internal view of the Memoright 32 GB SSD

Figure 2

 2 Figure2illustrates the use of many of these functions and parameters. Figure2.a illustrates the alignment of the LBA function, the impact of the IOSize and IOShift parameters, and the response time of the IO, rt(IO i ). Figure2.b illustrates the impact of the TargetOffset and TargetSize parameters, as well as the Partitions parameter. Figure2.c, on the other hand, illustrates the impact of the Incr, Pause, and Burst parameters for a sequential pattern. Note that for each pattern, we must also specify its length (IOCount) and warm-up period (IOIgnore). Setting the TargetOffset, IOIgnore, and IOCount parameters is part of the benchmarking methodology described in Section 4.

Figure 2 .Figure 2 :

 22 Figure2illustrates the use of many of these functions and parameters. Figure2.a illustrates the alignment of the LBA function, the impact of the IOSize and IOShift parameters, and the response time of the IO, rt(IO i ). Figure2.b illustrates the impact of the TargetOffset and TargetSize parameters, as well as the Partitions parameter. Figure2.c, on the other hand, illustrates the impact of the Incr, Pause, and Burst parameters for a sequential pattern. Note that for each pattern, we must also specify its length (IOCount) and warm-up period (IOIgnore). Setting the TargetOffset, IOIgnore, and IOCount parameters is part of the benchmarking methodology described in Section 4.

•

  Mixed patterns obtained by combining basic patterns. Additional parameters are then required to control the mix of patterns. Even considering only combinations of two basic patterns results in a very large space of IO patterns, with one additional parameter required to control the mix.

•

  Parallel patterns obtained by replicating a single basic pattern with a given degree of parallelism (ParallelDegree) or by mixing, in parallel, different basic patterns.

  O i = ⎣(i/Partitions) × IOSize⎦ mod PS Partitioning Partitions [2 0 , …, 2 8 ] SR (Partitions = 1) SR (Partitions = 2) SW (Partitions = 4) LBA(IOi) Sequential patterns only Seq: TargetOffset + (Incr × i × IOSize) Order Incr [-1, 0, 2 0 , …, 2 8 ] SR (Incr = -1 ) SW (Incr = 0) SR (Incr = 4) LBA(IOi) ParallelDegree concurrent processes. For process p, TargetOffsetp = p × TargetSize / ParallelDegree TargetSize p = TargetSize / ParallelDegree

  2 8 ] × 0.1 msec SR (Pause = 0.1 ms) SW (Pause = 0.5 ms) RR (Pause = 0.5 ms) t(IO i ) t (IOi-1) + rt(IOi-1) + (i mod Burst) × Pause Bursts Pause Burst e.g., 100 ms [2 0 , …, 2 6 ] × 10 SR (Burst = 6, Pause = 0.1 s) SW (Burst = 3, Pause = 0.1 s) RR (Burst = 6, Pause = 0.1 s) 3. Locality (TargetSize): We study the impact of locality of the baseline patterns, by varying TargetSize down to IOSize.

Figure 3 :

 3 Figure 3: Starting and running phase for Mtron SSD(RW)

Figure 4 :Figure 5 :

 45 Figure 4: Running phase for Kingston DTI

Figure 6 :

 6 Figure 6: Granularity for Memo

Figure 7 :Figure 8 :

 78 Figure 7: Granularity for Kingston DTI (SR,RR,SW)

Table 1 : Micro-Benchmark definitions

 1

	Micro-benchmark	Attribute	Pattern Definitions	Examples
	Baseline patterns	t(IO i )	consecutive: t(IO i-1 ) + rt(IO i-1 )
		IOSize(IO i )	constant (32 KB in our experiments)
		LBA(IOi)	Rnd: TargetOffset + random(TargetSize/IOSize) × IOSize
			Seq: TargetOffset + i × IOSize
		Mode(IO i )	read | write
	Granularity	IOSize(IOi)	IOSize
		IOSize	[2 0 , …, 2 9 ] × 512B (plus some non-powers of 2)	SW (IOSize = 8 KB)	SW (IOSize = 32 KB)	RR (IOSize = 8 KB)
	Alignment	LBA(IOi)	Rnd: TargetOffset + IOShift +
			random(TargetSize/IOSize) × IOSize
			Seq: TargetOffset + IOShift + i × IOSize
		IOShift	[2 0 , …, IOSize/512] × 512B
				SW (IOShift = 512 B)	SW (IOShift = 16 KB)	RR (IOShift = 16 KB)
	Locality	LBA(IO i )	Rnd: Unchanged
			Seq: TargetOffset + (i × IOSize) mod TargetSize
		TargetSize	Rnd: [2 0 , …, 2 16 ] × IOSize
			Seq: [2 0 , …, 2 8 ] × IOSize
				RR (Target Size = 4×IO Size)	SW (Target Size = 8×IO Size )	RR (Target Size = 32×IO Size)
		LBA(IO i )	Sequential patterns only
			Seq: P

i × PS + O i where PS = TargetSize/Partitions Pi = i mod Partitions

Table 2 : Selected flash devices

 2

	Brand	Model	Type	Size	Price
	Memoright	MR25.2-032S	SSD	32 GB	$943
	GSKILL	FS-25S2-32GB	SSD	32 GB	$694
	Samsung	MCBQE32G5MPP	SSD	32 GB	$517
	Mtron	SATA7035-016	SSD	16 GB	$407
	Transcend	TS16GSSD25S-S	SSD	16 GB	$250
	Transcend	TS32GSSD25S-M	SSD	32 GB	$199
	Kingston	DT hyper X	USB drive	8 GB	$153
	Corsair	Flash Voyager GT	USB drive	16 GB	$110
	Transcend	TS4GDOM40V-S	IDE module	4 GB	$62
	Kingston	DTI 4GB	USB drive	4 GB	$17
	Kingston	SD 4GB	SD card	2 GB	$12

Table 3 : Result summary

 3

			Basic patterns		Pause	Locality	Partitioning		Ordered
		SR	RR	SW	RW	RW	RW	RW	Reverse	In-Place	Large
	Device	(ms)	(ms)	(ms)	(ms)	(ms)	(MB)	(Partitions) (Incr = -1) (Incr = 0)	Incr
	Memoright	0.3	0.4	0.3	5	5	8 (=)	8 (=)	=	=	x4
	Mtron	0.4	0.5	0.4	9	9	8 (x2)	4 (x1.5)	=	=	x2
	Samsung	0.5	0,5	0.6	18		16 (x1.5)	4 (x2)	x1.5	x0.6	x2
	Transcend Module	1.2	1.3	1.7	18		4 (x2)	4 (x2)	x3	x2	x2
	Transcend MLC	1.4	3.0	2.6	233		4 (=)	4 (x2)	x2	x2	x1
	Kingston DTHX	1.3	1.5	1.8	270		16 (x20)	8 (x20)	x7	x6	x1
	Kingston DTI	1.9	2.2	2.9	256		No	4 (x5)	x8	x40	x1

One could consider other metrics such as space occupation or aging. Given the block abstraction the only way to measure space occupation is indirectly through write performance measurements. Measuring aging is difficult since reaching the erase limit (with wear leveling) may take years. Measuring power consumption, however, should be considered in future work.

Considering more than one varying parameter would lead to multidimensional graphs, which are too complex to analyze.

The lowest layer of the file system is the disk scheduler, which actually submits IO operations to the device driver. The disk scheduler is, as its name indicates, designed to optimize submission of IOs to disk. Whether disk schedulers should be redesigned for flash devices is an open question; the uFLIP benchmark should help in determining the answer.

ACKNOWLEDGMENTS

This research was done in the context of the Mana project (http://mana.escience.dk) funded by the Danish strategic research council and partially supported by the French National Agency for Research (ANR) under RNTL grant PlugDB.