WIXLIB

300200150Due to the high performance gain from channel-level parallelismon a single flashSSD, we need to treat I/O parallelism as a toppriority for optimizing I/O performance even in commoditysystems, as is stated in [3]. In order to achieve it, more lightweight method is needed since parallel processing (or mutlithreading) cannot be applied in every application programsinvolving I/Os. In order to best utilize channel-level parallelism,it is also required to deliver the outstanding I/Os to the flashSSDs,minimizing the interval of consecutive I/O requests since insideflashSSDs they can batch-process only the I/O requests gatheredin its own request queue (a part of NCQ technology) within a verynarrow time span. Therefore, we suggest a new I/O requestmethod, psync I/O that creates outstanding I/Os and minimize theinterval between consecutive I/O requests within a single process.2000KF120 psyncP300 psyncIodrive psyncF120 threadP300 threadIodrive thread250Bandwidth (MB/s)200Bandwidth (MB/s)300F120 psyncP300 psyncIodrive psyncF120 threadP300 threadIodrive thread2501501001005005048163264128 256Outstanding I/O levelParallel Psync I/O1800KNumber of context switchesdistribute them into multiple CPUs. Since I/Os of each processcan be independently requested to OS at the same time,outstanding I/Os (multiple parallel I/Os) can be delivered to aflashSSD at the same moment.248163264 128 256Outstanding I/O level124816Outstanding I/O level32(a) In a shared file (b) In separate files (c) Context switchesFigure 4. Psync I/O and Parallel processing comparisonWe compared the result with the bandwidth of parallel processingwhere each of multi-threads requested a sync I/O and the numberof multi-threads was fixed at the OutStd level with a random I/Opattern in a 4GB file. In the second benchmark, we measured theperformance with the same settings as the first benchmark exceptusing multiple files (A different file for each thread). Lastly, wemeasured context switching cost of parallel processing and psyncI/O as increasing the OutStd level in Linux. As shown in Figure 4(a), in a shared file, parallel processing performance showednearly saturated performance at the bandwidth of OutStd level 2.Consequently, psync I/O outperformed parallel processing in ashared file. On the contrary, in Figure 4 (b) with separate files,parallel processing showed similar performance to the psync I/Operformance. The performance degradation in a shared file isbecause write operations requested in sync I/O coupled with directI/O cannot be overlapped in a shared file in Linux EXT2 filesystem. POSIX requires write-ordering for synchronous I/Os,which indicates that writes must be committed to a file in theorder in which they are written and that reads must be consistentwith the data within the order of any writes. Most POSIXcompliant file systems simply implement a per-file reader-writerlock to satisfy the write-ordering requirement. Therefore, parallelprocessing cannot utilize the internal parallelism when I/Os arerequested into the same file in the file systems. Figure 4 (c) showsthe numbers of context switches of each method when 1 million4KB read requests were given. The context switch count ofparallel processing was an order of magnitude greater than psyncI/O at OutStd level 32. The direct cost and indirect cost of contextswitching can be much worse in parallel processing than psyncI/O. For example, a previous study [7] revealed that the time costcaused by context switching is a nontrivial part (nearly 10%) oftotal cost of DBMS operations. We obtained almost identicalresults for the three benchmarks by using multi-processes.2.3 Psync I/O: Parallel Synchronous I/OTwo different types of I/O request methods exist in currentoperating systems. One is synchronous I/O (sync I/O), whichwaits until the I/O request is completely processed. The other isasynchronous I/O (async I/O), which immediately returns even ifthe I/O processing is still in progress, thus making it possible forthe process to execute next command, but async I/O requires aspecial routine for handling later notification of I/O completion.We hope that future OS kernel versions will include system callsfor the still conceptual psync I/O. Psync I/O synchronouslyoperates in the same way as traditional sync I/O except that theunit of operation is an array of I/O requests. We define the threerequirements of psync I/O as follows. 1) It delivers the set of I/Osto the flashSSDs and retrieves request results at once. Another setof I/O requests can be submitted in sequence only after the resultsof the previous set are retrieved. 2) The I/Os are requested as agroup in the OS user space and the group needs to be sustaineduntil they are delivered to I/O schedulers in the OS kernel space,thereby minimizing the request interval between consecutive I/Osupon I/O schedulers 3) No special routine is required to handleI/O completion events since the process is blocked until the set ofI/Os are completely handled.Since no I/O requesting method that satisfies the psync I/Orequirements exists in current OSs, we designed a wrapperfunction that emulates psync I/O by using Linux-nativeasynchronous I/O API. The wrapper function delivers a group ofI/O requests to the ‘io submit()’ system call by containing them inLinux async I/O data structures (struct iocb), and it waits until allthe results are returned, executing ‘io getevents()’ system call inLinux. Even though this implementation cannot fully satisfy therequirement 2), this is the best alternative that we found. Likewise,in other operating systems, this alternative method can be alsoimplemented by using their KAIO (Kernelized Asynchronous I/O)APIs.We suggest algorithm design principles in order for DBMSs tobest benefit from the internal parallelism of flashSSDs based onprinciples suggested by previous studies [3, 10] and our ownfindings.1. Large granularity of I/Os: Request I/Os with largegranularity in order to utilize package-level parallelism.2. High outstanding I/O level: Create outstanding I/Os in orderto utilize the channel-level parallelism. Consider usingpsync I/O first in order to request multiple I/Os in a singleprocess and save parallel processing for later use in moresuitable applications (i.e. applications that require bothheavy computation and intensive I/Os).We compared the performance of the implemented psync I/O withthe performance of parallel processing by conducting benchmarksin direct I/O mode. In the first benchmark, we measured thebandwidth of each method in a shared file with a mixed read/writesetting on the Linux EXT2 file system. Psync I/O was configuredto request a group of I/Os as many as the OutStd level at a time.3. No mingled read/writes: Avoid creating I/Os in a mingledread/write pattern.288

′ P1 K1 P2 K2 P3 PF-1 KF-1 PF for each internal nodeThird, all the child nodes designated by the pointers in the pointersets of ′ are read at once through psync I/O. The entries of theread internal nodes are examined for every node, and for eachnode the pointer set to the next-level nodes is extracted, creatingan array of the pointer sets ′, again. This process is repeated,until it reaches leaf nodes and retrieves all the leaf nodescorresponding to the search requests S.Figure 5. Internal node structure3. B -TREE INDEX OPTIMIZATION3.1 Optimized Algorithms for flashSSDsIn this section, we optimize B -tree algorithms to utilize channellevel parallelism of flashSSDs, according to Principle 2 and 3.Figure 6 presents an example of MPSearch when the number ofsearch requests is 5. With 2 psync I/O calls, the leaf nodes havingthe search keys are retrieved by MPSearch.3.1.1 Multi Path Search AlgorithmSearches to next-level nodes cannot be performed withoutobtaining the search results of current-level nodes since indexrecords of the current-level nodes contain the locations of nextlevel nodes.During this procedure, psync I/O is executed (treeHeight-1) times,at maximum processing S read requests for each time, sincepsync I/O is executed once for every level except the root level.The only way to achieve Principle 2 is to search multiple nodes atthe same level. However, this is possible only if a set of searchrequests are provided at once.This indicates that MPSearch can achieve S OutStd level atmaximum. It also implies that S in-memory buffer pages arerequired for every psync I/O call since one buffer-page is neededfor every node to be loaded into main memory. This mightconsume a significant amount of main memory space if S isconsiderably large.Under the assumption that the set of search requests is given, wedesign a Multi Path Search (MPSearch) algorithm, whichprocesses a set of requests at once while searching multiple nodeslevel by level. The method to acquire the set of requests isexplained later with the detailed algorithm of each index operation.We represent an internal node of a B -tree index as a set of keyvalues (Ki) and pointer values (Pi) each pointing to the location ofa child node as depicted in Figure 5, where F represents the fanout(the maximum number of pointers).Therefore, we adopt a parameter called PioMax that indicates themaximum number of I/Os submitted to a psync I/O call. By doingso, the maximum main memory space is limited to (ℎ 1) pages. As demonstrated in the results of Figure3, PioMax is not necessary to be considerably large. A moderatevalue (around 32) can increase the bandwidth enough.Let S denotes the set of search requests.MPSearch process needs to be adjusted reflecting this change. s s is the key value for each search requestAlgorithm 1: Multi Path SearchProcedure MPSearch(S[], P[], PioMax, PioCnt, level, b[][])Input: S[] (search keys), P[] (pointers to target nodes), PioMax(max number of I/Os at a time), PioCnt (number of I/Orequests to psync I/O), tree level, b[][] (2nd dim array of bufferpages, b [i][j]: jth buffer page on ith level), F (node fanout).Output: leafNode[] (leaf nodes corresponding to S[])1: cnt 02: if (level (treeHeight-1)) then //leaf nodesb[level][] psync read(P[])3:leafNode[] b[level][] //convert buffers to leaf nodes4:return leafNode[]5:6: else //non leaf-nodesb[level][] psync read (P[]), isEnd false7:for n 0 to PioCnt-1 step 1 do8:9:node b[level][n] //covert buffer to node structure10:if (n PioCnt-1 and i F) then isEnd true11:for i 1 to F step 1 do12:if (CheckSearchNeeded(i, node.K[], S[])) then13:P[cnt ] node.Pi //Pi is ith pointer of the node14:if ((cnt 0 and (cnt % PioMax) 0) or isEnd) then15:MPSearch(S[], P[], PioMax, cnt, level 1, b[][])16:Reset P[], cnt 0function CheckSearchNeeded(index, K[],S[])17: K[0] , K[F] //K[i] is ith key value (Ki) of a node18: for i 1 to S step 1 do19: if (K[index-1] S[i] K[index]) then20:return true21: return falseS includes all the key values of search requests, and S representsthe number of given search requests.The basic concept of MPSearch is described as follows.First, the root node of the B -tree index is retrieved. The keyvalues of the root node are inspected, and the pointers to the nextlevel nodes designated by any of the search requests are extractedas (1), where P denotes the set of the extracted pointers (refer to‘CheckSearchNeeded’ function of Algorithm 1 for more details). 1 i K s K , s S, K , K (1) i Second, the next-level nodes designated by the pointer set (P) areread at once through psync I/O. The entries of the read internalnodes are examined node by node, and the pointer set for eachnode corresponding to S is extracted by using (1). The extractedpointer sets create an array of the pointer sets ′ as follows.pointer keyS {1, 2, 42, 65, 67}Level 065Level 11242②12571②122391①①9889②42 454750656768Figure 6. MPSearch with two psync I/Os289

Algorithm 1 presents the complete process of MPSearch withPioMax considered. MPSearch begins with reading the root node(line 7). Then the pointers to the child nodes relevant to the set ofsearch keys are extracted, and the relevant pointers create thepointer set (line 12-13, line 17-21). Each pointer set has a size lessthan PioMax, and in turn the pointer set is delivered to MPSearchfor the sub-tree traverse (line 13-15). If the number of relevantpointers is greater than PioMax, then the procedure recursivelycalls the procedure itself only with the first pointer-set havingpointers as many as PioMax, leaving the job to handle the rest ofthe pointers to a later task (line 14-15). After the sub-tree traverseby the recursive call is finished, the remaining pointers areprocessed by later recursive calls. This part is analogous to theDepth First Search (DFS).2 i 5 i 10 i 15 d 21 i 45 i 74 i 86 i 94 i 31 i 25 u 49 d59 isortedOffsetFigure 7. Operation Queue structureare batch processed. Since update operations are not immediatelyreflected to flashSSDs and reside on the in-memory structure for awhile, this method requires additional features to the traditionalDBMS recovery scheme for avoiding data-loss during systemcrashes. We address this issue in Section 3.4.Operation Queue: We first describe OPQ that provides an inmemory space for index records of update operations. The updateoperations reside in OPQ, until they are processed by a batchupdate operation (bupdate). The adoption of OPQ requires searchalgorithms to first scan the entries in OPQ before traversing treesso that the entries of queued update operations can be successfullysearched.In the recursive call from the root node, internal nodes on level 1are read via psync I/O (line 7). The psync I/O call retrieves therequested nodes at once from the locations provided by the givenpointer set P[], and loads them into the given buffers b[level][]. Inthe retrieved node, the procedure extracts the relevant child-nodepointers (line 12, 17-21), and creates a pointer set for everyPioMax pointers (line 8-13). For each pointer set, the procedure isrecursively called (line 15). When this procedure reaches the leaflevel (ℎ 1), the procedure retrieves the leaf nodesdesignated by the given pointer set via psync I/O (line 2-5).OPQ is an array-based structure, including index records of thequeued update operations in its elements called OPQ entries. OPQ Entry (Ent): consists of an index record and anoperation flag that indicates the type of the update operation.- Ent.indexRec: an index record containing the key valueand pointer to the data record page (data page id).3.1.2 Parallel Range SearchIt is straightforward to apply MPSearch into the range search.This is simply achieved by requesting the search request set Sdefined as (2) via MPSearch. s range. start s range. endindex record operation flagOPeration Queue (OPQ)- Ent.op: an operation flag indicating the update operationtype (i: insert, d: delete, u: update)Figure 7 shows an example of OPQ. The array region is dividedinto two parts, one for the sorted array region and the other for therecently appended entries. The two regions are differentiated bysortedOffset. We configured OPQ in this manner to considertrade-offs between the in-OPQ search cost for searching indexrecords within OPQ and the OPQ append cost for inserting anentry to OPQ. For every update operation, OPQ creates an OPQentry and merely appends it into the next slot of the most recentlyappended entry without considering the orders between key values.The OPQ append cost is minimal since only one main memorypage is accessed for an update operation. The sorting occurs onthe basis of a parameter called sort period (speriod). For everysperiod update operations, a sort operation for OPQ entries isexecuted. Since there are already sorted entries in the sortedregion (before sortedOffset), there is no need to sort the entireregion. The recently appended entries in the unsorted region (aftersortedOffset) are first sorted. Next, they are merged into theentries of the sorted region. The merge process is analogous tothat of the merge-sort algorithm. Due to these features, in-OPQsearches can be conducted by using binary search in the sortedregion, leaving the unsorted entries to the linear search.(2)The MPSearch retrieves the leaf nodes including the entries withkey values in the range.The traditional method to conduct a range search is reading theleaf nodes that are linked between each other one by one insequence, after searching the first leaf node containing an entrywith the least key value of the range. The new range search, calledparallel range (prange) search reads relevant internal nodes levelby level via psync I/O until it reaches to the leaf level.Prange search reads more internal nodes than the traditional rangesearch. Nevertheless, prange search outperforms the legacy rangesearch in general since the benefit from leaf-node reads by usingpsync I/O is substantial (up to ten-fold bandwidth increase). Wediscovered that prange search time was always less than or equalto the legacy range search time in any condition on the flashSSDstested in this paper (see the empirical study in Section 4.1.2).3.1.3 Update OperationsIn this section, we optimize update operations such as insert,delete, and update by utilizing the channel-level parallelism offlashSSDs. Hereinafter an update operation indicates an updatetype operation including an index-insert, index-delete, and indexupdate operation unless we further differentiate it as an indexupdate operation.Batch Update: By using OPQ, MPSearch can be applied tobatch-processing of the queued update operations. First the searchrequest set is defined as the following.The index records of update operations are inserted in an inmemory structure (Operation Queue) to accumulate a group ofupdate operations for later MPSearch-like batch-updates. Eachupdate operation is completed immediately after its index-recordis inserted into the Operation Queue (OPQ) as an OPQ entry.OPQ entries are not written to the flashSSDs until the OPQ entriesThe batch-update operation

The performance improvement by the channel-level parallelism is somewhat clearer than that of the package-level parallelism. If the host I/F (host interface) requests I/Os designated to different flash memory packages spanning several channels, the channel-level parallelism is achieved by transferring the associated data through