Shaoyi Yin
email: shaoyi.yin@inria.fr

Philippe Pucheral
email: philippe.pucheral@inria.fr

Xiaofeng Meng

PBFilter: Indexing Flash-Resident Data through Partitioned Summaries

Keywords: Indexing method, NAND Flash, Bloom Filter, cost model Indexing Flash-Resident Data through Partitioned Summaries méthode d'indexation, Flash NAND, Bloom Filter, modèle de coût

NAND Flash has become the most popular persistent data storage medium for mobile and embedded devices and is even being considered as a credible competitor for traditional disks. The hardware characteristics of NAND Flash (e.g. page granularity for read/write with a block-erase-before-rewrite constraint, limited number of erase cycles) preclude in-place updates. Previous works adapted traditional indexing methods to cope with these constraints mainly by deferring index updates thanks to a log and batching them to decrease the number of rewrite operations in Flash. These methods introduce a complex trade-off between read and write performance and neglect negative side-effects on the RAM consumption, Flash consumption and garbage collection cost. In this paper, we propose a new alternative for indexing Flashresident data, designed from the outset to exploit the peculiarities of NAND Flash. This approach, called PBFilter, organizes the index structure in a pure sequential way to avoid the sideeffects mentioned above. Key lookups are sped up thanks to two principles called Summarization and Partitioning. We instantiate these principles by data structures and algorithms based on Bloom Filters and show the effectiveness of this approach through a comprehensive performance analysis. PBFilter can be instantiated with different Summarization and Partitioning algorithms opening up a new way to think about indexing Flash-resident data.

Introduction

NAND Flash memory stands out as the best adapted storage medium for an ever wider spectrum of mobile and embedded devices (PDAs, cell phones, cameras, sensors, smart cards, USB keys, mp3 readers etc). The reasons for this success include shock resistance, size, energy consumption, performance and ease of on-chip integration. As capacity increases and price decreases, Flash memory is being considered as a mid-term serious competitor even for traditional disks [START_REF] Birrel | A Design for High-Performance Flash Disks[END_REF]. However, NAND Flash exhibits specific hardware characteristics making database management very challenging. Reads and writes are done at a page granularity, as in traditional disks, but writes are more time and energy consuming than reads. In addition, a page cannot be rewritten before erasing the complete block containing it, a costly operation. Finally, a block wears out after 10 5 to 10 6 repeated write/erase cycles. Due to this, updates are usually performed "outof-place", meaning that a page is copied in another location before being modified, entailing address translation and garbage collection overheads. Database storage models dedicated to NAND Flash have been proposed in [START_REF] Kim | A Small DBMS for Embedded System with Flash Memory[END_REF][START_REF] Lee | Design of Flash-Based DBMS: An In-Page Logging Approach[END_REF]. The strong point of IPL [START_REF] Lee | Design of Flash-Based DBMS: An In-Page Logging Approach[END_REF] is to offer a storage and buffering approach hiding the Flash peculiarities to the upper layers of the DBMS. The idea is delaying the updates in Flash thanks to a log stored in each physical block and rebuilding the accurate version of each page at load time. The updates are physically applied to a page when the corresponding log region becomes full. While elegant, this general method is not well suited to manage hot spot data in terms of updates, like index pages, because of frequent log overflows. Recent works addressed this issue by adapting B+Tree-like structures to NAND Flash [START_REF] Bityutskiy | JFFS3 Design Issues[END_REF][START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF][START_REF] Wu | An Efficient B-Tree Layer for Flash-Memory Storage Systems[END_REF]. While different in realization, these methods rely on a similar approach: to delay the index updates thanks to a log dedicated to the index and batch them with a given frequency with the objective to group updates related to a same index node. We call these methods batch methods hereafter. Batch methods entail a new trade-off between the number of reads and writes but good performance for both is difficult to achieve at once due to the Flash characteristics. In addition, read/write performance is no longer the sole metrics of interest in the Flash context. First, RAM consumption is a primary concern in many mobile and embedded devices, today the main target of Flash chip manufacturers. Second, the data organization in Flash impacts the costs of address translation and stale data reclamation. These indirect costs have been shown high and not easily predictable [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF]. Hence, we argue that a larger set of metrics (including RAM consumption and Flash usage indirect costs) has to be considered when designing an indexing technique for Flash-resident data. We also believe that a thorough rethinking of the indexing methods is mandatory to tackle accurately the Flash constraints rather than adapting traditional index structures initially designed for supporting random I/O. In this paper, we propose a new indexing approach designed to exploit natively the peculiarities of NAND Flash. NAND Flash is best suited to support sequential writes and page-level reads. Hence, the indexing approach proposed in this paper, called PBFilter, relies on producing only sequential writes and page-level reads. Let us imagine an index organized as a pure sequential append-only list of (key, pointer) pairs. This would avoid "out-of-place" updates, and then save address translation and stale data reclamation costs, provided a simple buffering strategy is followed. The question becomes how to look up a given key in a sequential list with acceptable performance? The PBFilter approach relies on two principles. Summarization consists in building a sequential summary of the (key, pointer) list and in doing the lookup first in this summary to determine the region of interest of the list. Different summarization algorithms can be envisioned introducing an interesting trade-off between the compression ratio of the summary and its accuracy. Partitioning consists in splitting a sequential structure (e.g., the key-pointer list or its summary) vertically in such a way that only a subset of partitions need to be scanned at lookup time. Again, different partitioning strategies can be devised introducing a trade-off between the number of partitions and the RAM consumption. The key idea behind Summarization INRIA and Partitioning is that both help speeding up the lookup without hurting sequential writes and page-level reads. The contribution of this paper is threefold: -To propose a new approach based on Summarization and Partitioning for indexing Flashresident data, which: (1) avoids the penalty of address translation and garbage collection, (2) minimizes RAM consumption and (3) makes read/write performance and resource consumption (RAM and Flash) fully predictable.

-To instantiate this generic approach with concrete data structures and algorithms based on Bloom Filters [START_REF] Bloom | Space/time tradeoffs in hash coding with allowable errors[END_REF] and demonstrate that the preceding objectives can be reached while maintaining very good lookup performance.

-To propose a comprehensive set of metrics capturing the behavior of Flash-based indexing methods and compare them through a precise analytical performance model.

In addition, as PBFilter can be instantiated with different Summarization and Partitioning algorithms, we expect that this work can open up interesting research directions related to the indexing of Flash-resident data.

The paper is organized as follows. Section 2 introduces the main characteristics of NAND Flash, studies the related work and states the problem addressed in this paper. Section 3 details the PBFilter indexing scheme. Section 4 presents a PBFilter instantiation through partitioned Bloom Filter summaries. Section 5 describes our analytical performance model, gives comparisons with batch methods, and shows preliminary experimental results. Section 6 sketches interesting open issues and Section 7 concludes.

2 Problem statement

NAND Flash characteristics

Flash devices come today in various form factors such as compact flash cards, secure digital cards, smart cards, USB token, and even as composite chip modules providing a disk like bus interface. Whatever the form factor and the manufacturer, Flash chips share common characteristics. A typical NAND Flash array is divided into blocks (the number of which depends on the Flash module capacity), in turn divided into pages (e.g., 32-64 pages per block) themselves divided into sectors (e.g., 4-8 sectors per page). Read and write operations usually happen at page granularity, but can also apply at sector granularity if required. A page is typically 512-2048 bytes. A page can only be rewritten after erasing the entire block containing it (usually named block-erase-before-rewrite constraint). Page write cost is higher than read, both in terms of execution time and energy consumption, and the block erase requirement makes writes even more expensive. A block wears out after 10 5 to 10 6 repeated write/erase cycles, requiring write load to be spread out evenly across the memory.

These hardware constraints make the management of updates complex. This complexity is slightly mitigated by the decomposition of a page into sectors. Sectors can be written independently in the same page, allowing one write per sector before requiring erasing the block. To avoid erasing blocks too frequently, updates are usually performed "out-of-place", meaning that a page to be updated is copied in another block and its initial image becomes garbage. This introduces the need for: (1) a translation mechanism relocating the pages and making their address invariant through indirection tables and (2) a garbage collection mechanism erasing blocks, either lazily (waiting that all pages of the block become stale) or eagerly (moving the active pages still present in the block before erasing it). Both mechanisms are combined in a Flash Translation Layer (FTL), usually integrated in the firmware of the Flash device [START_REF]Understanding the Flash Translation Layer (FTL) specification[END_REF].

RR n° 6548

For illustration purpose, Table 1 4 presents the execution time and energy consumption of various Flash devices for read and write operations at page granularity. The last row reports raw numbers, showing the performance of the hardware only. We can note very high discrepancies between the platforms, both in absolute times and in terms of the read/write ratio, with the commonality that writes are always more expensive than reads. As precisely studied in [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF] these discrepancies are explained partly by the raw chip characteristics and partly by the firmware managing the FTL. Raw chip characteristics are public but FTL are usually proprietary and constitute the primary source of performance unpredictability.

Related work

Several storage and indexing models have been specifically designed for EEPROM and NOR Flash memories [START_REF] Bolchini | Logical and Physical Design Issues for Smart Card Databases[END_REF][START_REF] Sen | Efficient Data Management on Lightweight Computing Device[END_REF]. Those models consider memories with a byte or word granularity for read and write operations, making them irrelevant in a NAND Flash context. Some other work [START_REF] Kim | A Small DBMS for Embedded System with Flash Memory[END_REF][START_REF] Lee | Design of Flash-Based DBMS: An In-Page Logging Approach[END_REF] adopted the idea of log-structured file systems (LFS) [START_REF] Rosenblum | The Design and Implementation of a Log-Structured File System[END_REF] to design or improve database storage models dedicated to NAND Flash, without proposing new index methods. For example, [START_REF] Lee | Design of Flash-Based DBMS: An In-Page Logging Approach[END_REF] proposed a storage and buffering model enabling existing DBMS to run on Flash with a minimal adaptation of the engine, but this solution is sub-optimal for hot-spot data structures like indexes, as explained in Section 1.

With the broadening of NAND Flash usage, recent work has considered more specifically the indexing problem in NAND Flash. As for traditional indexes, we can distinguish the hashbased and tree-based families of indexing methods. Little attention has been paid so far to hashbased methods in Flash. The reason is most probably that hashing performs well only when the number of buckets can be made high and when the RAM can accommodate one buffer per bucket, but RAM is often a scarce resource in Flash-based devices. One exception is the Microhash indexing structure designed to speed up lookups in sensor devices [START_REF] Zeinalipour-Yazti | An Efficient Index Structure for Flash-Based Sensor Devices[END_REF]. In this particular context, sensed data vary on a small domain (e.g., temperature values) so that the number of buckets can remain low. However, this method is not general and not adapted to large domain indexes like indexes on primary keys.

In the tree-based family, one work considers also the indexing of sensed data [START_REF] Mani | TINX -A Tiny Index Design for Flash Memory on Wireless Sensor Devices[END_REF]. This work proposes a tiny index called TINX based on a specific unbalanced binary tree. The performances revealed by the authors (e.g., 2500 page reads to retrieve one record among 0.6 million records) disqualify this method for large databases. To the best of our knowledge, all other papers suggest adaptations of the well-known B+Tree structure. Regular B+Tree techniques built on top of FTL have been shown to be poorly adapted to the Flash characteristics [START_REF] Wu | An Efficient B-Tree Layer for Flash-Memory Storage Systems[END_REF]. Indeed, each time a new record is inserted into a file, its key must be added to a B+Tree leaf node, incurring an out-of-place update of the corresponding Flash page. To avoid such updates, BFTL [START_REF] Wu | An Efficient B-Tree Layer for Flash-Memory Storage Systems[END_REF] constructs an "index unit" for each inserted primary key and organizes the index units as a kind of log. A large buffer is allocated in RAM to group the various insertions related to the same B+Tree node in the same log page. To maintain the logical view of the B+Tree, a node translation table built in RAM keeps, for each B+Tree node, the list of log pages which contain INRIA index units belonging to this node. In order to bound the size of these lists and therefore the RAM consumption as well as the lookup cost, each list is compacted when a threshold (e.g., 5 log pages in the list) is reached. At this time, the logged updates are batched to refresh the physical image of the corresponding B+Tree node.

FlashDB [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF] mixes Regular B+Tree and BFTL to take the best of each, using a self-tuning principle linked to the query workload. JFFS3 proposes a slightly different way to optimize B+Tree usage [START_REF] Bityutskiy | JFFS3 Design Issues[END_REF]. Key insertions are logged in a journal and are applied in the B+Tree in a batch mode. A journal index is maintained in RAM (recovered at boot time) so that a key lookup applies first in the journal index and then in the B+Tree.

In short, all the B+Tree based methods rely on the same principle: (1) to delay the index updates thanks to a log and batch them with the objective to group updates related to the same index node; (2) to build a RAM index at boot time to speed up the lookup of a key in the log;

(3) to commit the log updates with a given commit frequency (CF) in order to bound the log size. This introduces the following trade-off:

-The larger CF, the smaller the number of writes but the higher the number of reads (both at lookup and insertion time).

Unfortunately, this trade-off is more difficult to capture and to exploit than in a traditional (disk-based) context. First, writes generate out-of-place updates entailing an indirect garbage collection cost. This cost depends on the strategy implemented in the underlying FTL, with large discrepancies among the platforms [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF]. Second, the way the index structure is organized in Flash also impacts the garbage collection cost and the Flash occupancy, depending on whether stale data is grouped in a small set of pages or is spread over all pages occupied by the index. Third, the larger CF, the larger the RAM consumption. This consequence is often ignored while it may definitely proscribe the use of an indexing method for a particular platform.

Problem statement

In the light of the preceding discussion, more complete and accurate metrics seem mandatory to help assessing the adequacy of an indexing method to a target platform. We propose evaluating a Flash-based indexing method according to the following metrics:

-M1: Read cost at lookup time.

-M2: Read and write cost at insertion time.

-M3: Flash usage in terms of space occupancy and effort to reclaim stale data.

-M4: RAM consumption.

-M5: Performance and resource consumption predictability.

M1 and M2 are the usual performance metrics for indexing methods. The trade-off between M1 and M2 is tied to the application (read or write intensive). M2 prioritizes insertions, usually more frequent than deletes or updates in database applications. Depending on the targeted platform, the metrics of interest can be execution time or energy consumption. To answer both requirements, M1 and M2 are expressed in terms of number of read and write operations.

The objective of metric M3 is to capture (1) total amount of Flash occupied by the index and (2) indirect cost incurred by garbage collection, used to decrease this amount by reclaiming stale data. Indirect costs are by nature difficult to estimate and have been shown directly tight to the underlying FTL [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF]. To tackle this issue, we suggest expressing metric M3 by two values, namely the total number of active pages occupied by the index (i.e., pages containing at least one valid item) and the total number of pages containing only stale data (which can be reclaimed without copying data). Comparing these two values with the raw size of the index (total size of the valid items only) gives an indication about the quality of the Flash occupancy and about the effort to reclaim stale space, independently of the FTL implementation.

RR n° 6548

Metric M4 is of utmost importance for most embedded and mobile devices (smart cards, sensors, USB dongles, etc) which are today the primary targets of Flash storage. To illustrate this, secure chips and sensors are equipped with Kilo-bytes sized RAM. Even if not all platforms exhibit so severe RAM constraints, we attach a particular importance to this metric because it may definitely disqualify certain techniques. Metric M4 is expressed in KB and comprises the buffers to read from and write to the Flash and the main memory data structures required by the indexing method.

Finally, metric M5 captures the performance and resource consumption predictability. Predictability is an important concern in database systems in general and in Flash-based DBMS in particular considering the discrepancy among FTL implementations. To avoid making this metric fuzzy by reducing it to a single number, M5 is qualitative instead of quantitative and is spit into three dimensions. First, we attach four ranking to the dependence of the indexing method wrt the underlying FTL, considered as the primary source of performance uncertainty: totally dependent of the FTL, independent of the FTL's garbage collection mechanism (i.e., no stale data is ever produced or stale data is reclaimed by the indexing method itself), independent of the FTL's address translation mechanism (i.e., valid data never moves or moves are managed by the indexing method itself), totally independent of the FTL. The second dimension of performance predictability captures whether the values measured for M1 and M2 can be bounded whatever their absolute value (Boolean metric). Finally, resource consumption predictability is also a Boolean metric expressing whether the RAM requirement can be bounded whatever its absolute value.

Finding the best trade-off between these five metrics is application and platform dependent. However, it is important to study all the metrics, because (1) a dramatically bad behavior on a metric may disqualify an indexing method and (2) this assures that all metrics of interest have been considered for the targeted context.

The more metrics are positively met, the wider the application domain is. Typically, in the embedded device context where resources are highly constrained, the five metrics are significant.

To the best of our knowledge, no existing Flash-based indexing method performs well on all the metrics.

PBFilter indexing scheme

PBFilter is an alternative to the "batch" indexing methods. The general idea is to perform index updates eagerly and make this acceptable by organizing the complete database as a set of sequential data structures, as pictured in Figure 1. The objective is to transform database updates into append operations so that writes are produced sequentially, an optimal scenario for NAND Flash.

The database updating process is as follows. When a new record is inserted, it is added at the end of the record area (RA). Then, a new index entry composed by a couple <key, pt> is added at the end of the key area (KA), where key is the primary key of the inserted record 5 and pt is the record physical address. If a record is deleted, its identifier (or its address) is inserted at the end of the delete area (DA) but no update is performed in RA nor in KA. A record modification is implemented by a deletion (of the old record) followed by an insertion (of the new record value). To search for a record by its key, the lookup operation first scans KA, retrieves the required index entry if it exists, check that pt ∉DA and gets the record in RA. Assuming a buffering policy allocating one buffer in RAM per sequential data structure, this database updating process never incurs rewriting a same page in Flash.

The benefits provided by this simple database organization are obvious with respect to the met-INRIA rics introduced in Section 2. Metric M2: a lower bound is reached in terms of reads/writes at insertion time since: (1) the minimum of information is actually written in Flash (the records to be inserted and their related index entries and no more), (2) new entries are inserted at the index tail without requiring any extra read to traverse the index and (3) pages do not move, thus physical pointers can be used and FTL is not required, saving the overhead incurred by the FTL address translation mechanism 6 . Metric M3: neglecting DA, a lower bound is reached in terms of Flash space occupancy, again because the information written is minimal and never updated.

Hence, the number of active pages containing the index is equivalent to the raw size of this index. The size of DA measures the space overhead incurred by this method (expected to be low considering that deletes are not frequent in most databases). In addition, since a Flash page is never updated nor moved, no stale data is ever produced and the garbage collection cost is saved. Metric M4: a single RAM buffer of one page is required per sequential structure (RA, KA and DA). The buffer size can even be reduced to the size of a Flash sector in highly constrained environments (the benefit of a single I/O per page is lost but a page is still never moved making the garbage collection needless). Metric M5: PBFilter can bypass the FTL address translation layer (see footnote) so that performance uncertainties linked to the FTL are removed. In terms of resource consumption, the RAM usage is bounded as discussed above.

The drawbacks of this organization are obvious as well. The performance reached for metric M1 is far from being satisfactory since the read cost is (⎟KA⎟/2 + ⎟DA⎟ + 1) on the average, where ⎟ ⎟ denotes the page cardinality of a structure. Consequently, despite the removal of the FTL costs, performance predictability (metric M5) is not achieved since the uncertainty of the read cost at lookup time (for an existing record) is up to (⎟KA⎟ -1).

Figure 1. Database organization

Suggesting an indexing method entailing such bad and unpredictable lookup cost is senseless at first glance. The objective is to circumvent these two drawbacks with a minimal degradation of the benefits listed above. To this end, we introduce two additional principles.

The first one is Summarization. Summarization refers to any method which can condense the information present in KA and can produce the condensed information sequentially. Let us consider an algorithm that condenses each KA page into a summary record. Summary records can be sequentially inserted into a new structure called SKA through a new RAM buffer of one page (or sector) size. Then, lookups do a first sequential scan of SKA and a KA page is accessed for every match in SKA in order to retrieve the requested key (if it exists). Summarization introduces an interesting trade-off between the compression factor c (c=⎟KA⎟/⎟SKA⎟) and the fuzziness factor f (i.e., percentage of false positives) of the summary, the former decreasing the I/O required to traverse SKA and the latter decreasing the I/O required to access KA. The RR n° 6548 net effect of summarization is replacing the lookup cost in KA by (⎟KA⎟/2c + f⎟⎟KA⎟⎟/2) on the average, where ⎟⎟ ⎟ denotes the element cardinality of a structure. The positive impact on metrics M1 and M5 can be very high for favorable values of c and f. The negative impact on M4 is limited to a single new buffer in RAM. The negative impact on M2 and M3 is linear with ⎟SKA⎟ and then depends on c. Different algorithms can be considered as candidate "condensers", with the objective to reach the higher c with the lower f, the only requirement being to respect the following property: summaries must allow membership tests with no false negatives.

The second principle is Partitioning. The idea behind partitioning is to vertically split a sequential structure into p sequential partitions so that only p'<p partitions have to be scanned at lookup time. Partitioning can apply to KA, meaning that the encoding of keys is organized in such a way that lookups do not need to consider the complete key value to evaluate a predicate. Partitioning can also apply to SKA if the encoding of summaries is such that the membership test can be done without considering the complete summary value. The larger p, the higher the partitioning benefit and the better the impact on metrics M1 and M5. On the other hand, the larger p, the higher the RAM consumption (p buffers) or the higher the number of writes into the partitions (less than p buffers) with the bad consequence of reintroducing page moves and garbage collection. Again, different partitioning strategies can be considered with the following requirement: to increase the number of partitions with neither significant increase of RAM consumption nor need for garbage collection.

The question is whether condenser algorithms and partitioning strategies satisfying the requirements above actually exist and make the general approach viable. In the next section, we present one solution for each problem and show that, taken together, they lead to an approach satisfying the problem stated in Section 2, that is exhibiting at least a satisfactory behavior for all metrics at once. We do not argue that no other or better solutions exist. On the contrary we expect that this study is the first step towards the definition of a family of solutions.

PBFilter Instantiation

Bloom Filter Summaries

The Bloom Filter data structure has been designed for representing a set of elements in a compact way while allowing membership queries with a low rate of false positives and no false negative [START_REF] Bloom | Space/time tradeoffs in hash coding with allowable errors[END_REF]. Hence, it presents all the characteristics required for a condenser.

A Bloom filter to represent a set A={a 1 , a 2 , … a n }of n elements is described by a vector v of m bits, initially all set to 0. The Bloom filter uses k independent hash functions, h 1 , h 2 , … h k , each producing an integer in the range [1,m]. For each element a i ∈A, the bits at positions h 1 (a i ), h 2 (a i ), ..., h k (a i ) in v are set to 1 (a particular bit might be set to 1 multiple times). Given a query for element a j , all bits at positions h 1 (a j ), h 2 (a j ), ..., h k (a j ) are checked. If any of them is 0, then a j cannot be in A (Bloom filter do not generate false negatives). Otherwise we conjecture that a j is in A although there is a certain probability that we are wrong. The parameters k and m can be tuned to make the probability of false positives extremely low [START_REF] Gonnet | Handbook of Algorithms and Data Structures[END_REF].

This probability, called the false positive rate and denoted by f in the sequel, can be calculated easily assuming the k hash functions are perfectly random and independent. After all the elements of A are hashed into the Bloom filter, the probability that a specific bit is still 0 is ( )

m kn kn e m / / 1 1 - ≈ - .
The probability of a false positive is then

( ) ( ) ( ) k m kn k kn e m / 1 / 1 1 1 - - ≈ - - = ( ) k p - 1 for p= m kn e / -
. The salient feature of Bloom filters is that three performance metrics can be traded off against one another: computation time (linked to the number k), space occupancy (linked to the number m), and false positive rate f. Table 2 illustrates these trade-offs for some values of k and m. This table shows that a small increase of m may allow a dramatic benefit for f if the optimal value of k is selected. We consider that k is not a limiting factor in our context, since methods exist to obtain k hash values by calling only INRIA three times the hash function, while giving the same accuracy as by computing k independent hash functions [START_REF] Dillinger | Fast and Accurate Bitstate Verification for SPIN[END_REF]. Bloom filters can be used as a condenser algorithm in PBFilter as follows. For each KA page, a Bloom filter summary is built by applying k hash functions to each index key present in that page. This computation is performed when the KA page is full, just before the RAM buffer containing it is flushed to the Flash. The computed Bloom filter summary is stored in the RAM buffer allocated to SKA. In turn, the SKA buffer is flushed to the Flash when full. At lookup time, the searched key a i is hashed with the k hash functions (step 1). Then, SKA is scanned to get the first Bloom filter summary having all bits at positions h 1 (a i ), h 2 (a i ), ..., h k (a i ) set to 1 (step 2). The corresponding page of KA is directly accessed (step 3) and the probability that it contains the expected index entry (a i ,pt) is (1-f). Otherwise, the scan continues in SKA. A fourth step is required to check that pt ∉DA before accessing the record in RA. We make the assumption that inserts vastly outnumber deletes so ⎟DA⎟ is small enough to have little effect on the total read cost of the lookup. We believe that this assumption is usually met in the database context but Section 6 discusses an optimization if it turns out to be wrong.

Partitioned Summaries

Despite the benefits of summarization, the lookup performance remains linked to the size of SKA (on the average, half of SKA needs to be scanned). The lookup performance can be improved by applying the partitioning principle suggested in section 3. Each Bloom filter is then vertically split into p partitions (with p ≤ m), so that the bits in the range [1 .. m/p] belong to the first partition, the bits in the range [((i-1)*m/p + 1) .. (i*m/p)] belong to the i th partition, etc. When the SKA buffer is full, it is flushed into p Flash pages, one per partition. By doing so, each partition is physically stored in a separate set of Flash pages. When doing a lookup for key a i , instead of reading all pages of SKA, we need to get only the SKA pages corresponding to the partitions containing the bits at positions h 1 (a i ), h 2 (a i ), ..., h k (a i ). The benefit is a cost reduction of the lookup by a factor p/k. As already stated, the larger p, the higher the partitioning benefit but also the greater the RAM consumption (p buffers) or the greater the number of writes and the need for garbage collection (if the number of buffers is less than p, buffers must be flushed while the corresponding partition pages are not full, entailing several flushes in the same page, then page rewrites).

We propose below a partitioning mechanism which exhibits the nice property of supporting a dynamic increase of p with no impact on the RAM consumption and no need for a real garbage collection (as discussed at the end of the section, stale data are naturally grouped in the same blocks which can be erased as a whole at low cost). This comes at the price of introducing a few reads and extra writes at insertion time. The proposed mechanism relies on: (1) the usage of a fixed amount of Flash as a persistent buffer to organize a stepwise increase of p and (2) the fact that a Flash page is divided into s sectors (usually s=4) which can be written independently.

The former point gives the opportunity to reclaim the Flash buffer at each step in its integrality (i.e., without garbage). The latter point allows s writes into the same Flash page before requiring copying the page elsewhere.

Figure 2 illustrates the proposed partitioning mechanism. The size of the SKA buffer in RAM is set to the size of a Flash page and the buffer is logically split into s sectors. The number of initial partitions, denoted next by L1 partitions, is set to s and one Flash page is initially allocated to each L1 partition. The first time the SKA buffer in RAM becomes full (step 1), each sector s i (with 1≤i≤s) of this buffer is flushed in the first sector of the first page of the i th L1 partition.

RR n° 6548

The second flush of the SKA buffer will fill in the second sector of the first page of each L1 partition and so forth until the first page of each L1 partition becomes full (i.e., after s flushes of the SKA buffer). A second Flash page is then allocated to each L1 partition and the same process is repeated until each partition contains s pages (i.e., after s 2 flushes of the SKA buffer). Each L1 partition contains 1/s part of all Bloom filters (e.g., the i th L1 partition contains the bits in the range [((i-1)*m/s + 1) .. (i*m/s)]).

At this time (step 2), the s L1 partitions of s pages each are reorganized (read back and rewritten) to form s 2 L2 partitions of one page each. Then, each L2 partition contains 1/ s 2 part of all Bloom filters. As illustrated in Figure 2, each L2 partition is formed by projecting the bits of the L1 partition it stemmed from on the requested range, s times finer (e.g., the i th L2 partition contains the bits in the range [((i-1)*m/s 2 + 1) .. (i*m/s 2 )]). Step 3 L3 partitions

Figure 2. Dynamic partitioning

After another s 2 SKA buffer flushes (step 3), s new L1 partitions have been built again and are INRIA reorganized with the s 2 L2 partitions to form (s 2 +s 2 ) L3 partitions of one page each and so forth. The limit is p=m after which there is no benefit to partition further since each bit of bloom filter is in a separate partition. After this limit, the size of partitions grows but the number of partitions remains constant (i.e., equal to m).

The benefit of partitioning dynamically SKA is significant with respect to metrics M1 and M5 since the lookup cost can be made low and almost constant whatever the size of the indexed file. Indeed, a lookup needs to consider only k Li partitions of one page each (assuming the limit p=m has not been reached and Li partitions are the last produced) plus min (k ,s) L1 partitions, the size of which vary from 1 to s pages. This leads to an average cost of (k + min (k, s) * s/2), usually with s=4. The RAM consumption (metric M4) remains unchanged, the size of the SKA buffer being one page (note that extending it to s pages would save the first iteration). The impact on metric M2 is an extra cost of about

⎡ ⎤ ∑ i i s 2 log * 2 2
reads and writes (see the cost model for details). This extra cost may be considered important but is strongly mitigated by the fact that it applies to SKA where each page condenses B p /m records, where B p is the size of a Flash page in bits (B p /m is likely to be greater than 1000). Section 5 will show that this extra cost is low compared to the insertion cost of existing indexing techniques. Section 5 will also show the low impact of partitioning on metric M3 for the same reason, that is the high compression ratio obtained by Bloom filters making SKA small with respect to KA.

At the end of each step i, and after Li partitions have been built, the Flash buffer hosting L1 partitions and the pages occupied by L i-1 partitions can be reclaimed. Reclaiming a set of stale pages stored in the same block is far more efficient than collecting garbage crumbs spread over different pages in different blocks. The distinction between garbage reclamation and garbage collection is actually important. Garbage collection means that active pages present in a block elected for erasure must be moved first to another block. In addition, if at least one item is active in a page, the complete page remains active. In methods like BFTL, active IUs can be spread over a large number of pages in an uncontrolled manner. This generates a worst situation where many pages remain active while they contain few active index units and these pages must be often moved by the garbage collector. PBFilter never generates such situations. The size of the Flash buffer and of the L i partitions is a multiple of s 2 pages and these pages are always reclaimed together. Blocks are simply split in areas of s 2 pages and a block is erased when all its areas are stale.

Hash then Partition

As stated above, the benefit of partitioning is a cost reduction of the lookup by a factor p/k. The question is whether this factor can still be improved. When doing a lookup for key a i in the current solution, the probability that positions h 1 (a i ), h 2 (a i ), ..., h k (a i ) fall into a number of partitions less than k is low, explaining the rough estimate of the cost reduction by the factor p/k This situation could be improved by adding a hashing step before building the Bloom filters. Each Bloom filter is split into q buckets by a hash function h 0 independent of h 1 , h 2 , ..., h k ,. Each time a new key is inserted in KA, h 0 is applied first to determine the right bucket, then h 1 , h 2 , ..., h k are computed to set the corresponding bits in the selected bucket. This process is similar as building q small Bloom filters for each KA page. The experiments we conducted led to the conclusion that q must remain low to avoid any negative impact on the false positive rate. Thus, we select q=s (with s usually equals to 4). The benefit of this initial hashing is guaranteeing that the k bits of interest for a lookup always fall into the same L1 partition, leading to an average cost of (k + s/2) for scanning SKA.

RR n° 6548 (3) BFTL with periodic compaction of the node translation table, denoted by BFTL2. BTree is the best representative of traditional disk-based indexing methods and will serve as a point of reference to assess the benefit of designing specific indexing methods for Flash. BFTL2 [START_REF] Wu | An Efficient B-Tree Layer for Flash-Memory Storage Systems[END_REF] is the best known representative of batch methods. Finally, BFTL1 is added in the comparison to understand the impact of (not) bounding the size of the log in batch methods. We do not integrate FlashDB [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF] in the comparison because it corresponds to a dynamic mix of BTree and BFTL2. Hence its behaviour is difficult to translate accurately in a cost model and its main performance metrics would be always in-between of BTree and BFTL2. Other variations of Treebased batch methods could also have been considered but the main objective is comparing opposite approaches (traditional, batch, Summarization & Partitioning), rather than focusing on variations.

This objective also led us to build a precise analytical cost model rather than measuring different implementations on the same hardware platform. Indeed, traditional and batch methods rely on a FTL while PBFilter is designed to bypass it. Comparing numbers obtained on top of an opaque and unpredictable FTL [START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF] does not make sense and would be considered unfair. By contrast, the cost model parameters can be easily set to significant numbers representing specific hardware features.

Section 5.4 reports on real experiments made with PBFilter and shows the accuracy of the cost model.

5.1.2

Performance Metrics According to the problem statement introduced in Section 2.3, our performance analytical model distinguishes the following metrics:

-R: average number of page reads to look up a key.

-W: total number of page writes to insert N records.

-IR: total number of page reads to insert N records.

-RC: RAM consumption in KB.

-FO: total number of Flash pages occupied by the index structure, i.e. containing at least one valid index information.

-FE: total number of Flash pages which contain only stale data and can be erased without any data move.

Let us come back to the distinction between FO and FE, introduced in Section 2.3 to capture the garbage collector cost without making assumption on the FTL implementation. Let us denote by VD (resp. SD), the set of index data currently valid (resp. stale). If an index method never produces stale data, FO=VD and FE=0. If stale data are produced (the usual case) but are well clustered into Flash pages, FO=VD and FE=SD. If however, valid and stale data are mixed into the same Flash pages, FO can be up to VD+SD (FE being the complement).

Parameters and Formulas

The parameters and constants used in the analytical model are listed in Table 3 andTable 4, respectively. 6. To make the formulas as precise as possible, we use Yao's Formula [START_REF] Yao | Approximating the Number of Accesses in Database Organizations[END_REF] when necessary.

INRIA Table 5 contains basic formulas used in the cost model and the cost model itself is presented in Table

-Yao's Formula: Given n records grouped into m blocks (1<m≤n), each contains n/m records. If k records (k≤n-n/m) are randomly selected, the expected number of blocks hit is: Average fill factor of B+Tree [START_REF] Yao | On Random 2-3 Trees[END_REF] β=2

- ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ + - + - - × = ∏ = k i i n i nd m k m n Yao
Expansion factor of flash storage caused by the buffering policy in BFTL [START_REF] Wu | An Efficient B-Tree Layer for Flash-Memory Storage Systems[END_REF] Sp=2048(bytes) Size of a Flash page

Performance Comparison

We first compare the four methods under test on each metric with the following parameter setting: N=1 million records, Sk=12, C=5 for BFTL2 (a medium value wrt [START_REF] Wu | An Efficient B-Tree Layer for Flash-Memory Storage Systems[END_REF]), and B=7, d=16, k=7 for PBF (which correspond also to medium values). The results are shown in Figures 4(a) to 4(e). The first conclusion which can be drawn from these figures is that each method, except PBF, exhibits a very bad behaviour on at least one (and often more) metric. BTree exhibits a very good lookup performance but the price to pay is an extremely high write cost and consequently a high number of stale pages produced (FE). This proves that regular indexing techniques cannot accommodate Flash storage with no adaptation 7 . BFTL has been primarily designed to decrease the write cost incurred by BTree and Figures 4(c) and 4(e) shows the benefit. However, BFTL1 incurs a high lookup cost and a high RAM consumption given that the node translation lists are not bounded. The IR cost is also very bad since each insertion incurs a traversal of the tree. By bounding the size of the node translation lists, BFTL2 exhibits a much better behaviour for the metric R, IR and RC (though RC remains very high) at the expense of a higher number of writes (to refresh the index nodes) and a higher Flash consumption (BFTL RR n° 6548 mixing valid and stale data in the same Flash pages). Hence, these figures show that PBF is the sole indexing method providing acceptable performance on all metrics at once. In this setting, PBF performance is not simply satisfactory, it outperforms BFTL1 on all metrics, BTree on metrics IR, W and FO and BFTL2 on metrics IR, W, RC and FO while obtaining as good performance as its competitors on metrics R. In addition, PBF exhibits an excellent behaviour in terms of RC, consuming only 7 buffers of 2KB (1 buffer to read from Flash, 4 buffers to write the structures SKA and another 2 for KA and DA). Note that the RAM requirement for SKA can even be reduced to a single buffer, as explained in Section 4.2, leading to a total RAM consumption of 8KB 8 . This makes PBF particularly adapted to mobile and embedded devices.

BTree being disqualified by its dramatically bad behaviour in terms of W and FO, the rest of the study concentrates on BFTL2 and PBF (BFTL1 is considered only when this allows drawing interesting conclusions).

For further analysis, we vary parameter C, keeping the preceding values for the other parameters, to determine whether BFTL2 could outperform PBF in another setting. The influence of C on metrics W, FO and FE is pictured in Figure 4(f). As expected, W and FO decrease as C increases since the tree reorganizations become less frequent (FE stays equal to 0). Actually, W and FO decrease asymptotically up to reach the same values as BFTL1 which is nothing but BFTL2 with an infinite C. Whatever C, the performance of BFTL2 on W and FO is still worse than PBF. In addition, R grows linearly with C (see formula in Table 6) so that BFTL2 needs reading 105 pages to do a lookup for C=30. The impact of increasing C is also very bad on RC (Figure 4(d) makes this clear comparing BFTL1 and BFTL2). Conversely, favourable values of C for R (e.g., R=18 for C=5) have a dramatic impact over W and FO (e.g., W=FO=241466 for C=5). As a conclusion, BFTL2 performs better than PBF on no metric whatever C. (i) use a logarithmic scale for readability). BFTL2 scales better than PBF in terms of R and even outperforms PBF for N greater than 2.5 million records (though R performance of PBF remains acceptable). Unfortunately, BFTL2 seems not the ideal alternative for high N because it scales very badly in terms of W. BFTL1 scales much better in terms of W but exhibits unacceptable performance for R and RC. Let us come back to PBF. PBF scales also badly in terms of W. The reason is that the cost of repartitioning becomes dominant for large N and repartitioning occurs at every Flash buffer overflow. A solution for large files is then to increase the size of the Flash buffer hosting the L1 partitions under construction. The comparison between PBF1 and PBF2 on Figure 4(h) shows the benefit of increasing the Flash buffer from 16 pages for PBF1 (that is 4 L1 partitions of 4 pages each) to 64 pages for PBF2 (16 L1 partitions of 4 pages each). Such increase does not impact metric R since the number of reads in L1 partitions does not depend on the number of partitions but of their size (which we keep constant). The impact on metric RC is negligible, especially in environments dealing with very large files (12 more buffers for SKA which could be only 3 pages when organizing the buffer by sectors). This optimization seems very effective for the scalability on W. The scalability on R requires a further optimization. Actually, the bad R performance of PBF is due to the increase of the number of pages in each final partition and of the average accesses to KA which is f*|KA|/2. The growth of the size of each final partition can be compensated by a reduction of k while obtaining a smaller f by increasing d to trade-off with the growth of |KA|. For instance, the values d=24 and k=4 produce even better lookup performance for N=5 million records than the one obtained with d=16 and k=7 for N=1 million records (9 vs. 10). Anyway, future work is required to optimize PBF further for very large files.

To make the comparison as complete as possible, Figures 4(m) and 4(n) analyze the influence of Sk on all methods, keeping the initial values of the other parameters. Regarding metric R,

INRIA

Tree-based methods accommodate large keys better than PBF. The reason is that large keys incur more KA pages and then magnifies the influence of false positives. But again, the performance can be maintained by tuning parameters d and k so as to reduce the false positive rate in the required proportion. In Figures 4(m), we can note that the performance with some special number of Sk is even better than that with bigger Sk, simply because only 1 KA page needs to be accessed for the Bloom filter qualified by the lookup for such situation while 2 accesses for others 9 .The difference between PBF1 (d=16 and k=7) and PBF3 (d=20 and k=7) on both figures illustrates the impact of this tuning 10 . The next subsection discusses more deeply the tuning of PBF.

Tuning PBFilter

As shown in the previous section, tuning d and k allows adapting gracefully PBF to various situations. It is therefore important to delimit the range of tuning capabilities provided by PBF and understand their impact on all metrics.

The good behavior of PBF highlighted above has been obtained with relatively high values of d and k (d=16 and k=7). The size of the Bloom filters m has actually a limited impact on the size of the global index structure (in the measured setting, |SKA|/|KA| = 0.10). It mainly impacts the cost of repartitioning, which could also be tuned as suggested above. In addition, the CPU cost incurred by the computation of k hash function is negligible compared to the I/O cost (see next section). This brings high opportunities to tune d and k.

Experimental Results

Figure 3. Secure USB Flash device 9 To ease the repartition process and maximise space occupancy, the Bloom filter size should be a power of 2. If by modifying d, m becomes greater than 2 x , then m is enlarged to 2 x+1 and each Bloom filter is computed on a larger number n of keys (from two consecutive pages of KA) required to recover the expected value of d. The consequence is simply reading 2 KA pages instead of 1 for the Bloom filter(s) qualified by the lookup. 10 Another way to deal with large Sk is hashing the keys thanks to a collision-free hash function (e.g., HMAC producing a 8 bytes signature) before inserting them in KA. This does not impact the lookup process since only exact-matches are considered.

RR n° 6548

PBFilter has been implemented and integrated in the storage manager of an embedded DBMS dedicated to the management of secure portable folders [START_REF] Anciaux | Restoring the Patient Control over her Medical History[END_REF]. The prototype runs on an experimental secure USB Flash platform provided by Gemalto, our industrial partner. This platform, pictured in Figure 3, is equipped with a smartcard-like secure microcontroller connected by a bus to a large (Gigabyte-sized soon) NAND Flash memory (today the 128MB Samsung K9F1G08X0A module). The microcontroller itself is powered by a 32 bit RISC CPU (clocked at 50 MHz) and holds 64KB of RAM. The DBMS is built on top of a native Gemalto FTL, bypassing the address translation and garbage collection mechanisms but a similar solution is provided by the Samsung S-SIM FTL thanks to the VFL API.

Today, we are not granted permission to publish performance numbers about this platform due to pending patents, one being related to PBFilter [START_REF] Pucheral | System and Method of Managing Indexation of Flash Memory[END_REF]. Anyway, as already stated, real numbers are of little interest when evaluating Flash indexing methods due to the high discrepancy among the platforms. Hence the results are given in terms of number of operations, similarly to the cost model. Experiments have been conducted thanks to a cycle-accurate hardware simulator of the platform for convenience.

We ran our prototype under all the parameter settings used in 5.2 and 5.3. Unsurprisingly, the tests produced exactly the same numbers as those computed by the cost model for all metrics but R. Indeed, the sequential organization and the fixed size of all data structures make the insertion process and the number of repartition steps fully predictable for a given parameter setting, avoiding any uncertainty for IR, W, FO and FE metrics (In the prototype, transaction atomicity is guaranteed thanks to NOR Flash buffers and do not interfere with the NAND Flash management).

The discrepancy related to the R metric deserves a deeper discussion. The cost model computes the false positive rate using the formula given in Section 4.1, assuming the k hash functions are totally independent, a condition difficult to meet in practice. Much work [START_REF] Dillinger | Fast and Accurate Bitstate Verification for SPIN[END_REF][START_REF] Kirsch | Less Hashing, Same Performance: Building a Better Bloom Filter[END_REF] has been done to build efficient and accurate bloom filter hash functions. In our experiment, we compared Bob Jenkins' lookup2, Paul Hsieh's SuperFastHash, and Arash Partow hash over datasets of different distributions (random, ordinal and normal) produced by Jim Gray's DBGen generator. The results show that the degradation of the false positive rate is quite acceptable for the former two hash functions but not for the latter. Table 7 shows the R metric measured for each hash function and data distribution under the setting: N=1 million, Sk=12, d=16, k=7 (the cost model gives R=10 for this setting, as in Figure 4(a)). About the efficiency of hash functions, Bob Jenkins and SuperFastHash are quite fast (6n+35 and 5n+17 cycles respectively, where n is the key size in bytes), and k independent hash values can be obtained by calling only three times the hash function [START_REF] Dillinger | Fast and Accurate Bitstate Verification for SPIN[END_REF].

⎣ ⎦ ⎡ ⎤ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ ∑ = - ) * 1 /( 2 ) 1 ( log ) * 1 * 2 ( * ) 1 * 8 * /( 2 s L Sb i i s L M Sp N ⎡ ⎤ s L Nr s L s L Sb Nr i i * 1 * ) * 1 * 2 ( ) / 1 / %( 2 ) 1 ( log 2 + ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ + ∑ = - Notes: [Note1]
In BFTL, there are five pointers in each Index Unit (data_ptr, parent_node, identifier, left_ptr, right_ptr), explaining factor 5.

[Note2] Yao's formula is used here to compute how many buffer chunks (1 buffer chunk containing B pages) that fb*M records are distributed to, which is the average length of the lists in node translation table for BFTL1.

[Note3] The IUs from the same logical node are stored in different physical pages, so we divide the total number of IUs (fb*M) by the total number of physical pages to get the average number of IUs stored in the same physical page.

[Note4] L1 denotes the number of pages in each initial L1 partition and L1*s is the size of the Flash buffer used to manage them.

RR n° 6548

What if deletions or updates are very frequent?

The PBFilter approach has been preliminary designed to tackle applications where insertions are more frequent and critical than deletes or updates. We believe that this characteristic is common in practice. Let us assume that this assumption is wrong and then the size of DA is high. The solution would be to apply exactly the same techniques as in KA to speed-up the lookup in DA, that is Bloom filter summarization and partitioning. Assuming deletes are as frequent as inserts, all costs should be multiplied roughly by a factor 2 (read cost, write cost, Flash occupancy, RAM usage). Extrapolating the INRIA results presented in Section 5 shows that PBFilter would remain very competitive even in this scenario and that the objective stated in Section 2, that is exhibiting a satisfactory behavior for all metrics at once, is still met.

Can we envision other/better condenser algorithms? We believe that PBFilter can be instantiated in different ways to serve optimally different purposes or tackle different target platforms. For instance, let us assume a context where the read/write cost ratio is so low that metric M2 strongly dominates M1 and where M4 can be slightly relaxed. In this case, we could use a compression algorithm which reaches a higher compression of KA at the price of a decompression in RAM before exploiting each summary record. Partitioning no longer holds in this context but the number of writes in SKA is reduced (no partition to reorganize, reduction of SKA size). An example of such algorithm is compressed Bloom filters [START_REF] Mitzenmacher | Compressed Bloom Filters[END_REF], but any other compression algorithm could be considered as far as membership tests can be performed on the decompressed summaries without false negative. Classifying the algorithms of interest according to the criteria to optimize is part of our future work.

Can we index secondary keys? Summarizing a KA list containing many duplicates does not make sense. Indeed, if the selectivity of the secondary key is lower than (⎟KA⎟/⎟⎟KA⎟⎟), every page of KA would be qualified. A first solution could be to use PBFilter to maintain the set of secondary keys present in the database (without duplicates), doing lookups in this set and attaching a list of pointers to records to each of these keys. How to manage the dynamicity of these pointer lists efficiently in Flash is an open question. Another approach would be to encode KA keys differently. Let us assume first a secondary key with a very low selectivity. The usual way to index such attribute is to build a bitmap index, that is one bitmap per domain value with one bit per record. Bitmaps can be built sequentially and replace key values in KA. The vertical partitioning principle introduced in Section 4.2 can apply to KA with the benefit to read only the requested bitmap at lookup time. If the secondary key has a higher selectivity, Value-List indexes [START_REF] Chan | Bitmap Index Design and Evaluation[END_REF] seem very appropriate to encode keys in KA. The intuition is drawing a parallel between bitmap indexing and number representation in different bases. To illustrate this, a number in the range [0..999] can be represented either by one digit in base 1000 (i.e., one bit set to 1 among 1000 bitmaps) or by three digits in base 10 (i.e., 3 bits set to 1 among 3*10 bitmaps), etc. This introduces a trade-off between space occupancy and lookup performance (e.g., in the latter case, 3 bitmaps have to be scanned). [START_REF] Chan | Bitmap Index Design and Evaluation[END_REF] also introduces Range-Encoded Bitmap Indexes to support range queries. All these techniques seem well adapted to our context since they can be managed sequentially and can be partitioned. A deeper analysis of secondary keys and range queries is part of our future work.

Conclusion

NAND Flash has become the most popular persistent storage medium for mobile and embedded devices and is being considered as a mid-term competitor for traditional disks, urging the database community to design Flash-aware indexing methods. Previous works in this area defer index updates thanks to a log and batch them with the objective to decrease the cost of writes in Flash. This introduces a complex trade-off between read and write performance and entails side-effects on the RAM consumption, Flash consumption and garbage collection cost. While often neglected, these side-effects may disqualify an indexing method for a target platform. This paper introduced a comprehensive set of metrics to capture the behavior of Flash-based indexing methods, including their side-effects. Then, it proposed an alternative to batch methods, called PBFilter, exploiting natively the peculiarities of NAND Flash memory and shown its effectiveness through a comprehensive analytical performance study and preliminary performance measurements. Thanks to its good behavior on all metrics at once, including predictability (very low and bounded RAM requirement, FTL independence), PBFilter is particularly well suited to mobile and embedded devices. It has been integrated in the kernel of an embed-RR n° 6548 ded DBMS and is being validated in this context with the help of our industrial partner. Thanks to its tuning capabilities, PBFilter seems easily adaptable to other Flash-based environments and can meet various application requirements in terms of file size, key size, read/write tradeoffs. Investigating other summarization and partitioning strategies could ever enlarge the application domain of PBFilter and is part of our future work, as well as the optimal management of very large files.

Figures 4 (

 4 Figures 4(g) to 4(i) analyse the scalability of BFTL and PBF methods on R, W and RC varying N from 1 million up to 7 million records, keeping the initial values for the other parameters (Figures 4(g) and 4(i) use a logarithmic scale for readability). BFTL2 scales better than PBF in terms of R and even outperforms PBF for N greater than 2.5 million records (though R performance of PBF remains acceptable). Unfortunately, BFTL2 seems not the ideal alternative for high N because it scales very badly in terms of W. BFTL1 scales much better in terms of W but exhibits unacceptable performance for R and RC. Let us come back to PBF. PBF scales also badly in terms of W. The reason is that the cost of repartitioning becomes dominant for large N and repartitioning occurs at every Flash buffer overflow. A solution for large files is then to increase the size of the Flash buffer hosting the L1 partitions under construction. The comparison between PBF1 and PBF2 on Figure4(h) shows the benefit of increasing the Flash buffer from 16 pages for PBF1 (that is 4 L1 partitions of 4 pages each) to 64 pages for PBF2 (16 L1 partitions of 4 pages each). Such increase does not impact metric R since the number of reads in L1 partitions does not depend on the number of partitions but of their size (which we keep constant). The impact on metric RC is negligible, especially in environments dealing with very large files (12 more buffers for SKA which could be only 3 pages when organizing the buffer by sectors). This optimization seems very effective for the scalability on W. The scalability on R requires a further optimization. Actually, the bad R performance of PBF is due to the increase of the number of pages in each final partition and of the average accesses to KA which is f*|KA|/2. The growth of the size of each final partition can be compensated by a reduction of k while obtaining a smaller f by increasing d to trade-off with the growth of |KA|. For instance, the values d=24 and k=4 produce even better lookup performance for N=5 million records than the one obtained with d=16 and k=7 for N=1 million records (9 vs. 10). Anyway, future work is required to optimize PBF further for very large files.

Figure 4 (

 4 Figure 4(j) shows the influence of d on R with the other parameters set to the previous values: N=1million, Sk=12, B=7, k=7. As expected, the bigger d, the smaller the false positive rate and then the better R. At the same time, larger Bloom filters increase the frequency of repartitioning and then increase W and FE in the proportion shown in Figure4(k). As expected, the impact on FO is negligible. Figure4(l) shows the influence of k on R with d=16. The bigger k, the better R, up to a given threshold. This threshold is explained by the Bloom filter principle itself (see formula in Section 4.1 showing that there is an optimal value for k beyond which the false positive rate increases again) and by the fact that a bigger k means scanning more partitions in SKA, a benefit which must be compensated by lower accesses in KA.As a conclusion, d introduces a very precise trade-off between R and W, FO, FE, allowing adapting the balance between these metrics to the targeted application/platform tandem. The choice of k under a given d should minimize i*k+f*|KA|/2, where i is the number of pages in each final partition.

Figure 4 .

 4 Figure 4. Evaluation results

Table 1 . Perf. and energy consumption of Flash devices

 1

	Device	R(µJ)	W(µJ)	R(µs)	W(µs)
	Compact Flash 512M	2970	6220	18000	29000
	Mini SD 512M	109	22292	1100	193000
	Samsung 128MB (raw)	0.74	9.9	15	200

Table 2 . False positive rate under various m/n and k

 2

	m/n	k=3	k=4	k=5	k=6	k=7	k=8
	8	.0306	.024	.0217	.0216	.0229
	12	.0108	.0065	.0046	.0037	.0033	.0031
	16	.005	.0024	.0014	.0009	.0007	.0006

5 Performance evaluation 5.1 Performance Analytical Model 5.1.1 Indexing methods under test

  This section compares quantitatively the Bloom filter instantiation of PBFilter, denoted by PBF hereafter, with representative related works: (1) regular B+Tree running on top of FTL, denoted by BTree; (2) BFTL with no compaction of the node translation table, denoted by BFTL1 and

Table 3 . Parameters for the analytical model

 3

	Parameters	Signification
	N	Total number of inserted records
	Sk	Size of the primary key (in bytes)
	B	Number of buffer pages in RAM
	C	Maximum size of a node translation table list in BFTL2
	d	Value of m/n in Bloom filter (see Table 2 for examples)
	k	Number of hash functions used by Bloom filter

Table 4 . Constants for the analytical model Constants Signification

 4

	Sr=4 (bytes)	Size of a physical pointer
	fb=0.69

Table 5 . Basic formulas of the analytical model

 5

	Vars	Annotations	Expressions
	Common formulas
	M	Number of index units (IUs) in each page [Note1]	⎣ Sp/(Sk + ⎣ Sp/(Sk +	⎦ for others Sr) for BFTL1&2 ⎦ Sr) * 5
	Formulas

specific to Tree-based methods (Btree, BFTL1, BFTL2)

	Formulas specific to PBF
	N KA	Total number of pages in KA	⎡	N /		M			⎤
	Sb	Size of a bloom filter (bits)	⎡ log 2 2	(	M	* d	)	⎤
	Mb	Number of bloom filters in a page	⎣ Sp / 8 *	Sb	⎦
	M1	Number of <key, pinter> pairs contained by one bloom filter	⎣ Sb /	d	⎦
	Nr	Total number of partition reorganizations [Note4]	⎣ ⎣	N KA		/		Mb	⎦		/(	1 L	*	s	)	⎦
	Pf	Number of last final partitions	1 L	*	s		*	2	⎡ log 2	(	Nr	%(	Sb	/	1 L	/	s	)	⎤	, if Nr>0, else Pf =0
	N FB	Number of pages occupied by the final valid blooms	⎣	N			/(	Sp		*	8	*		M	) 1	⎦	*	Sb	+	Pf	+	⎣ (	⎣	N	KA	/	Mb	⎦	mod(	L 1	*	s	))	/	s	⎦ s *
	N E	Total number of pages which can be erased
	ht	Height of B+Tree	⎡ log	fb	*	M	+	1	N	⎤
	Nn	Total number of B+Tree nodes after N inser-tions	∑ = ht i 1	⎡ ⎢ ⎢		(		fb	*	M	)(	N fb	*	M	+	) 1	i	-⎥ ⎥ ⎤ 1
	Ns	Number of splits after N insertions	Nn-ht
	L	Average number of buffer chunks that the IUs from the same B+Tree node are distrib-uted to [Note2]	Yao(N, N/(fb*M*B), fb*M) for BTree, Yao(N, β*N/(M*B), fb*M) for BFTL1&2,
	α	Number of index units of a logical node stored in a same physical page [Note3]	fb*M/L
	Nc	Number of compactions for each node in BFTL2	⎢ ⎢ ⎡	C L	--	1 1	⎥ ⎥ ⎤
																																	INRIA

RR n° 6548

This table is taken from[START_REF] Nath | Dynamic Self-tuning Database for NAND Flash[END_REF]. The numbers of the last row are close to the Samsung NAND Flash module K9F1G08X0A we used for our own experiments.

Like all state of the art methods mentioned in Section 2, we concentrate the study on primary keys. The management of secondary keys is briefly addressed in Section

Several FTL provide different API levels (e.g., FTL, VFL, FIL levels in Samsung S-SIM FTL) allowing bypassing some functionalities (e.g., bad block management, ECC management, address translation, etc).

We could have drawn the same conclusion if we had measured the behavior of traditional hashing in Flash. Indeed, either the number of buckets is very small so that a RAM buffer can be allocated to each and R is very bad (because of the bucket size) or the number of buckets is very high and RC is very high too.

For the sake of simplicity, the formulas of the cost model consider 4 buffers for SKA.

Acknowledgments

The authors wish to thank Luc Bouganim and Dennis Shasha for fruitful discussions and valuable comments on this paper. A special thank is also due to Jean-Jacques Vandewalle from Gemalto for his technical support.

[Note1] For BTree, the read cost of a node integrates two additional I/Os to go through the FTL indirection table. For BFTL1&2, loading a node requires traversing, in the node translation table, the whole list of IUs belonging to this node and accessing each in Flash. In PBF, the read cost comprises: the lookup in the final and initial partitions and the cost to access (KA), including the overhead caused by false positives.

[Note2] For BTree, the write cost integrates the copy of the whole page for every key insertion (and 2 times more for splits). BFTL methods also need data copy when doing splits and the write cost of BFTL2 integrates the cost of periodic reorganizations. The write cost for PBF is self-explanatory.

[Note3] For Tree-based methods, the IR cost integrates the cost to traverse the tree up to the target leaf and the cost to read the nodes to be split. For PBF, it integrates the cost to read the partitions to be merged at each iteration.

[Note4] RC comprises the size of the data structures maintained in RAM plus the size of the buffers required to read/write the data in Flash.

[Note5] FO+FE is the total number of pages occupied by both valid and stale index units. In BFTL1&2, FE=0 simply because stale data are mixed with valid data. By contrast, stale data remain grouped in BTree and PBF. In BTree, this good property comes at a high cost in terms of FE.


Pierre Bérard
email: bernard.helffer@univ-nantes.fr

AN EULER-TYPE FORMULA FOR PARTITIONS OF THE MÖBIUS STRIP

Keywords: Mathematics Subject Classification. 58C40, 49Q10 Spectral theory, Möbius strip, Laplacian, Partitions

Introduction

In [2], in collaboration with R. Kiwan, we investigated the Courant-sharp property for the eigenvalues of the Dirichlet Laplacian on the square Möbius strip, equipped with the flat metric. We pointed out that the orientability of the nodal domains (more precisely the fact that they are all orientable or not) can be detected by an Euler-type formula. The purpose of the present note is to establish this formula in the framework of partitions.

In Section 2, we fix the notation and recall (or modify) some of the definitions for partitions given in [START_REF] Bérard | Remarks on the boundary set of spectral equipartitions[END_REF], and we state the Euler-type formula we are interested in, see Theorem 2.10. The proof of the theorem is given in Section 3.

Partitions

2.1. Definitions and notation. Let Σ denote a compact Riemannian surface with or without boundary. We consider Euler-type formulas in the general framework of partitions. We first recall (or modify) some of the definitions given in [START_REF] Bérard | Remarks on the boundary set of spectral equipartitions[END_REF].

A k-partition of Σ is a collection, D = {D j } k j=1 , of k pairwise disjoint, connected, open subsets of Σ. We furthermore assume that the D j 's are piecewise C 1 , and that (2. [START_REF] Bérard | Remarks on the boundary set of spectral equipartitions[END_REF] Int(∪ j D j ) = Σ .

The boundary set ∂D of a partition D = {D j } k j=1 ∈ D k (Σ) is the closed set, (2.2) ∂D = ∪ j (∂D j ∩ Σ) .

Definition 2.1. A partition D = {D j } k j=1 is called essential if, for all j, 1 ≤ j ≤ k, (2. 3) Int(D j ) = D j .

Definition 2.2. A regular k-partition is a k-partition whose boundary set ∂D satisfies the following properties:

(i) The boundary set ∂D is locally a piecewise C 1 immersed curve in Σ, except possibly at finitely many points {y i ∈ ∂D ∩ Σ} in a neighborhood of which ∂D is the union of ν(y i ) C 1 semi-arcs meeting at y i , ν(y i ) ≥ 3. (ii) The set ∂D ∩ ∂Σ consists of finitely many points {z j }. Near the point z j , the set ∂D is the union of ρ(z j ) ≥ 1 C 1 semi-arcs hitting ∂Σ at z j . (iii) The boundary set ∂D has the following transversality property: at any interior singular point y i , the semi-arcs meet transversally; at any boundary singular point z j , the semi-arcs meet transversally, and they meet the boundary ∂Σ transversally.

The subset of regular k-partitions is denoted by

R k (Σ) ⊂ D k (Σ).
When D is a regular partition, we denote by S(D) the set of singular points of ∂D.

Definition 2.3. A regular k-partition D = {D j } k j=1 is called normal, if it satisfies the additional condition, for all j, 1 ≤ j ≤ k, (2.4) ∀x ∈ ∂D j , ∃r > 0 s. t. B(x, r) ∩ D j is connected.
Remark 2.4. The definition of a normal partition implies that each domain in the partition is a topological manifold with boundary (actually a piecewise C 1 surface with boundary, possibly with corners). A normal partition is essential.

Example 2.5. The partition of a compact surface Σ (with or without boundary) associated with an eigenfunction is called a nodal partition. The domains of the partition are the nodal domains of Φ, the boundary set ∂D is the nodal set Z(Φ), the singular set S(D) is the set of critical zeros of Φ. This is an example of an essential, regular partition. Nodal partitions are not necessarily normal due to the singular set, see Figure 3.1 (middle) and Figure 3.3 (A).

For a partition D ∈ D(Σ), we introduce the following numbers. Obviously, ω(D, Σ) = 0 whenever the surface Σ is orientable.

Remarks 2.6.

(i) We use the definition of orientability given in [3,Chap. 5.3] (via differential forms of degree 2), or the similar form given in [START_REF] Jean | A guide to the classification theorem for compact surfaces, collection[END_REF]Chap. 4.5] in the setting of topological manifolds (via the degree). A topological surface is orientable if one can choose an atlas whose changes of chart are homeomorphisms with degree 1.

(ii) A compact surface (with boundary) is non-orientable if and only if it contains the homeomorphic image of a Möbius strip. One direction is clear since the Möbius strip is not orientable. For the other direction, one can use the classification of compact surfaces (with boundary).

For a regular partition D, we define the index of a point x ∈ S(D) to be,

(2.5) ι(x) = ν(x) -2 , if x is an interior singular point, ρ(x) , if x is a boundary singular point.
For a regular partition, define the number σ(D, Σ) to be,

(2.6) σ(D, Σ) = 1 2 x∈S(D) ι(x) .
Finally, we introduce the number A similar procedure is applied at a boundary singular point. By recursion, we can in this way eliminate all the singular points at which condition (2.4) is not satisfied. Choosing ε small enough, this procedure does not change the orientability of the modified domains, while the added disks are orientable.

(2.7) δ(D, Σ) = ω(D, Σ) + β(D, Σ) + σ(D, Σ) -κ(D, Σ) .
Remark 2.8. By the same process, one could also remove all singular points with index ι > 1. We do not need to do that for our purposes.

Partitions and Euler-type formulas.

In the case of partitions of the sphere S 2 , or of a planar domain Ω, we have the following Euler-type formula, which appears in [9, 10] (sphere) or [START_REF] Hoffmann-Ostenhof | Bounds on the multiplicity of eigenvalues for fixed membranes[END_REF] (planar domain).

Proposition 2.9. Let Σ be S 2 , or a bounded open set Ω in R 2 , with piecewise C 1 boundary, and let D be a regular partition with ∂D the boundary set. Then,

(2.8) κ(D, Σ) = 1 + β(D, Σ) + σ(D, Σ) .
Theorem 2.10. Let D be an essential, regular partition of the Möbius strip M 1 .

With the previous notation, we have,

(2.9) κ(D, M 1 ) = ω(D, M 1 ) + β(D, M 1 ) + σ(D, M 1 ) .

Proof of Theorem 2.10

The idea to prove Theorem 2.10 is to examine how δ(D, Σ) changes when the partition D and the surface Σ are modified, starting out from a partition D of the Möbius strip, and arriving at a partition D of a domain Ω in R 2 , on which we can apply (2.8).

Lemma 3.1. Let D be a regular partition of M 1 . Assume that there exists a simple piecewise

C 1 curve : [0, 1] → M 1 , such that ⊂ ∂D, (0), (1) ∈ ∂M 1 , and transversal to ∂M 1 . If Ω := M 1 \ is simply-connected 1 , then δ(D, M 1 ) = 0.
Proof. Observing that D can also be viewed as a partition of Ω, it is enough to prove that δ(D, Ω) = δ(D, M 1 ) . For this, we make the following observations.

• Since 1 = b 0 (∂D ∪ ∂Ω) = b 0 (∂D ∪ ∂M 1 ) and b 0 (∂Ω) = b 0 (∂M 1 ), we have

β(D, Ω) = β(D, M 1 ) . • ω(D, M 1 ) = ω(D, Ω) = 0. Indeed, each domain in D is orientable because Ω is simply-connected. • κ(D, M 1 ) = κ(D, Ω).
• Let x be a singular point of D in M 1 belonging to , with index ν(x). After scissoring, we obtain two boundary points x + ∈ + and x -∈ -, with indices ρ + and ρ -such that ρ + + ρ -= ν(x) -2 . • After scissoring, the boundary singular point (0) of yields two boundary singular points y 0,+ and y 0,-such that ρ 0,+ +ρ 0,-= ρ( (0))-1, with a similar property for (1). • As a consequence of the two previous items, we have

σ(D, M 1 ) = σ(D, Ω) + 1 .
Since Ω is homeomorphic to a simply-connected domain in R 2 , we have κ(D, Ω) = 1 + β(D, Ω) + σ(D, Ω). Taking into account the preceding identities, it follows that δ(D, Ω) = 0. Lemma 3.2. Let D be a regular partition of M 1 . Then, there exists a simple piecewise C 1 path : [0, 1] → M such that:

• M 1 \ is simply connected;

• crosses ∂D and hits ∂M 1 transversally;

• S(D) ∩ = ∅.

Proof. Starting from any line 0 such that M 1 \ 0 is simply connected, it is easy to deform 0 in order to get the two other properties. 1 More precisely, after scissoring M 1 along , and unfolding, one can view Ω as a subset Ω of R 2 .

The former is now split into two lines + and -in the boundary of Ω. For simplicity, we denote by , both the curve, and the image ([0, 1]).

Proof. Denote by y i , x 1 , . . . , x N , y f the points of ∩ ∂D, where y i and y f belong to ∂M 1 ; each open interval J on the path , delimited by two consecutive points in the sequence, is contained in some element D J of the partition, and the end points of J belong to ∂D J . Using the assumption that the elements of D are simply-connected, and comparing D with D, we observe that: Since S is connected, there exists a path : [0, 1] → S, with (0) = x 0 and (1) = x 1 . If x 0 and x 1 both belong to D, the claim is clear. Without loss of generality, we may now assume that x 0 ∈ D.

Define the set J := {t ∈ [0, 1] | (t) ∈ K}. Since x 0 ∈ K, the set J in not empty, and we define t 0 := inf J. Clearly, (t 0 ) ∈ K, and since K ⊂ D, (t 0 ) ∈ D. Since D is open, there exists some ε > 0 such that ([t 0 -ε, t 0 + ε]) ⊂ D, and hence x ε = (t 0 -ε) ∈ D. If x 1 ∈ D, then there exists a path γ ε from x ε to x 1 , contained in D\K. The path γ ε • | [0,t 0 -ε] is contained in S \K and links x 0 and x 1 .

If x 1 ∈ D, we can consider the path -1 and apply the preceding argument. Define t 1 = sup J. Then t 1 exists and (t 1 ) ∈ K, and there exists δ > 0 such that x δ = (t 1 + δ) ∈ D. There exists a path γ ε,δ linking x ε and x δ in D \K. The path

| [t1+δ,1] • γ ε,δ • | [0,t 0 -ε]
is contained in S \K and links x 0 and x 1 .

Lemma 3.5. Let D be a normal partition of M 1 , and let D be an element of D. Assume that D is orientable. Then, D is homeomorphic to a sphere with q discs removed, and one can find q piecewise C 1 cuts j (i.e. disjoint simple curves joining two points of ∂D and hitting the boundary transversally) such that D \ ∪ j is simply connected.

Proof. Since D is normal, the domain D is an orientable surface with boundary.

According to the classification theorem [START_REF] Jean | A guide to the classification theorem for compact surfaces, collection[END_REF]Chap. 6], D is homeomorphic to some Σ 0,g,q , a sphere with g handles attached, and q disks removed. We claim that g = 0. Indeed, if g = 0, there exists g disjoint simple closed curves whose union does not disconnect D and hence, by Lemma 3.4 does not disconnect M 1 . Since M 1 has genus 1, we must have g ≤ 1. If g = 1, we have a simple closed curve γ which disconnects D, and preserves orientation since D is orientable. A simple closed curve which disconnects M 1 reverses orientation, a contradiction, see [8]. One can draw cuts on the model surface Σ 0,0,q and pull them back to D.

Claim 3.6. One can find piecewise C 1 cuts Indeed, we can start from a continuous cut γ : [0, 1] → M 1 , with γ(0, 1) ⊂ D, joining two points γ(0) ∈ Γ 0 and γ(1) ∈ Γ 1 , two components of ∂D. In order to finish the proof, we need to approximate γ by a piecewise C 1 path γ 1 which is transversal to ∂D at γ(0) and γ [START_REF] Bérard | Remarks on the boundary set of spectral equipartitions[END_REF]. For this purpose, we choose B(γ(0), 2r 0 ) ∩ D, B(γ(1), 2r 1 ) ∩ D, with r 0 , r 1 small enough so that these sets do not intersect ∂D\Γ i . We choose t 0 , t 1 ∈ (0, 1) such that t 0 ∈ B(γ(0), r 0 ), γ(t 1 ) ∈ B(γ(1), r 1 ). We cover γ([t 0 , t 1 ]) with small disks B(γ(t), r) ⊂ D, with r small enough so that the disks B(γ(t), r) do not meet ∂D. By compactness, we can extract a finite covering of γ([t 0 , t 1 ]). We can now easily construct the desired path γ 1 , close to γ by using geodesics segments contained in the disks.

Lemma 3.7. Let D be a normal partition of M 1 such that all the domains D i ∈ D are orientable. Then, there exists a new partition D of M 1 all of whose domains are simply-connected, and such that δ(D, M 1 ) = δ( D, M 1 ).

In particular, δ(D, M 1 ) = 0 .

Proof. This is essentially an application of Lemma 3.5, with Lemma 2.7 in mind. Each time, we apply one step in the proof of Lemma 3.5 to one of the domains D i ∈ D, β decreases by 1, and we create two critical points x 1 and x 2 with ι(x 1 ) = ι(x 2 ) = 1.

Lemma 3.8. Let D be a normal partition of M 1 . Assume that some domain D ∈ D is non-orientable. Then, there exists a connected component Γ of ∂D, and a piecewise C 1 path : [0, 1] → M 1 , such that (0), (1) ∈ Γ, with transversal to Γ at its end points, ((0, 1)) ⊂ D, and D \ is connected and orientable.

Proof. The partition D being normal, the domain D is a non-orientable surface with boundary and hence, there exists a homeomorphism f : D → Σ 1,c,q , one of the standard non-orientable surfaces, a sphere with c ≥ 1 cross-caps attached, and q discs removed (c is the genus2 of Σ 1,c , and q is the number of boundary components of D). The surface Σ 1,c,q contains c pairwise disjoint simple closed curves whose union does not disconnect the surface, each cross-cap contributes for one such curve. Since the genus of M 1 is 1 (M 1 is a sphere with one cross-cap attached, and one disk removed), Lemma 3.4 implies that c = 1. It follows that f : D → Σ 1,1,q , a Möbius strip Σ 1,1 with q disks removed. Denote by Γ = f -1 (∂Σ 1,1 ), the inverse image of the boundary of the Möbius strip. It is easy to cut Σ 1,1,q by some path 0 , with end points on ∂Σ 1,1 , in such a way that Σ 1,1,q \ 0 is simply-connected. The path 1 is given by 1 = f -1 ( 0 ). In order to finish the proof, it suffices to approximate 1 by a piecewise C 1 path transversal to ∂D. For this purpose, we can use the same arguments as in the proof of Claim 3.6.

Proof of Theorem 2.10

Let D be a regular partition of the Möbius strip. Let δ(D, M 1 ) be defined in (2.7). By Lemma 2.7, we may assume that D is a normal partition, without changing the value of δ(D, M 1 ). Assume that all the domains in D are orientable. Applying Lemma 3.7, we conclude that δ(D, M 1 ) = 0, and the theorem is proved in this case.

Assume that (at least) one of the domains in D, call it D 1 is non-orientable. We claim that D 1 is actually the only non-orientable domain in D. Indeed, assume that there is another non-orientable domain D 2 . By Lemma 2.7, both domains are surfaces with boundary, with genus 1. Each D i , i = 1, 2, contains a simple closed curve γ i which does not disconnect D i . Since D 1 ∩ D 2 = ∅, we would have two disjoint simple closed curves γ 1 , γ 2 . Applying Lemma 3.4 twice, we obtain that γ 1 ∪ γ 2 does not disconnect M 1 . This is a contradiction since M 1 has genus 1. Apply Lemma 3.8: D 1 is homeomorphic to a Möbius trip with q disks removed, there is a path which does not disconnect D 1 , and such that D 1 \ is orientable. In doing so, using the fact that is piecewise when β ∈ (0, π 3 ) is fixed and θ ∈ (0, π 2 ). As explained in [2, Section 5.4], there is a dramatic change in the nodal pattern when θ passes some value θ(β) (this value is precisely defined in [2, Eq. (5.26)]). For 0 < θ ≤ θ(β) the nodal domains are all orientable; for θ(β) < θ < π 2 , there is one non-orientable nodal domain, homeomorphic to a Möbius strip (the domain in green). When θ = θ(β), the nodal domain in green is not a surface with boundary due to the singular point at the boundary.

  (a) κ(D, Σ) denotes the number of domains of the partition; (b) β(D, Σ) is defined as b 0 (∂D ∪ ∂Σ) -b 0 (∂Σ), the difference between the number of connected components of ∂D ∪ ∂Σ, and the number of connected components of ∂Σ; (c) ω(D, Σ) is the orientability character of the partition, ω(D, Σ) = 0, if all the domains of the partition are orientable; ω(D, Σ) = 1, if at least one domain of the partition is non-orientable.

Lemma 2. 7 (

 7 Normalization). Let D be an essential, regular partition of Σ. Then, one can construct a normal partition D of Σ such that δ( D, Σ) = δ(D, Σ), and ω( D, Σ) = ω(D, Σ).Proof. Using condition (2.3), we see that an essential, regular partition D = {D j } k j=1 is normal except possibly at points in S(D), with index ι > 1, and for which there exists some domain D j such that B(x, ε)∩D j has at least two connected components. Here, B(x, ε) denotes the disk with center x and radius ε in Σ. Let x be such a point. For ε small enough, introduce the partition D x whose elements are the D j \B(x, ), and the extra domain B(x, ε) ∩ Σ. In this procedure, we have κ(D x ) = κ(D) + 1; an interior singular point x, with ν(x) ≥ 4 is replaced by ν(x) singular points of index 3 for which condition (2.4) is satisfied. Hence, σ(D x ) = σ(D) + 1 and δ(D x ) = δ(D).

Lemma 3 . 3 .

 33 Let D be a regular partition of M 1 whose elements D i are all simplyconnected. Let : [0, 1] → M 1 be a path as given by Lemma 3.2. Let D be the partition of M 1 whole elements are the connected components of the D i \ . Then, ∂ D = ∂D ∪ , and δ(D, M 1 ) = δ( D, M 1 ). In particular D satisfies the assumptions of Lemma 3.1, and δ(D, M 1 ) = 0 .

  κ( D) = κ(D) + N + 1; the partition D has two extra simple singular boundary points, and N interior singular points with index ι = 4, so that σ( D) = σ(D) + N + 1 ; β( D) = β(D) and ω( D) = ω(D) = 0. The lemma follows. Lemma 3.4. Let S be (the interior of) a surface with or without boundary. Let D be an open subset of S, and K ⊂ D a compact subset. Assume that D \ K is connected. Then, S \K is connected. Proof. It suffices to prove the following claim. Claim. Given any x 0 , x 1 ∈ S \K, there exists a path γ : [0, 1] → S \K such that γ(0) = x 0 and γ(1) = x 1 .

  C 1 and transversal to Γ, we obtain a regular partition D = D 1 \ , D 2 , ..., D κ(D) of M 1 . Since all the domains of D are orientable, by the preceding argument, we have δ(D , M 1 ) = 0. On the other-hand, we have ω(D , M 1 ) = 0, β(D , M 1 ) = β(D, M 1 ), κ(D , M 1 ) = κ(D, M 1 ), and since we have the extra arc in ∂D , whose end points are singular points of index ι = 1, we have σ(D , M 1 ) = σ(D, M 1 ) + 1. It follows that, 0 = β(D , M 1 ) + σ(D , M 1 ) -κ(D , M 1 ) = β(D, M 1 ) + σ(D, M 1 ) + 1 -κ(D, M 1 ) , and hence δ(D, M 1 ) = 0. The proof of Theorem 2.10 is now complete.

Figure 3 .

 3 Figure 3.1 displays the typical nodal patterns of the Dirichlet eigenfunction (3.1) Φ β,θ (x, y) = cos θ sin(2x) sin(3y) + sin θ sin(3x) sin(2y + β) ,

Figure 3 . 1 .

 31 Figure 3.1. Example 1

Figure 3 .

 3 Figure 3.2 displays the nodal patterns of the eigenfunctions sin(3x) (left) and sin(5x) (right), on a 3D representation 3 of the Möbius strip. The nodal domains are colored according to sign. In both cases, there is one nodal domain which is homeomorphic to a Möbius strip. The other nodal domains are cylinders, and hence orientable though not simply-connected.

Figure 3 .Figure 3

 33 Figure 3.2. Example 2

Figure 3 .

 3 3 (B) displays the nodal pattern of the function cos θ sin(x) cos(6y) + sin θ sin(6x) cos(y), with θ = 0.4 π. There is one non-orientable domain (colored in pink), homeomorphic to a Möbius strip with two holes (nodal domains colored in blue or in green). There is another disk-like nodal domain (colored in yellow).

Figure 3 . 3 .

 33 Figure 3.3. Example 3

For an orientable surface without boundary, the genus is defined as the number of handles attached to the sphere. For a non-orientable surface without boundary, the genus is defined as the number of cross-caps attached to the sphere.

We work with the flat metric on the Möbius strip, and use an embedding into R 3 which is not isometric.