Brice Chardin
email: brice.chardin@ensma.fr

Jean-Marc Lacombe
email: jean-marc.lacombe@edf.fr

Jean-Marc Petit
email: jean-marc.petit@liris.cnrs.fr

J-M Lacombe

J-M Petit

Chronos: a NoSQL System on Flash Memory for Industrial Process Data

Keywords: database, flash memory, NoSQL system, data historian

Within Électricité de France (EDF) hydroelectric power stations, IGCBoxes are industrial mini PCs dedicated to industrial process data archiving. These equipments expose distinctive features, mainly on their storage system based exclusively on flash memory due to environmental constraints. This type of memory had notable consequences on data acquisition performance, with a substantial drop compared with hard disk drives. In this setting, we have designed Chronos, an open-source NoSQL system for sensor data management on flash memories. Chronos includes an efficient quasi-sequential write pattern along with an index management technique adapted for process data management. As a result, Chronos supports a higher velocity for inserted data, with acquisition rates improved by a factor of 20 to 54 over different solutions, therefore solving a practical bottleneck for EDF.

legal archiving requirements. Such data consist of timestamped measurements, retrieved for the most part from process data acquisition systems.

Power stations generate large amounts of data for thousands of measurement time series, with sampling intervals ranging from 40ms to a few seconds. This data is aggregated in soft real-time -without operational deadlinesat the plant level by local servers. This archived data -past, but also current values -are used for various applications, including devices monitoring, maintenance assistance, decision support, compliance with environmental regulation, etc. IGCBoxes (cf. figure 1) are a practical example of such applications. These industrial inexpensive mini PCs are distributed over hydroelectric power stations to archive industrial process data from a few days to two years. These equipments expose distinctive features, mainly on their storage system based exclusively on flash memory for its endurance in an industrial environment (due to environmental constraints such as vibrations, temperature variations and humidity). The consumer electronics flash memories (CompactFlash) chosen for IGCBoxes had notable consequences on insert performance, with a substantial drop compared with hard disk drives [START_REF] Pasteur | Results of the use of MySQL free DBMS as a data historian[END_REF]. Indeed, conventional DBMSs lack specific optimization for low to mid-level flash memories, especially with write-intensive workloads. In this setting, we have designed Chronos, an open-source NoSQL system for industrial process data management on flash memories 1 . Chronos exploits flash memories good random read performance which allows an append-only approach for insertions. Specifically, we identified an efficient quasi-sequential write pattern on the targeted devices and built Chronos around this design. Chronos also includes index management techniques optimized for typical process data management workloads. Experimental results show an improvement by a factor of 4 to 18 compared with other solutions, including the one currently in production on IGCBoxes.

Paper Organization

In Section 2, we first describe EDF access patterns and how flash memories can be used efficiently in this context via a quasi-sequential write pattern. We then discuss how this write mechanism is integrated in our NoSQL system, Chronos.

In Section 3, we describe Chronos optimizations for process data, especially an adapted B-tree split algorithm. Performance is discussed in Section 4, with a complexity analysis and experimental results. Related works are presented in Section 5, followed by a conclusion.

2 Write patterns on flash memories

Since insertions have been identified as the main bottleneck, we first clarify insertion patterns at EDF in this section. We then identify an efficient write access pattern on flash memories, followed by a discussion on its integration within Chronos.

EDF access patterns

At EDF, process data consist of a sensor id, a timestamp, a measured value and some metadata. Table 1 gives an example of such data, with the metadata being a simple description of the quality of the sample: whether the sensor was in a good or bad state. Such metadata can usually be more thorough, and include for example a secondary timestamp (the time of acquisition by the system, as opposed to the timestamp provided by the sensor), a bit array to describe the state of the sensor or the network, etc. These tuples can be split in two parts: the key (i.e. the concatenation of the sensor id and the timestamp), and the value (i.e. the concatenation of the measured value and its metadata), which allows us to consider some general hypotheses on the workload, without loss of generality with respect to EDF context.

Order Keys are inserted with increasing timestamps. While these timestamps should be globally increasing, clock synchronization is not perfect; the following -weaker -hypothesis is therefore used: for each sensor id, insertions occur with increasing timestamps.

Using the following order (1), the insertion workload is then made of multiple concurrent streams -typically one for each sensor id -with ordered keys.

We assume a total order on sensor id.

(id x , timestamp x ) ≤ (id y , timestamp y ) ⇔ (id x < id y ) ∨ (id x = id y ∧ timestamp x ≤ timestamp y ) (1)
Hypothesis 1. The sequence of inserted keys (key 0 , key 1 , ..., key i ) can be split into a finite number N of subsequences so that keys are strictly increasing within each. In other words, there exists a function f : N → [0, N ] such that:

∀(i, j) ∈ N × N, f (i) = f (j) ∧ i < j ⇒ key i < key j
No overlap Insertions are supposed to occur in empty intervals of the table. For a subsequence of k insertions (key i , value i ) 0≤i<k , supposed ordered (key i < key i+1 ), the table initially holds no tuple whose key is in the range [key 0 , key k-1 ].

In EDF context, this is true for new insertions, where the timestamp is the current date (and the table does not contain any data for the sensor id after this date). In Table 1, Hypothesis 2. Let (key 0 , key 1 , ..., key k-1 ) be a subsequence of k ordered keys to be inserted. Initially, the table does not hold any key in the interval [key 0 , key k-1 ].

To sum up, we generalize EDF access patterns as insertions of k key-value pairs (key i , value i ) 0≤i<k with keys strictly increasing (key i < key i+1 ), and no keys in the interval [key 0 , key k-1 ] belong to the table beforehand. Several of such insertion sequences can occur concurrently. At EDF, other data accesses are primarily retrieval operations, mostly based on range queries, i.e., analyze the values of a sensor between two specified timestamps.

Write spatial locality for FTL-based devices

The insertion pattern identified in the previous section is inherently sequential for each sensor ID. However, the large number of sensors that has to be supported (several thousands) makes this pattern unsuitable for flash memories. In this section, we discuss how flash memories can be written to efficiently, to later design our DBMS around it.

As the Flash Translation Layer (FTL) enclosed in flash devices is usually proprietary and undocumented, studies have been conducted to identify preferred write access patterns. uFLIP [START_REF] Bouganim | uFLIP: Understanding Flash IO Patterns[END_REF] for instance is a component benchmark designed to quantify the behavior of flash-memories when confronted to defined I/O patterns. Some of these patterns relate to locality and increments between consecutive writes. Their results confirm that localizing random writes greatly improves efficiency and large increments lead to performance which could be even worse than random writes. This result is supported by a study of logstructured file systems for flash-based DBMS [START_REF] Wang | Evaluating Non-In-Place Update Techniques for Flash-Based Transaction Processing Systems[END_REF], as these file systems tend to write large data blocks in sequence. Experimental results validate potential benefits, with performance improved by up to x6. [START_REF] Arpaci-Dusseau | Removing The Costs Of Indirection in Flash-based SSDs with NamelessWrites[END_REF].

In [START_REF] Birrell | A Design for High-Performance Flash Disks[END_REF], Birrell et al. identify a strong correlation between the average latency of a write operation and the distance between writes, as long as this distance is less than the size of two flash blocks. They conclude that write performance varies with the likelihood that multiple writes will fall into the same flash block, which is a manifestation of an underlying block or hybrid-mapping FTL. As a result, a fine-grained mapping is mandatory for high performance flash memories, but we believe that such a mapping can be efficiently managed by the host in an additional indirection layer, distinct from the FTL.

We first propose to quantify the effect of spatial locality on FTL-based devices, by introducing a notion of distance between consecutive writes. In our experiments, the average write duration for each distance d is evaluated by skipping |d|-1 sectors between consecutive writes. This metric can be negative to discriminate between increasing and decreasing address values. From the results of previous works, we conjecture a usual behavior where, up to a distance d max , the average cost of a write operation cost(d) is approximately proportional to d.

To validate this assumption, we measured the effect of distance on a variety of flash devices 2345 . Although individual write durations are erratic, their average value converge when this access pattern is sustained. While our assumption is not verified for all devices, figure 2 shows that this property holds for a flash-based SSD2 and two USB flash drives 34 . Scattered writes (ie. d ≥ d max ) are typically 20 to 100 times slower than sequential writes for flash memories with a block-mapping FTL [START_REF] Bouganim | uFLIP: Understanding Flash IO Patterns[END_REF]. Consequently, and because of this proportional performance pattern, reducing the average distance between consecutive writes can significantly improve efficiency, even if strict sequential access (d = 1) is not achieved. Our optimization focuses on these quasi-sequential access patterns, skipping as little sectors as possible. In the remainder of the paper, only positive distances -increasing addresses -are considered. Additionally, the addressable space is assumed to be circular, in order to avoid handling edges differently.

Quasi-sequential writes

To improve I/O performance, an indirection layer converts any write pattern into a quasi-sequential pattern (cf. figure 3). This is achieved by redirecting write operations to free sectors that minimize the distance between consecutive writes. Consequently, sectors holding valid data and free sectors are mixed on the flash memory. Addresses of free sectors are stored to form a pool of sectors available for writing: the sector minimizing the distance with the previous write is selected for each write operation. To describe our quasi-sequential write algorithm, we represent the flash memory as an ordered set of physical sectors. The indirection layer redirects read and write operations and provides logical sectors to applications. The amount of logical sectors is lower that the amount of physical sectors since a pool of free -physical -sectors is set aside to redirect write operations.

To write -actually to overwrite -a logical sector, data is assigned to a free sector adjacent to the previous write. The previously associated physical sector is reclaimed and added to the pool of free sectors. Figure 4 illustrates how logical writes are assigned to physical locations, when writing successively on logical sectors 0, 3 and 0. Consequently, physical sectors containing obsolete data are immediately freed and can be overwritten. As the size of the pool remains constant, this optimization does not require garbage collection. Yet, as an independent and internal mechanism, the FTL might still use garbage collection to handle flash erasures.

The average distance of the quasi-sequential access pattern is determined exclusively by the proportion of pool sectors, regardless of the logical write access pattern. As we consider devices whose write latency is proportional to this average distance, the amount of pool sectors can be adjusted to obtain an expected efficiency [START_REF] Chardin | An FTL-agnostic Layer to Improve Random Write on Flash Memory[END_REF]. Still, increasing the pool size requires additional flash memory space.

As a potential downside, sequential reads are also transformed into random reads. However, this behavior is not an issue for flash devices, as random reads are as efficient as sequential reads [START_REF] Bouganim | uFLIP: Understanding Flash IO Patterns[END_REF].

Integration in Chronos

In previous work [START_REF] Chardin | An FTL-agnostic Layer to Improve Random Write on Flash Memory[END_REF], data retrieval required a non-volatile address translation table to maintain logical-physical addresses associations. With a DBMS, this address translation table could be made volatile as only a table identifier is needed within each data block to rebuild the database after a crash. To integrate this write pattern in Chronos, we settled for the nameless writes interface [START_REF] Arpaci-Dusseau | Removing The Costs Of Indirection in Flash-based SSDs with NamelessWrites[END_REF] as an abstraction of flash memory accesses. This interface was originally designed to let SSDs choose the location of a write internally, by assigning a location for the data during a nameless write operation. However, in Chronos, this layer is not integrated in the device, but is used to manage write redirection within the DBMS.

The nameless writes interface includes four basic operations. The main write operation allows this abstraction to choose the physical location of the data, which is returned by the access method: address ← nameless_write(data)

In-place writes are still allowed (when the physical location is provided by Chronos), as well as reading: write(address, data) data ← read(address)

To reuse sectors with nameless writes, those have to be freed beforehand, using a trim command. If the flash device supports it, this operation can optionally indicate that data stored at this location are obsolete.

trim(address)

Since our target device class has good quasi-sequential write and random read performance, the nameless write operation is designed to result in quasisequential writes. This interface therefore maintains the set of free sectors in a data structure (based on binary trees) with three operations:

pop to retrieve the physical location of the next sector to write to, with a O (1) complexity, insert to add a free sector to this set, with a O (log n) complexity, erase to remove a sector from this set, with a O (log n) complexity. Algorithms 1, 2 and 4 show the interactions between this data structure and the flash memory access abstraction.

With nameless writes, physical locations have to be stored by Chronos. A B-tree is used to index data blocks, therefore keeping the association between key intervals and physical addresses for the corresponding data. However, This abstraction isolates the selection of physical locations from other components of Chronos. With minor modifications, it is possible to replace the write sector selection algorithm by another solution -for example pure sequential writes with a garbage collection mechanism -, or even to let the device make this decision, as suggested in the original article [START_REF] Arpaci-Dusseau | Removing The Costs Of Indirection in Flash-based SSDs with NamelessWrites[END_REF].

Chronos principles

Chronos is a NoSQL system designed to manage process data on flash memory. It is generalized as a software library providing an ordered key-value store, but optimized for access patterns described in Section 1. Chronos interacts with the flash memory using the nameless write interface presented previously to improve write performance.

Figure 5 gives an overview of this architecture. Chronos allows an application to manage tables and cursors on these tables, and interacts with the device through the file system. To improve performance, the preferred access for flash memories is by using a raw file system, which provides a direct access to the block interface of the device.

In this section, we first introduce a common technique to speed up data acquisition using write cursors and present its integration within Chronos. We then describe our proposition to improve B-trees split algorithm in our context, followed by discussions on their impact on disordered keys and durability.

Write cursors

In Chronos, write cursors relate with the concept of fence keys [START_REF] Graefe | Modern B-Tree Techniques[END_REF]. On any node of the B-tree, these fence keys are local copies of minimum and maximum possible key values, specifically lower and upper boundary keys stored in parent nodes in the B-tree. Negative and positive infinity are represented with special fence values. At the leaf level, to which write cursors are associated with, fence keys define a possible key range for new key-value pairs. Once opened, a cursor can then be used to insert pairs whose keys belong to its associated leaf, without searching the B-tree from the root. This behavior is especially useful in EDF context, where consecutive inserted keys are associated with the same leaf.

To validate an insertion using cursors, fence keys are stored with the volatile memory representation of leaves. Although these boundaries can be modified by concurrent accesses (such as, typically, the deletion of the tuple associated with a boundary), this stored interval is always a lower bound of the leaf's validity interval. Checking this interval does not result in false positive answers, but negative answers -inserted key does not belong to this intervalrequire an update of the leaf's fence keys before rejecting the insertion. This mechanism allows efficient key-value pairs insertion in this validity interval, without searching the B-tree from the root.

B-tree insert algorithm optimization with respect to EDF access patterns

With these cursors, consecutive insertions attempt to write the same leaf as the previous operation. Other NoSQL systems such as Berkeley DB [START_REF] Olson | FREENIX'99: 1999 USENIX Annual Technical Conference, FREENIX Track[END_REF] already include this kind of optimization; however, splitting a node still requires a topdown search from the root to add the median key in the parent node. Moreover, this operation leaves both new nodes half full. In EDF context, no new insert operation should occur for the node holding lower keys -i.e. past timestamps -according to special access patterns identified previously. Figure 6 illustrates how a standard B-tree behaves with respect to insertions of ordered keys.

Consequently, the fill factor of the tree -i.e. the ratio between useful data and reserved space -can be improved by a factor of two: when a node is split, instead of dividing it in two nodes of equal size, Chronos only allocates a new node containing the highest key. This optimization is practical only if new insertions follow this highest key. Otherwise, the node is split at the last inserted key, in order to match the favorable case for future insertions.

Figure 7 illustrates this mechanism for leaves split operations. The resulting B-tree is more compact with the adapted split algorithm, with a fill factor close to 1.

This adapted algorithm does not guarantee that nodes are at least half full. For instance, in the worst case scenario where keys are inserted in reverse order, each leaf contains only one tuple. Consequently, to avoid almost empty nodes in the higher levels of the tree, this mechanism is only applied for leaves. The standard split algorithm is used for higher levels. Determining how many levels of the tree (currently one: only leaves) should use the adapted algorithm is a prospect for improvement. To avoid searching the tree from the root during a node split, in-memory node representations maintain a pointer to the parent node. These pointers are thus never stored on the flash memory. To simplify pointer management, when a node is kept in main memory, his parent also is, recursively up to the root. At the lowest level, leaves are only kept in memory if a read or write cursor is attached.

This mechanism makes up for the lack of chained references between leaves, to process range queries efficiently -without searching the tree from the root to find successive leaves.

Algorithm 5 details insertions of key-value pairs in leaves. In the favorable split case, tuples associated with lower keys are moved to a new leaf written on the flash memory, with a fill factor of 1. The old leaf then only contains a single tuple, the latest. In the unfavorable case, higher keys are moved, with an undefined fill factor.

Disorder

Network latency can introduce a bounded disorder in insertions, that is to say that the position of each tuple in the insertion stream can be slightly different from its position in an ideal stream. We suppose this disorder lower than an upper bound .

Let timestamps of inserted tuples be timestamp i , with i the insertion order:

∀(i, j), j < i -⇒ timestamp j < timestamp i
Consequently, a window of size is enough to reorder incoming tuples. This reordering is performed within write cursors using a buffer. The value of has to be chosen with care as inserted tuples that do not meet this upper bound require the cursor to be reopened and therefore decrease performance. As a result, the size of the reordering window is a compromise between performance and the amount of data lost on power failure (buffered data is lost).

Durability

Chronos does not handle transactions to improve performance. In our context, data is lost regardless of transactional capabilities when the system is unavailable since sensors only have limited local storage. However, persistence is mandatory for historical data. Chronos keeps leaf nodes associated with opened cursors and their ancestor nodes in volatile memory. For internal nodes, which are not required to rebuild the table, data durability is not impacted. Leaves however contain original data, which is lost on failure -even though part of this data can be recovered from previous versions of leaves kept on flash memory. Data from the reordering window are especially lost during failure. Usually, data loss affect recent insertions and are bounded, by cursor, by the size of a leaf and of the reordering window: L + .

In Chronos, since tuples are not split between multiple physical sectors, rebuilding the table only requires a table identifier to be stored in a header within each sectors holding leaf data. This operation however requires scanning the whole flash memory, which can be expensive for large databases. Moreover, erased data can be unintentionally retrieved during recovery. It could however be possible to define checkpoints to store a version of the index. A recovery operation would then only need to scan sectors written subsequently. The integration of data recovery within Chronos is a prospect for improvement.

Performance

Complexity analysis

For process data management typical workloads, Chronos makes a point of minimizing flash memory accesses. These accesses can be quantified, and turn out to be close from an optimal solution -without data compression. Although flash memory is the limiting factor, CPU utilization is also estimated, in order to identify a possible limitation in scalability.

Given a tree with nodes of average size F -each node holds F keys -and leaves of average size L -each leaf holds L key-value pairs. This tree holds a total of N key-value pairs. We then insert k key-value pairs (key i , value i ) 0≤i<k successively in this tree, with increasing indices i. Notations are given in table 2.

Hypothesis 1 [START_REF] Pasteur | Results of the use of MySQL free DBMS as a data historian[END_REF]. Key-value pairs are inserted with keys strictly increasing.

key 0 < key 1 < • • • < key k-1
Hypothesis 2 (2 ). Initially, the table does not hold any key in the interval [key 0 , key k-1 ].

As a result of hypothesis 1 and 2, these insertions match the favorable case of our write algorithm. Consequently, the fill factor for leaves is always 1. As for internal nodes, average number of keys per node is supposed to remain constant; this simplifying assumption has limited impact since internal nodes are at least half full. Hypothesis 3. Average sizes for leaves and nodes L and F remain constant.

Flash memory access

For typical workloads, Chronos writes almost exclusively sectors filled with new data (leaves of the B-tree). The rest (internal nodes and nodes accessed during the opening of the cursor) make up for a small fraction of written data. Indeed, we prove that k insertions lead to about k /L nameless write operations.

Property 1 After k insertions, k L(F -1)
nodes and k L leaves are added to the tree.

Proof. Initially, the tree's height is h, and it holds A leaves and B nodes such that:

h = log F N L A = N L B = h i=1 N LF i
After k insertions, the amount of key-value pairs stored in the tree is N = N + k, whose height is now h , with A leaves and B nodes such that:

h = log F N L A = N L B = h i=1 N LF i h -h = log F N L -log F N L = log F N N A -A = N L - N L = k L B -B = h i=1 N LF i - h i=1 N LF i = h i=h+1 N LF i + h i=1 N LF i - h i=1 N LF i = h i=h+1 N LF i + k L h i=1 1 F i (2) yet, h i=h+1 N LF i = N LF h+1    1 - 1 F h -h 1 - 1 F    = N LF h+1     1 - 1
F log F ( N N ) 1 - 1 F     = N LF h+1    1 - N N 1 - 1 F    = N LF h+1    k N 1 - 1 F    = k LF h+1    1 1 - 1 F    (3) additionnally, h i=1 1
F i is a geometric series:

h i=1 1 F i = 1 F    1 - 1 F h 1 - 1 F    (4)
From ( 2), ( 3) and ( 4):

B -B = k LF h+1    1 1 - 1 F    + k LF    1 - 1 F h 1 - 1 F    = k LF    1 F h 1 - 1 F + 1 - 1 F h 1 - 1 F    = k LF    1 1 - 1 F    = k L(F -1)
To sum up,

h -h = log F N N A -A = k L B -B = k L(F -1)
After k insertions, the tree thus holds k L(F -1) additional nodes and k L additional leaves.

Property 2 For k insertions, kF L(F -1)

+ flash memory sectors are written, with ≤ log F N L .

Proof. When inserting new data using an opened cursor -our hypotheses imply that the cursor initially opened stays valid -, a flash memory write operation only occurs during the split of a node or a leaf (cf. algorithm 5).

The number of writes therefore equals the number of new elements in the tree.

From property 1, for k insertions, k L(F -1) nodes and k L leaves are added to the tree.

k L(F -1) + k L = kF L(F -1)
Disregarding cursor opening and closing phases, the number of flash memory sectors written thus amounts to kF L(F -1) .

The only nodes from the initial tree that could have been updated are those accessed during the cursor's opening, that is h nodes -among which some might not have been modified.

Consequently, the total number of flash memory sectors written is at most kF L(F -1) + log F N L .

In practice, F 1, so F /F -1 1 -that is to say the tree is mainly made of leaves 6 . Chronos therefore writes a new sector every L(F -1) /F L insertions on average. Proof. Opening and closing a cursor are usual B-tree search operations, with a complexity of O (log(N )) and O (log(N )) = o(k) [START_REF] Graefe | Modern B-Tree Techniques[END_REF], which disappear in the amortized complexity. Disregarding these two phases, computational complexity comes from the following basic operations:

appending a key-value pair to a leaf, in O (1), splitting a leaf, in O (F + L) -without split recursion, splitting a node, in O (F ) -without split recursion.

For leaves splitting, only the following operations (from algorithm 5) have a significant computational complexity, our hypotheses matching the favorable case:

operation 7 in O (L): copy (part of) the leaf content, operation 11 in O (F ): insert a key in parent node.

Complexity is comparable for internal nodes, in O (2F ) = O (F ).

From previous results, k L(F -1)

nodes and k L leaves are split in totalincluding recursions -for k insertions. Total computational complexity C then amounts to:

C = k × O (1) + k L(F -1) × O (F ) + k L × O (F + L) = O k 1 + 1 L + F L + L L = O k 1 + F L Therefore: C k = O 1 + F L
In this complexity, only cursors open and close operations are conditioned by N , which is neglected when k, the amount of insertions, becomes large enough.

Benchmark

Many benchmarks have been defined for relational database management systems for years, like TPC-C or TPC-H [START_REF]Transaction Processing Performance Council[END_REF][START_REF]Transaction Processing Performance Council[END_REF]. Nevertheless, to the best of our knowledge, none of them are designed for process data management. The idea of comparing these systems with an existing benchmark -designed for RDBMS -seems natural. However, in the context of industrial data at EDF, it is impractical to use one of the Transaction Processing Performance Council benchmarks for the following reasons:

-Chronos is not ACID-compliant, and do not support transactions.

-Insertion is a fundamental operation. This type of query is executed in realtime, which prevent using benchmarks that batch insertions, like TPC-H. -Chronos is designed to handle time series data. It is mandatory that the benchmark focuses on this type of data for results to be relevant.

Benchmarks for data stream management systems, like Linear Road [START_REF] Arasu | Linear Road: A Stream Data Management Benchmark[END_REF] have also been considered; but continuous queries are not part of typical workloads at EDF [START_REF] Pasteur | Overview of the long-term stored data in power generation units[END_REF].

We have therefore defined a simple benchmark inspired by the scenario of nuclear power plants data management. In this context, data generated by sensors distributed on the plant site are aggregated by a daemon communicating with the DBMS. For insertions, the benchmark simulates this daemon and pseudo-randomly generates data to be inserted. This workload fits IGCBoxes use case, where updates are rare and deletions are forbidden.

This data is then accessible for remote users, which can send queries to update, retrieve or analyze this data. After the insertion phase, this benchmark proposes a simple yet representative set of such queries.

The full specifications of this benchmark are given in [START_REF] Chardin | Data Historians in the Data Management Landscape[END_REF] along with a more thorough analysis of different solutions; this paper focuses on Chronos performance. To sum up, this benchmark defines 12 kinds of queries: insertion (Q0), update (Q1), raw data extraction (Q2), aggregate calculation (Q3, Q4, Q5 and Q6), data filtering (Q7 and Q8), analysis on multiple time series (Q9 and Q10) and most recent value extraction for all time series (Q11). These queries are evaluated on two kinds of data: analog values (QX and QX.1) and boolean values (QX.2).

Inserted data amounts to 500M (500,000,000) tuples for each data type -analog and boolean -which sums up to 11.5 GB without compression and timestamps stored on 8 bytes. These tuples are divided between 200 time series (100 for each data type). 1M updates for each data type are then queried against the database; followed by up to 1K (1000) SFW queries -100 for R9 and R10, 1 for R11.1 and R11.2 -with different parameters. Date parameters for queries R2 to R8 are generated to access 100K tuples on average. R9 and R10 involve all analog time series, therefore each execution access 10M tuples on average. This benchmark is used to compare the performance of Chronos with two solutions used in this context at EDF: the RDBMS MySQL 5.5 and the data historian InfoPlus.21 version 2006.5. We also evaluate the NoSQL system Berkeley DB version 5.2, whose access methods and usage are comparable with Chronos. MySQL and Berkeley DB have been tuned to improve their performance [START_REF] Chardin | Data Historians in the Data Management Landscape[END_REF], especially by disabling transactions. On the other hand, In-foPlus.21 and Chronos are designed for this application, and did not need any significant adjustment.

Experimental results

Experiments have been conducted on a server with a Xeon Quad Core E5405 2.0GHz processor, 3GB of RAM and three 73GB 10K Hard Disk Drives with a RAID 5 Controller. The same benchmark is then executed with a single USB flash drive 7 as the mass storage system. Since Chronos and Berkeley DB both have a simple data retrieval API, queries can be classified in 4 categories: -Insertions (with ordered keys), -Updates (with random keys), -Range queries, -Key search (to retrieve a single key-value pair). Data historians (InfoPlus.21) and RDBMSs (MySQL) performance however vary according to the type of range query. We therefore specify 4 additional sub-categories for range queries:

-Raw data extraction, -Aggregate queries (count, min, max, average, sum), -Filtered values (using thresholds), -Analysis of multiple series.

On hard disk drives

Table 3 reports execution times with each system on hard disk drives. For instance, line 1 means that executing Q0.1 500M times took 8 003 seconds for InfoPlus.21, 24 672 seconds for MySQL, 2 850 seconds for Berkeley DB and 236 seconds for Chronos. Figure 8 then gives an overview of processing capacities, expressed in tuples processed per second. Table 4 and Figure 9 summarize the average processing capacity for each system by category of queries.

As illustrated in Figure 9, Chronos can sustain over 2M insertions per second, that is 13× better than Berkeley DB (168K), 33× better than InfoPlus.21 (67K) and 107× better than MySQL (21K) 8 . This first phase of the benchmark is exclusively composed of insert operations (no data is updated or deleted). Therefore, invalid sectors can only occur on index nodes update, which represent at most 0.4% of the data on disk. Consequently, the quasi-sequential pattern is comparable with a pure sequential access performance-wise, which Fig. 9 Processing capacity by category on hard disk drives (higher is better) is efficient on both HDDs and flash memories. Insert operations also benefit from the fill factor optimization. Accessing single tuples, i.e, non range queries, (updates and current values extraction) involve random accesses for every solution, which then exhibit comparable performance -with the notable exception of InfoPlus.21 which is optimized for current values extraction [START_REF] Chardin | Data Historians in the Data Management Landscape[END_REF].

As for range queries (Q2.1 to Q10, c.f. Figures 8 and9), Chronos reads the hard disk drives randomly, while other solutions read sequentially. Consequently, Chronos is on average 1.7× slower than Berkeley DB, that is 3.9× slower than MySQL and 4.5× slower than InfoPlus.21. On account of these random reads, performance is naturally improved with flash memories.

On flash memory

Table 5 reports execution times with each system on flash memory. Figure 10 then gives an overview of processing capacities, expressed in tuples processed per second. Table 6 and Figure 11 summarize the average processing capacity for each system by category of queries.

As illustrated in Figure 11, Chronos can sustain 900K insertions per second, that is 20× faster than Berkeley DB (45K), 47× faster than MySQL (19K) and 54× faster than InfoPlus.21 (17K).

Updates however are especially slow for every solution, where sustainable workloads range from 1 to 18 updates per second. With the USB flash drive used in this experiment, random writes are inefficient, which explains this result -moreover, in Chronos current implementation, updates do not use nameless writes, i.e., updates are in-place.

With flash memories, updates significantly deteriorate performance for subsequent queries (Q2.1 and Q2.2), which is distinctive of their internal garbage collection mechanisms. Disregarding this behavior, Chronos range queries performance is improved by a factor of 3.9× compared with hard disk drives. Similarly, Berkeley DB process these queries 5.3× faster. For comparison, MySQL and InfoPlus.21 are only 6% and 44% faster, respectively.

For range queries (Q2.1 to Q10, c.f. Figures 10 and11), Chronos can process on average 386K tuples per second, that is 1.2× slower than MySQL (449K), 1.9× slower than InfoPlus. [START_REF] Li | Tree Indexing on Flash Disks[END_REF] For range queries, the disparity between the various solutions is significantly reduced compared with hard disk drives. Consequently, Chronos fares significantly better on flash memory with respect to other solutions both for insertions and extractions.

To sum up, Chronos on flash memories is more than an order of magnitude faster for insertions compared with other solutions, while providing comparable performance for range queries. In particular, this behavior allows Chronos to better fulfill the requirements of IGCBoxes.

Analysis in IGCBoxes context

For IGCBoxes mid-term (two years) data archiving, data are acquired and extracted at least once, but can also be queried locally at the plant level. However, the extraction/insertion ratio remains low -typically between 1 and 2. With this workload, Chronos stands out with performance 4× to 18× higher than other solutions. For example, if each tuple is extracted 1.5 times on average -unsing range queries -, Chronos can sustain a workload of 220K A real-world experimentation has been conducted on a test platform at EDF Hydraulic Engineering Center in Grenoble, France, with 2nd generation IGCBoxes 9 . The historical data management library has been modified for Chronos, and compared with the current solution based on MySQL -which includes several optimizations such as batch insert statements.

Under heavy workloads with up to 15K insertions per second from 4000 sensors, the performance of the acquisition system has been improved by a factor of 9.4× with Chronos compared with the solution currently in production.

Related work

In [START_REF] Shafer | Specialized Storage for Big Numeric Time Series[END_REF], Shafer et al. describe specialized storage requirements for numeric time series and give an overview of suitable data management systems. However, these solutions do not focus on efficient insertions nor do they take into account flash memories distinctive features. While Chronos does not meet every requirement listed in this paper, it could, like Berkeley DB for the distributed data store Voldemort [START_REF] Sumbaly | Serving Large-scale Batch Computed Data with Project Voldemort[END_REF], provide a low level data management layer to build such a system. Chronos quasi-sequential approach is inspired by flash log-structured file systems such as JFFS [START_REF] Woodhouse | Jffs : The journalling flash file system[END_REF] or LogFS. However, these file systems target flash chips and are not suitable as is for flash memories that include FTL. Besides, log-structured file systems (including general-purpose file systems such as NILFS [START_REF] Konishi | The linux implementation of a log-structured file system[END_REF]) have a background garbage-collection mechanism that might interfere negatively with the insertion workload.

The Append and Pack [START_REF] Stoica | Evaluating and Repairing Write Performance on Flash Devices[END_REF] approach for instance writes data sequentially (append ). Reclamation (pack ) is performed by moving least recently updated data to the head of the log. To avoid moving static data, two logs hot and cold are differentiated depending on update frequency: reclamation (pack ) moves data to the cold log, while writing (append ) is performed on the hot log.

Compared with previous such approaches to log writes on flash memories (IPL [START_REF] Lee | Design of Flash-Based DBMS: An In-Page Logging Approach[END_REF], PDL [START_REF] Kim | Page-Differential Logging: An Efficient and DBMS-independent Approach for Storing Data into Flash Memory[END_REF] and Append and Pack [START_REF] Stoica | Evaluating and Repairing Write Performance on Flash Devices[END_REF]), our contribution does not require garbage collection mechanisms to reclaim contiguous flash memory regions. Moreover, IPL and PDL significantly decrease read performance, while our algorithm only has a negligible impact for this operation. In compensation, our algorithm requires a good amount of free sectors to be gathered on the device in order to write quasi-sequentially. Such distribution might occur less frequently as the device becomes full. Chronos RAM consumption is also significantly higher, which prevents its usage in devices where this resource is scarce.

As for indexation, FD-tree [START_REF] Li | Tree Indexing on Flash Disks[END_REF] is a set of ordered series. Each series constitute a level, beginning with level L0 stored in RAM with a B-tree; lower levels (L1, L2, etc.) have their capacity increased by a constant ratio n compared with the level above them. When a level is full, it is merged with the level above which leads to sequential writes. However, merging two levels at the bottom of the tree can be especially expensive and block other accesses until its completion.

Contrary to conventional indexes, lazy-adaptive trees (LA-tree) [START_REF] Agrawal | Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices[END_REF] do not propagate updates to leaves. Each node has an associated buffer on flash memory to store its updates, which contains pending operations for this node or its descendants. Reclaiming a buffer consists in pushing its operations towards the bottom of the tree, until eventually reaching leaves.

FD-tree and Lazy-adaptive tree (LA-tree) aim at improving write performance for indexes on flash memories. They are however designed for conventional workloads and do not take into account EDF specific insertion pattern.

Get Tracked [START_REF] Dobreva | Get tracked: A triple store for rfid traceability data[END_REF] is a triple store to manage RFID measurements with high insertion rates. This DBMS maintains 15 clustered B+trees for each possible index order and aggregation level, with optimization techniques for each index. Rather, Chronos maintains a single clustered index on (Sensor ID, Timestamp, Value) similar to their index on (Reader ID, Timestamp, Electronic Product Code) for RFID data, which was optimized by reserving spare pages for each reader ID to insert future data. Their technique leads to multiple batch writes on the device to update the index with new records. Only a large batch size would provide acceptable performance on flash memory, a the cost of increased RAM consumption and amount of data lost on failure. Chronos achieves a single sequential write access pattern for this kind of index, while keeping the batch size as small as possible (4 KB).

Nameless writes [START_REF] Arpaci-Dusseau | Removing The Costs Of Indirection in Flash-based SSDs with NamelessWrites[END_REF] are a generic flash memory abstraction, allowing the isolation of index management and flash memory management. For instance, flash memories where quasi-sequential writes are not efficient could also be used, provided an efficient write pattern is found (and random reads are still fast).

High-end SSDs also provide good random write performance, in exchange for more RAM and processing power [START_REF] Agrawal | Design Tradeoffs for SSD Performance[END_REF][START_REF] Lee | Advances in Flash Memory SSD Technology for Enterprise Database Applications[END_REF]. However, these designs provide homogeneous performance across the entire flash memory, which is not required by most applications. By adding a software layer, Chronos provides good write performance on low-cost devices.

Additionally, latest SSDs evaluations [START_REF] Jung | Revisiting widely held SSD expectations and rethinking systemlevel implications[END_REF][START_REF] Bjorling | The Necessary Death of the Block Device Interface[END_REF] show that sequential writes and random writes have similar performance and sequential reads perform significantly better than random reads. Because the nameless writes abstraction relies on sequential writes and random reads, Chronos will not perform optimally on these devices. Yet, other optimizations introduced in this paper -dedicated to process data management workloads -are unrelated to access patterns and still applicable.

Conclusion

Chronos is a simple NoSQL system, suitable for industrial process data management on flash memories, and optimized towards insertions. By design, Chronos has some limitations which can prevent it from being used in other contexts: data durability is only guaranteed to some extent, and data accesses -both insertions and extractions -are based on range queries.

Experimental results confirm however the efficiency of optimizations included in Chronos: quasi-sequential writes on flash memory, node split algorithm adaptation and using write cursors for insertions. Indeed, Chronos offers the highest performance among benchmarked solutions for insertions. In compensation, these optimizations lower extraction performance, especially since this operation requires random reads on the device. This downside is significant with hard disk drives, but reasonable with flash memories. Chronos is therefore a competitive solution when insertions make up an extensive part of the workload.

In Chronos, the data layout is optimized towards writing (quasi-sequential writes) at the cost of reading performance (random reads). Making this compromise adjustable to meet applications requirements -especially when data is read more frequently -is a prospect for improvement.

Fig. 1

 1 Fig. 1 The original IGCBox (left) and the TinyBox version (right)

  following insertions should have a timestamp above '2014-01-21 09:00:18' for sensor 1, '2014-01-21 09:00:11' for sensor 2 and '2014-01-21 09:00:20' for sensor 3. Valid intervals for future insertions are then: ] (1, 2014-01-21 09:00:18), (2, 2014-01-21 09:00:11) [ for sensor 1, ] (2, 2014-01-21 09:00:11), (3, 2014-01-21 09:00:00) [ for sensor 2, ] (3, 2014-01-21 09:00:20), (+∞) [ for sensor 3.

Fig.

  Fig. Influence of distance on write duration Sequential Random Quasi-sequential

Fig. 4

 4 Fig. 4 Write redirection overview

input: data 1

 1 address ← list.pop() 2 flash.write(address, data) 3 return(address) Algorithm 1: nameless_write input: address, data 1 list.erase(address) /* remove the address from the list of free sectors if present */ 2 flash.write(address, data) Algorithm 2: write input: address 1 data ← flash.read(address) 2 return(data) Algorithm 3: read input: address 1 list.insert(address) 2 flash.trim(address) /* if supported by the device */ Algorithm 4: trim

Fig. 5

 5 Fig. 5 Chronos architecture

Fig. 7

 7 Fig. 7 Chronos split algorithm

4. 1 . 2

 12 Processor utilization Property 3 The amortized complexity of an insertion in CPU cycles is constant, in O 1 + F L .

Fig. 8

 8 Fig.8Processing capacity on hard disk drives (higher is better)

Fig. 10 Fig. 11

 1011 Fig.10Processing capacity on flash memory (higher is better)

Table 1

 1 EDF process data

	sensor id	timestamp	value	metadata
	3	2014-01-21 09:00:00	17.62	good
	1	2014-01-21 09:00:10	5.43	good
	2	2014-01-21 09:00:11	-58.46	bad
	1	2014-01-21 09:00:12	11.07	good
	1	2014-01-21 09:00:18	13.94	good
	3	2014-01-21 09:00:20	-8.32	good

  : leaf, key, value output: error code 1 if key ≤ leaf.lower_bound or key ≥ leaf.upper_bound then 2 return(out of range) 3 leaf.keys.add(key) /* keys are kept in sorted order */ 4 leaf.values.add(value) 5 if leaf is overfull then 6 if key = max(leaf.keys) then /* favorable case */ {tuples <k,v> ∈ leaf : k < split_key} 9 leaf ← {tuples <k,v> ∈ leaf : k ≥ split_key} /* update the leaf, which then only contains the latest pair */ 14 split_key ← min({keys k ∈ leaf.keys : k > key}) 15 new_leaf ← {tuples <k,v> ∈ leaf : k ≥ split_key} 16 leaf ← {tuples <k,v> ∈ leaf : k < split_key}

	7	split_key ← key
	10	leaf.lower_bound ← split_key
	11	address ← nameless_write(new_leaf)
	12	leaf.parent.insert_left(split_key, address) /* if necessary, split
		internal nodes recursively */
	13	else /* unfavorable case */
	17	leaf.upper_bound ← split_key
	18	address ← nameless_write(new_leaf)
	19	leaf.parent.insert_right(split_key, address) /* if necessary, split
		internal nodes recursively */
	20 return(ok )
		Algorithm 5: Inserting a key-value pair in a leaf

input 8 new_leaf ←

Table 2 Notations

 2

	N	number of key-value pairs in the tree
	N	number of key-value pairs in the tree after k insertions
	F	average size of internal nodes (in keys)
	L	average size of leaves (in keys)
	h	height of the tree
	h	height of the tree after k insertions
	A	number of leaves
	A	number of leaves after k insertions
	B	number of internal nodes
	B	number of internal nodes after k insertions

Table 3

 3 Query execution time on hard disk drives

		Query		Execution time (in s)
		(amount)	InfoPlus.21	MySQL	Berkeley DB	Chronos
	Q0.1 (×500M)	8 003	24 672	2 850	236
	Q0.2 (×500M)	7 086	24 086	3 116	222
	Q1.1 (×1M)	16 763	12 240	9 032	8 402
	Q1.2 (×1M)	16 071	13 088	9 349	8 523
	Q2.1 (×1K)	268	410	693	1 263
	Q2.2 (×1K)	215	285	655	1 018
	Q3.1 (×1K)	207	187	531	1 214
	Q3.2 (×1K)	167	182	533	995
	Q4	(×1K)	210	193	537	1 216
	Q5	(×1K)	189	186	514	1 115
	Q6	(×1K)	189	192	513	1 091
	Q7	(×1K)	234	234	508	1 059
	Q8	(×1K)	231	278	506	1 055
	Q9	(×100)	1 641	1 710	4 878	4 878
	Q10 (×100)	1 689	7 661	4 978	4 899
	Q11.1 (×1)	9.5 × 10 -4	1.15	2.75	1.06
	Q11.2 (×1)	2.8 × 10 -4	1.13	4.81	0.90

Table 4

 4 Processing capacity on hard disk drives

		Average processing capacity (in tuples per second)
	Query type	InfoPlus.21	MySQL	Berkeley DB	Chronos
	Insertions	66519	20512	167950	2185448
	Updates	61	79	109	118
	Raw data	419125	297390	148486	88704
	Aggregates	523257	532162	190329	89291
	Filtering	430125	393531	197239	94608
	Multiple series	600725	357663	202943	204563
	Current values	231203	88	29	103

  (714K), and 2.1× slower than Berkeley DB (816K).

		InfoPlus.21				MySQL			Berkeley DB				Chronos
		7
		6
	Tuples processed per second	2 3 4 5
		10
		1
		Q0.1	Q0.2	Q1.1	Q1.2	Q2.1	Q2.2	Q3.1	Q3.2	Q4	Q5	Q6	Q7	Q8	Q9	Q10	Q11.1	Q11.2
									Query type

Table 5

 5 Query execution time on flash memory

		Query		Execution time (in s)
		(amount)	InfoPlus.21	MySQL	Berkeley DB	Chronos
	Q0.1 (×500M)	34 412	26 468	10 887	638
	Q0.2 (×500M)	26 849	25 444	11 137	493
	Q1.1 (×1M)	820 011	229 096	53 690	109 450
	Q1.2 (×1M)	731 862	251 751	56 397	94 506
	Q2.1 (×1K)	341	1 066	2 839	420
	Q2.2 (×1K)	201	272	1 744	231
	Q3.1 (×1K)	103	168	104	260
	Q3.2 (×1K)	93	160	102	228
	Q4	(×1K)	104	171	102	261
	Q5	(×1K)	97	170	101	254
	Q6	(×1K)	96	171	101	254
	Q7	(×1K)	205	227	101	258
	Q8	(×1K)	202	288	101	252
	Q9	(×100)	1 993	1 722	1 000	2 554
	Q10 (×100)	1 989	7 497	1 001	2 485
	Q11.1 (×1)	9.9 × 10 -4	0.31	0.39	0.37
	Q11.2 (×1)	2.7 × 10 -4	0.38	0.69	0.39
	Table 6 Processing capacity on flash memory
			Average processing capacity (in tuples per second)
	Query type	InfoPlus.21	MySQL	Berkeley DB	Chronos
	Insertions	16576	19271	45411	898949
	Updates	1	4	18	10
	Raw data	395384	230728	46282	335498
	Aggregates	1016055	595613	980504	398751
	Filtering	491427	393875	990099	392211
	Multiple series	502261	357053	999500	396979
	Current values	235690	293	201	263

  Sustainable workload function of the extraction/insertion ratio (higher is better) tuples per second on insertion, while Berkeley DB can only sustain 42K tuples per second, 18K for MySQL and 16K for InfoPlus.21. Figure12shows highest sustainable workloads, depending on this extraction/insertion ratio. For this reason, Chronos is competitive despite its lower performance for extractions, with better performance than other solutions while the extraction/insertion ratio remains under 16.

		10 6
	Sustainable workload (in tuples per second)	10 3 10 4 10 5
		10 2	1	10	100	1000
					Read/write ratio
			InfoPlus.21	MySQL	Berkeley DB	Chronos
	Fig. 12

http://lias-lab.fr/~bchardin/chronos

SSD Mtron MSD SATA3035-032.

Flash chip HYNIX HY27UG088G5B with an ALCOR AU6983HL controller.

Kingston DataTraveler R500 64 Go.

Kingston SD card SD/2GB B000EOMXM0.

For instance, for our benchmark (cf. Section 4.2), with 17 bytes tuples (among which 12 are the key), and 4096 bytes sectors, L = 240 and F = 256, then 99.6% of the tree is made of leaves.

MySQL is CPU bound for insertions on hard disk drives, all other queries and systems combinations are I/O bound.

AMD Geode 500MHz, 2GB CompactFlash storage device.