Abstract:
Aspects of the present invention provide high-performance indexing for data-intensive systems in which “slicing” is used to organize indexing data on an SSD such that related entries are located together. Slicing enables combining multiple reads into a single “slice read” of related items, offering high read performance. Small in-memory indexes, such as hash tables, bloom filters or LSH tables, may be used as buffers for insert operations to resolve slow random writes on the SSD. When full, these buffers are written to the SSD. The internal architecture of the SSD may also be leveraged to achieve higher performance via parallelism. Such parallelism may occur at the channel-level, the package-level, the die-level and/or the plane-level. Consequently, memory and compute resources are freed for use by higher layer applications, and better performance may be achieved.

Description:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0001]    This invention was made with government support under 1050170 awarded by the National Science Foundation. The government has certain rights in the invention. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    The present invention relates to the field of computer systems, and in particular, to high-performance indexing for data-intensive systems. 
         [0003]    Data-intensive systems, that is, computer systems that involve substantial amounts of data storage and recovery, are being employed in a wide variety of applications today. Efficient data storage and access normally uses an index structure, such as a key-value index where the address of storage is determined by applying a key (representative of the stored data) to the index to obtain the storage address. Key-value storage systems are employed in cloud-based applications as diverse as ecommerce and business analytics systems and picture stores. Large object stores having key-value indexes are used in a variety of content-based systems such as network de-duplication engines, storage de-duplication, logging systems and content similarity detection engines. 
         [0004]    An index may be a simple association list linking pairs of keys and address values like the index of a book. Finding a particular index entry could conceivably be done by ordering the keys (like alphabetizing entries in an index) and searching for key using a search out of them such as a binary search. Preferably, however, to ensure high application performance, index systems often rely on random hashing-based indexes, whose specific design may depend on the particular system. Generally a hash includes keys and values at locations within the index may be determined by applying a hash type function to the key. A benefit of hash indexes is that the hash function immediately directs the user to the necessary key-value pair. For example, wide-area network (“WAN”) optimizers, Web caches and video caches may employ large streaming hash tables. De-duplication systems may employ bloom filters to summarize the underlying object stores. Content similarity engines and certain video proxies may employ locality sensitive hash (“LSH”) tables. Given the volume of the underlying data, the indexes typically span several tens of Gigabytes, and indexes continue to grow in size. The information in indexes of this type are held both in the key-value pairs of the index but also in the particular topology of the index, that is the location and not simply the order of the keyvalue pairs in the index. Compressing or reordering the entries in a hash type index, for example for space savings, would render the hash index inoperable. 
         [0005]    Across such systems, the index may be quite intricate in design. Significant engineering is often devoted to ensure high index performance, particularly with respect to achieving low latency and high throughput, at low costs, particularly with respect to the value of each component used to store the index, as well as the amount of energy they consume. Many state-of-the-art systems advocate using solid-state drive (“SSD”) implementations comprised of flash memory to store indexes, given flash memory&#39;s superior density, lower cost and energy efficiency over conventional memory, such as DRAM, and superior density, energy efficiency and high random read performance over conventional disk storage. As used herein, SSD will be understood to be non-volatile solid-state memory commonly known as flash memory. 
         [0006]    In SSD&#39;s, a flash memory page, which may be between 2048 and 4096 bits in size, is typically the smallest unit of read or write operations. Accordingly, reading a single entry in an index stored in the SSD, such as a 16 Byte key-value pair entry, may be as costly as reading a page. In addition, pages are typically organized into blocks with each block spanning 32 or 64 pages. While the performance of random page reads may be comparable to that of sequential page reads, random page writes are typically much slower. 
         [0007]    Some ability to provide increased throughput in SSD implementations via leveraging certain parallelisms currently exists. Certain SSD implementations have begun to support native command queuing (“NCQ”), in which multiple I/O operations may execute concurrently. 
         [0008]    Some recent research proposals have proposed SSD-based indexes for large key-value stores. 
         [0009]    One such proposal, “Cheap and Large CAMs for High Performance Data-Intensive Networked Systems,” NSDI 2010, Ashok Anand, Chitra Muthukrishnan, Steven Kappes, Aditya Akella and Suman Nath, referred to as “BufferHash,” the contents of which are hereby incorporated by reference, buffers all insertions in the memory, and writes them in a batch on flash. BufferHash maintains in-memory bloom filters to avoid spurious lookups to any batch on flash, and requires less than one page read per lookup on average. However, BufferHash often scans multiple pages in the worst case due to false positives produced by the bloom filters and typically requires greater than 4 bytes/key. 
         [0010]    Another proposal, “SILT: A Memory-Efficient, High-Performance Key-Value Store,” SOSP, pages 1-13, 2011, H. Lim, B. Fan, D. G. Andersen, and M. Kaminsky, referred to as “SILT,” the contents of which are hereby incorporated by reference, comes close to meeting the design requirements outlined above by achieving a low memory footprint (0.7 bytes/entry) and requiring a single page lookup on average. However, SILT uses a much more complex design than other systems in that it employs a plurality of data structures where one is highly optimized for a low memory footprint and others are write-optimized but require more memory. SILT continuously moves data from the write-optimized data structures to the memory-efficient data structure. In doing so, SILT has to continuously sort new data written and merge it with old data, thereby increasing the computation overhead. These background operations also affect the performance of SILT under continuous inserts and lookups. For example, the lookup performance drops by 21% for a 50% lookup-50% insert workload on 64B key-value pairs. The authors of SILT also acknowledge that sorting becomes performance bottleneck. 
         [0011]    The conventional wisdom with respect to index design is that domain and operations-specific SSD optimizations are necessary to meet appropriate cost-performance trade-offs. This poses two problems: (a) SSD implementations having poor flexibility, and (b) SSD implementations having poor generality. 
         [0012]    Poor Flexibility: 
         [0013]    Index designs often target a specific point in the cost-performance spectrum, severely limiting the range of applications that can use them. This also makes indexes difficult to tune, for example, using extra memory for improved performance. In addition, indexes are often designed to work best under specific workloads. As a result, even minor deviations often cause performance to be quite variable. 
         [0014]    Poor Generality: 
         [0015]    The design patterns often employed typically apply only to the specific data structure on hand. As a result, it is often difficult to employ different indexes in tandem, such as hash tables for cache lookups alongside LSH tables for content similarity detection over the same underlying content, as they may employ conflicting techniques that result in poor SSD input/output (“I/O”) performance. 
       SUMMARY OF THE INVENTION 
       [0016]    The present invention significantly improves the access of index data from flash type memories which have relatively large increments of data access by providing buffer indexes that can accumulate hash type index data for writing to the flash memory. The accumulated index data is arranged on the flash memory so that related data, meaning data related to the same hash, is clustered for more efficient readout. The clustering may be on a flash “page” to be read out together or may take advantage of underlying parallel structure of the flash memory. 
         [0017]    Slicing enables combining multiple reads into a single “slice read” of related items, offering high read performance. 
         [0018]    Small in-memory indexes, such as hash tables, bloom filters or LSH tables, may be used as buffers for insert operations to resolve the issue of slow random writes on the SSD. When full, these buffers are written to the SSD. Each of these written data structures are called “incarnations.” Data is organized on the SSD such that all related entries of different incarnations are located together in a slice, thereby optimizing lookup. The size of a slice may be tuned to control I/O cost. 
         [0019]    In addition, the internal architecture of an SSD may be leveraged to achieve higher performance via parallelism. Such parallelism may occur at various levels in the architecture of the SSD, such as the channel-level, the package-level, the die-level and the plane-level. Parallelism benefits may be more significant under particular I/O patterns, and, as such, identifying such patterns and encapsulating regular I/O workloads into them may provide significantly higher performance. Based on the architecture of the SSD, read requests may be appropriately reordered (without violating application semantics) to distribute them uniformly to extract maximal parallelism benefits. 
         [0020]    In addition to supporting high performance, the buffering and slicing primitives used in our indexes eliminate the need to maintain complex metadata to assist in index I/O operations. This frees memory and compute resources for use by higher layer applications. Buffering and slicing also facilitate extending the indexes to use multiple SSDs in the same system, offering linear scaling in performance while imposing sub-linear scaling in memory and CPU overhead. State-of-the-art techniques typically cannot be “scaled out” in a similar fashion. 
         [0021]    Different indexes may each leverage these optimizations, which may be easier to tune to achieve optimal performance under a given cost constraint, and which may support widely-varying workload patterns and applications with differing resource requirements as compared to past implementations. These optimizations may also offer better input/output operations per second (“IOPS”), cost less and consume lower energy than past implementations. 
         [0022]    As described herein, aspects of the present invention provide a method for indexing data in a storage system comprising: (a) receiving a data element for storage in a storage system at a storage address; (b) determining a slot address in an index in a first memory as a function of a key value of the data element for storage; (c) storing the data element for storage linked to the storage address as an index pair at the slot address; and (d) transferring at an interval the index pair from the first memory to an index in a second memory being a flash memory larger in capacity than the first memory to be preferentially combined with previously transferred index pairs having the same slot address. 
         [0023]    The method may further comprise: (e) receiving a key value of a data element for retrieval from the storage system; (f) determining a slot address in the index of the second flash memory as a function of a value of the data element for retrieval; (g) reading the preferentially combined index pairs having the same slot address from the second flash memory in a single read cycle; and (h) identifying the data element for retrieval and obtaining a linked storage address. There may be multiple first memories, and step (d) may move the contents of common slot addresses of each of the first memories into a corresponding slot memory of the second memory. 
         [0024]    The common slot addresses of the first memories may be less than all slot addresses of the first memories and the predetermined time may be a time when the common slot addresses of the all the first memories have been filled. 
         [0025]    The transferred index pairs from the first memories may be combined to be concentrated in a page of the second memory, wherein a page represents a unit of data readout of the second memory. 
         [0026]    The method may further comprise reordering a plurality of read requests to allow a plurality of read cycles to occur at the same time within the second flash memory. A plurality of read cycles may occur on channels leading to different flash memory packages within the second flash memory at the same time. 
         [0027]    An interval may occur after a predetermined number of index pairs have been stored at slot addresses. 
         [0028]    The method may further comprise a plurality of indexes in the first memory, wherein determining the same slot address based on different data elements results in storing the different data elements linked to their respective storage addresses as index pairs in different indexes using the same slot address. 
         [0029]    The index may comprise a hash table, and could further comprise a locality-sensitive hash table. 
         [0030]    The first memory may be DRAM. 
         [0031]    The method may further comprise: (e) determining if a key value for another data element may be in the storage system by using a bloom filter in the first memory; and (f) transferring at an interval the bloom filter from the first memory to a bloom filter in the second memory to be preferentially combined with previously transferred bloom filters using the same hash function. 
         [0032]    Another embodiment may provide a method for indexing data in a storage system using flash memory comprising: (a) determining the mapping between a first logical page and a first plurality of memories coupled to a first channel within a flash memory; (a) determining the mapping between a second logical page and a second plurality of memories coupled to a second channel within the flash memory; and (c) reordering a plurality of read requests to the flash memory to allow a plurality of read cycles to occur at the same time within the flash memory. 
         [0033]    The plurality of read cycles may occur on channels leading to different flash memory packages within the flash memory at the same time. 
         [0034]    The method may further comprise: (d) receiving a data element for storage in a storage system at a storage address; (e) determining a slot address in an index in a first memory smaller in capacity than the flash memory as a function of a value of the data element for storage; (f) storing the data element for storage linked to the storage address as an index pair at the slot address; and (g) transferring at an interval the index pair from the first memory to an index in the flash memory to be preferentially combined with previously transferred index pairs having the same slot address. 
         [0035]    An interval may occur after a predetermined number of index pairs have been stored at slot addresses. 
         [0036]    The method may further comprise a plurality of indexes in the first memory, wherein determining the same slot address based on different data elements results in storing the different data elements linked to their respective storage addresses as index pairs in different indexes using the same slot address. 
         [0037]    The index may be a random hash-based index. 
         [0038]    The method may further comprise: (h) receiving a data element for retrieval from the storage system; (i) determining a slot address in the index of the flash memory as a function of a value of the data element for retrieval; (j) reading the preferentially combined index pairs having the same slot address from the flash memory in a single read cycle; and (k) identifying the data element for retrieval and obtaining a linked storage address. A single read cycle may result in reading a flash memory page. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0039]    Embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which: 
           [0040]      FIG. 1  is a block diagram of a simplified computer data system having a mass storage device, a solid-state drive and a memory in accordance with an embodiment of the present invention; 
           [0041]      FIG. 2A  is a block diagram of a flash memory package, and  FIG. 2B  is a block diagram of a flash memory plane, each in accordance with an embodiment of the present invention; 
           [0042]      FIG. 3  is a logical diagram illustrating indexing data in a storage system in accordance with an embodiment of the present invention; and 
           [0043]      FIG. 4  is a logical diagram illustrating adding concurrency to slice hash in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0044]    Referring to  FIG. 1 , the present invention shall be described in the context of a simplified computer system  10  having a mass storage device (“MSD”)  12 , a solid-state drive (“SSD”)  14  and a memory  16  in accordance with an embodiment of the present invention. The mass storage device  12 , which may be, for example, one or more hard disk drives, optical disc drives or magnetic tape drives, holds data which may be measured, for example, in Petabytes or Exabytes, and couples directly or indirectly to a device controller  18 , which may be, for example, one or more Serial ATA (“SATA”) controllers or similar devices. 
         [0045]    The device controller  18  also couples directly or indirectly to the SSD  14 , which may be measured in size, for example, in Gigabytes, such as a 128 Gigabyte SSD, and the device controller  18  also couples directly or indirectly to a system controller or chipset  20 . The system controller or chipset  20  couples directly or indirectly to one or more system processors  60 , which may execute computer readable software fixed in a tangible medium, and to memory  16 . The memory  16  may be any conventional computer system memory, and in a preferred embodiment, may be dynamic random access memory (“DRAM”), which may be measured, for example, in Gigabytes. 
         [0046]    The SSD  14  comprises interface logic  30 , an SSD controller  32 , a RAM buffer  40  and a plurality of flash memory packages  42 ,  44 ,  48  and  50 , or similar non-volatile computer memory which can be electrically erased and reprogrammed. The device controller  18  communicates with interface logic  30 , which, in turn, communicates with the SSD controller  32  generally via I/O requests and responses. 
         [0047]    The SSD controller  32  comprises an SSD processor  34  or similar logic, a buffer manager  36  and a flash controller  38 . The SSD processor  34  couples between the interface logic  30  and the flash controller  38 , and the SSD processor  34  also couples to the RAM buffer  40 . The buffer manager  36  couples between the interface logic  30  and the flash controller  38 . The SSD controller  32  operates to translate logical pages of incoming requests to physical pages, to translate physical pages of outgoing responses to logical pages, and to issues commands to flash memory packages  42 ,  44 ,  48  and  50  via the flash controller  38 . The flash controller  38  communicates with the plurality of flash memory packages  42 ,  44 ,  48  and  50  via a plurality of flash memory channels  46  and  52 , in which certain flash memory packages  42  and  44  are coupled via one channel  46 , and certain flash memory packages  48  and  50  are coupled via another channel  52 . In a preferred embodiment, data will be organized in the SSD  14  such that that multiple entries to be read reside on the same page, thereby reducing the number of page reads. 
         [0048]    Referring to  FIG. 2A , a block diagram of exemplar flash memory package  42  is shown in accordance with an embodiment of the present invention. Each flash memory package may comprise a plurality of flash memory integrated circuit chips or dies  80  and  82 . In turn, each die  80  and  82  may further comprise a plurality of flash memory planes, such as planes  84  and  86  on die  80 , and planes  88  and  90  on die  82 . 
         [0049]    Referring to  FIG. 2B , a block diagram of exemplar flash memory plane  84  is shown in accordance with an embodiment of the present invention. Each flash memory plane may further comprise a cache register  92 , coupled in turn to a data register  94 , coupled in turn to a plurality of blocks  96 . Each block may further comprise a plurality of pages  98  for holding data. The data register  94  may temporarily store a data page during a read or write. A page generally represents a minimum increment of data access, being either the amount of data that must be written to or read from the SSD package in a single read cycle or write cycle. 
         [0050]    In operation, for a write command, the SSD controller  32  may first transfer data to the cache register  92 , then to the data register  94 , via a channel such as channel  46 . The data may then be written from the data register  94  to a corresponding physical page. Conversely, for a read command, the data may be first read from the physical page to the data register  94 , then to the cache register  92 , and then the data may be transferred from the cache register  92  to the controller via a channel such as channel  46 . This architecture accordingly provides varying degrees and levels of parallelism. Parallelism, as used herein, means that data can be read or written to simultaneously in different parallel structures. 
         [0051]    Each channel can operate in parallel and independently of each other. Thus, the SSD  14  allows channel-level parallelism. Typically, the data transfers from/to the flash memory packages  42  and  44  on the same channel, or the flash memory packages  48  and  50  on the same channel, are serialized. However, data transfers may also be interleaved with other operations, such as reading data from the page  98  to the data register  94  on other packages sharing the same channel. This interleaving allows package-level parallelism. The SSD controller  32  also allocates consecutive logical pages across a gang of different packages on the same channel to provide package-level parallelism. The command issued to a die  80  can be executed independently of others on the same flash memory package  42 . This allows die-level parallelism. 
         [0052]    Accordingly, multiple operations of the same type, such as read cycles, write cycles and/or erase cycles, can occur simultaneously on different planes in the same die. A two plane command may be used for executing two operations of the same type on two different planes simultaneously. This provides plane-level parallelism. Furthermore, data transfers to and from the physical page can be pipelined for consecutive commands of the same type. This may be achieved using the cache register  92  in the plane. For consecutive write commands, the cache register  92  stores the data temporarily until the previous data is written from the data register  94  to the physical page  98 . The cache register  92  may similarly be used for pipelining read commands. 
         [0053]    Currently, reading data from the physical page  98  to the data register  94  may typically takes on the order of 25 microseconds (μs). Data transfers on the channel may typically take on the order of 100 μs. Thus, transfer time on the channel is the primary bottleneck for page reads. As such, the throughput of page reads may be significantly improved by leveraging channel-level parallelism. 
         [0054]    A first approach to extract the benefits of parallelism may be to simply use multiple threads issuing requests in parallel. By issuing multiple requests in parallel, and increasing the depth of the I/O queue, the overall throughput may be considerably improved. 
         [0055]    However, to issue requests in a manner that ideally exploits parallelism, it is important to understand the mapping between pages and channels. Recently, the authors of “Essential Roles of Exploiting Internal Parallelism of Flash Memory Based Solid State Drives in High-Speed Data Processing,” HPCA, pages 266-277, 2011, F. Chen, R. Lee, and X. Zhang, the contents of which are hereby incorporated by reference, have devised a method to determine the mapping. A group of consecutive logical pages is striped across different packages on the same channel. The authors discuss a technique to determine the size of the group that gets contiguously allocated within a channel. They refer to this logical unit of data as a “chunk.” They show how to determine the chunk size and the number of channels in the SSD. Using this, they also show how to derive the mapping policy. In particular, they discuss techniques for deriving two common mapping policies: (a) write-order mapping, where the i th  chunk write is assigned the channel 1% N, assuming N is the number of channels, and (b) logical block address (“LBA”) based mapping, where the LBA is mapped to a channel based on LBA % N. Using the above, the chunk size and number of channels for the 128 Gigabyte SSD  14  may determined, for example, to be 8 Kilobytes and 32, respectively, following a write-order mapping. With this knowledge of the order of writes to the SSD  14 , we can determine the channel corresponding to a page, which enables determining how to reorder and schedule requests to spread them across channels. In addition, package-level parallelism may be achieved by issuing chunk-sized or larger reads. 
         [0056]    Based on the above properties of the SSD  14 , we identify the following guidelines in designing large hash table-based data structures: (a) avoiding random page writes and issue few large writes, (b) combining multiple reads by arranging data in such a way that the multiple lookups can be confined to a single page or a small number of pages, and (c) intelligent request reordering to allow uniform distribution over channels. 
         [0057]    Referring now to  FIG. 3 , a logical diagram illustrating indexing data in a storage system in accordance with an embodiment of the present invention is shown. A data element  100  is received for storage in a storage system  102 , which may be a mass storage device, at a storage address  104 . A slot address  106 , such as slot “0,” is determined in an index  108  in a first memory  110  (“in-memory”), which may be DRAM, as a function  101 , such as a random hash-based function, of a value of the data element  100  for storage. The data element  100  linked to the storage address  104  is stored as an index pair  112  and  114 , respectively, at the slot address  106  in the index  108  in the first memory  110 . The index  108 , a collection of index pairs at various slot addresses in the first memory  110 , may be referred to as an “incarnation.” An alternative embodiment may provide a plurality of incarnations in the first memory  110 , such as an additional index  109  in the first memory  110 . 
         [0058]    At intervals, such as when the index  108  is full, which may be determined, for example, by reaching a predetermined number of slot addresses for an incarnation, the index pairs, such as index pair  112  and  114 , are transferred from the first memory  110  to an index  125 , a portion of which may be referred to as a “slice table,” in a second flash memory  126  larger in capacity than the first memory  110 , such as an SSD, to be preferentially combined with previously transferred index pairs. For example index pair  112  and  114  having the slot address “0” may be transferred to the slice table  125  in the second flash memory  126  at a particular “slice” or index  120  with other index pairs also having the same slot address “0,” such as index pair  130  and  132 . The slice table  125  may exist alongside additional slice tables, such as index  127 . Similarly, index pair  140  and  142  having the slot address “N” may be transferred to the slice table  125  in the second flash memory  126  at a particular “slice”  124  in the second flash memory  126  with other index pairs also having the same slot address “N,” such as index pair  144  and  146 . In other words, index pairs at each slot address in an incarnation are transferred to slices where they are grouped with previously transferred index pairs according to having the same slot address. For “N” slot addresses in the index  108  in the first memory  110 , there may be “N” slices in the index or slice table  125  in the second flash memory  126 . For such embodiments using hash tables, this may be referred to as “slice hash.” Such intervals need not occur at fixed or predetermined times. 
         [0059]    In a preferred embodiment, the size of a slice can be limited to a page, and thus it would require only one page read. For example, for a 16B key-value pair, one slice can contain as many as 128 incarnations. 
         [0060]    Additional incarnations may be created in the first memory  110 , such as the additional index  109 . For example, determining the slot address for distinctly different data values could result in determining the same slot address. In this case, the entries may be stored in different incarnations using the same slot address. In transferring incarnations to the slice table, the most recently created incarnation may be transferred as the latest entries in the corresponding slice table—with the oldest entries in the slice table evicted as may be required, such as due to space limitations—a in a FIFO order. 
         [0061]    A slot address  106 , such as slot “0,” is determined in an index  108  in a first memory  110  (“in-memory”), which may be DRAM, as a function  101 , such as a random hash-based function, of a value of the data element  100  for storage. 
         [0062]    The data element  100  may also be received for retrieval from the storage system. In this case, a slot address  134  is determined in the index or slice table  125  of the second flash memory  126  as a function of a value of the data element  100  for retrieval. The preferentially combined index pairs having the same slot address are read from the second flash memory  126  in a single read cycle, the data element for retrieval is identified and a linked storage address is obtained. 
         [0063]    For inserts/writes, we insert a key into the in-memory index  108 . If the in-memory index  108  becomes full, we first read the corresponding slice table  125  from the second flash memory  126 . We then replace the entries for the corresponding incarnation for each slot or slice with the entry of the in-memory index  108 . Then, we write back the modified slice table  125  to the second flash memory  126 . The in-memory index  108  is cleared, and the current incarnation count is incremented. Subsequent insertions happen in a similar way. Once all incarnations are exhausted on the second flash memory  126 , the incarnation count is reset to zero. Thus, this scheme supports a default FIFO eviction policy. 
         [0064]    For updates, if the key is in the in-memory index  108 , the in-memory index  108  is updated with the new value. Alternatively, if the key lies on the second flash memory  126 , directly updating the corresponding key-value pair on the second flash memory  126  would cause random page writes and affect performance. Instead, the new key-value pair is inserted into the in-memory index  108 . 
         [0065]    For lookups/reads, the key is first looked up in the in-memory index  108 . If not found, the corresponding slice table is looked up on the second flash memory  126  and the slice is read from the SSD. The entries for all incarnations may be scanned in the order of the latest to the oldest incarnation. This ensures that the lookup does not return stale values. 
         [0066]    Partitioning Slice Hash: 
         [0067]    Based on the first few bits of keys, the in-memory index  108  may be partitioned into multiple small in-memory indexes, and, for each in-memory index  108 , a corresponding small-sized slice table on flash may be maintained. Thus, if an in-memory partition becomes full, only the corresponding slice table on the SSD requires updating. In this way, the size of slice tables on flash and the worst case insertion latency may be controlled. 
         [0068]    Leveraging Available Memory: 
         [0069]    If additional memory is available, spurious lookups may be reduced using in-memory bloom filters. All lookups may be first checked in these bloom filters. If the bloom filters indicate that a key is present in the second flash memory  126 , only then is an SSD lookup issued. Further, memory may be used opportunistically. For example, bloom filters can be maintained for only some partitions, for example, those that are accessed frequently. This gives the ability to adapt to memory needs, while ensuring that in the absence of such additional memory application performance targets are still met. 
         [0070]    Adding Concurrency 
         [0071]    Referring now to  FIG. 4 , a diagram illustrating adding concurrency to slice hash is shown in accordance with an embodiment of the present invention. In order to leverage the parallelism inherent to an SSD, I/O requests should be issued in parallel. Instead of using a multithreaded programming model, multiple concurrent I/O requests may be issued to the SSD, such as that described in “B+−Tree Index Optimization by Exploiting Internal Parallelism of Flash-Based Solid State Drives,” PVLDB, 5, 2011, H. Roh, S. Park, S. Kim, M. Shin, and S.-W. Lee, referred to as “psync I/O,” the contents of which are hereby incorporated by reference. Internally, psync I/O uses multiple asynchronous I/O calls, and waits until all I/O&#39;s are completed. 
         [0072]    A controller  200  may processes requests originating from request queue  202 , which may comprise insert, update and/or lookup operations, in batches. The controller  200  first processes all requests that can be instantly served in memory. Then the controller  200  processes lookup requests which need reading from the SSD. To leverage channel-level parallelism maximally, the controller should pick requests that go to different channels. Based on determining a mapping between pages and channels as discussed above, a channel-estimator may be developed to estimate the mapping between read requests and channels. Using these estimates, a set of K requests, with K corresponding to the size of the SSD&#39;s NCQ, such that the number of requests picked for any channel is minimized. While it is desirable to use as much concurrency as the NCQ can provide, it is important to optimally exploit channel parallelism. 
         [0073]    The algorithm underlying request selection works as follows. In block  204 , a “depth” for each channel is maintained, which estimates the number of selected requests for a channel. Multiple passes over the request queue are taken until K requests are selected. In each pass, requests that would increase the depth of any channel by at most 1 are selected. In this manner, the set of read requests to be issued are found. 
         [0074]    In block  206 , the controller then asks a worker  210  to process these read requests in parallel, such as using psync I/O. While the worker  210  is waiting for flash reads to complete, the controller also determines the next batch of read requests to be issued to the worker  210 . After the flash page reads are complete, the worker  210  searches the entries of all incarnations on the corresponding flash page for the given key. 
         [0075]    After processing lookups, in block  208  the controller assigns SSD insert requests to the worker  210 . These occur when an in-memory index is full and needs to be flushed onto the Flash SSD  212 . The worker  210  processes these SSD insert requests, and accordingly reads/writes slice tables from the SSD  212 . 
         [0076]    Note that there may be consistency issues with reordering reads and writes. The controller handles such corner cases explicitly. 
         [0077]    Building on the technique used in “Essential Roles of Exploiting Internal Parallelism of Flash Memory Based Solid State Drives in High-Speed Data Processing,” write-order mapping to predict the channel corresponding to a request may be determined. As discussed above, data chunk writes alternate across channels. In other words, the first write goes to the first channel, the second write goes to the second channel, and so forth. Knowing this write order can help determine the channel for any chunk. One approach is to maintain an index that keeps track of the assignment of each chunk to a channel; whenever a chunk is written, estimate its channel as 1% N for the i th  write and update the index. For example, the size of the index may be estimated around 160 Megabytes for 4 Kilobyte data chunk in a 128 Gigabyte SSD, and assuming 4 bytes for the chunk identifier, and 1 byte for the channel in the index. 
         [0078]    We consider an approach that does not require any index management. We configure the size of the slice table to be a multiple of N×ChunkSize, where N is the number of channels. This simplifies determination of the channel. Whenever a slice table is written to the SSD, there will be N chunk writes, and the i th  chunk write would go to the i th  channel. The subsequent slice table write would also follow the same pattern; after the N th  channel, the first chunk write would go to the first channel, the second chunk write would go to the second channel, and so on. In other words, once we determine the relative chunk identifier (first, or second, or Nth) for an offset in the slice table, we can determine the channel. The relative chunk identifier can be determined as the offset modulo chunk size. 
         [0079]    Due to its simplistic design and low resource footprint, slice hash can easily leverage multiple SSDs attached to a single machine. Slice hash can benefit from multiple SSD&#39;s in two ways: (a) higher parallelism (the key space is partitioned across multiple SSDs; one controller-worker combination for each SSD is maintained; lookup/insert requests may be distributed across multiple SSDs; and each controller may handle requests in parallel), and (b) lower memory footprint (for each in-memory index, one slice table per SSD is maintained). For lookups, concurrent lookup requests to all SSDs may be issued, in effect requiring an average latency of one page lookup. For insertions, insertions into a slice table on one SSD are made, and as it becomes full, insertions move to next SSD. Once all SSD&#39;s slice tables are full, insertions return to the slice table on the first SSD. This may reduce the memory footprint, while maintaining the same latency and throughput. Other systems, such as BufferHash and SILT, do not support such scaling out and ease of tuning. 
         [0080]    Leveraging Multiple SSD&#39;s: 
         [0081]    In practice, depending on the specific requirements of throughput and memory footprint, a combination of the above two techniques may be used to tune the system accordingly. Thus, slice hash allows us to leverage multiple SSD&#39;s in many different ways. 
         [0082]    Latency and the memory overhead of slice hash may be analyzed accordingly. Table 2 provides a summary of notations relevant for such analysis. 
         [0000]    
       
         
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                 Symbol 
                 Meaning 
               
               
                   
                   
               
             
             
               
                   
                 M 
                 Total memory size 
               
               
                   
                 N 
                 Number of SSDs 
               
               
                   
                 n 
                 number of partitions 
               
               
                   
                 H 
                 Size of a single hashtable (=M/n) 
               
               
                   
                 s 
                 Size taken by a hash entry 
               
               
                   
                 u 
                 Utilization of tje hashtable 
               
               
                   
                 s eff   
                 Effective average space taken by a hash entry (=s/u) 
               
               
                   
                 k 
                 Number of incarnations (=F/M) 
               
               
                   
                 F 
                 Total flash size 
               
               
                   
                 S 
                 Size of slicetable (=H × k) 
               
               
                   
                 P 
                 Size of a flash page/sector 
               
               
                   
                 B 
                 Size of a flash block 
               
               
                   
                 r p   
                 Page read latency 
               
               
                   
                 r b   
                 Block read latency 
               
               
                   
                 w b   
                 Block write latency 
               
               
                   
                   
               
             
          
         
       
     
         [0083]    The memory overhead per entry may be estimated. The total number of entries in an in memory hash table is H/s eff  where H is the size of a single hash table and s eff  is the effective average space taken by a hash entry (actual size (s)/utilization (u)). The total number of entries overall in a slice hash for a given size F of flash is: 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   
                     F 
                     + 
                     M 
                   
                   H 
                 
                 ) 
               
               × 
               
                 H 
                 
                   s 
                   eff 
                 
               
             
             = 
             
               
                 F 
                 + 
                 M 
               
               
                 s 
                 eff 
               
             
           
         
       
     
         [0084]    Here, M is the total memory size. Hence, the memory overhead per entry is MI #entries, in other words, 
         [0000]    
       
         
           
             
               
                 M 
                 
                   F 
                   + 
                   M 
                 
               
               × 
               
                 s 
                 eff 
               
             
             , 
             
               
 
             
              
             or 
           
         
       
       
         
           
             
               1 
               
                 k 
                 + 
                 1 
               
             
             × 
             
               s 
               eff 
             
           
         
       
     
         [0000]    where k is the number of incarnations. 
         [0085]    For s=16 Bytes (key 8 bytes, value 8 bytes), u=80%, M=1 Gigabyte, and F=32 Gigabytes, the memory overhead per entry is 0.6 bytes/entry. In contrast, SILT and BufferHash have memory overheads of 0.7 bytes/entry and 4 bytes/entry, respectively. 
         [0086]    By using N SSD&#39;s, we can reduce the memory overhead to even lower, 
         [0000]    
       
         
           
             
               1 
               
                 
                   k 
                   × 
                   N 
                 
                 + 
                 1 
               
             
             × 
             
               s 
               eff 
             
           
         
       
     
         [0000]    using the technique outlined above. For the above configuration with N=4 SSD&#39;s, this amounts to 0.15 bytes/entry. 
         [0087]    The average time taken for insert operations may be estimated. The time taken to read a slice table and then write it back is first calculated. This is given by 
         [0000]    
       
         
           
             ( 
             
               
                 
                   S 
                   B 
                 
                 × 
                 
                   r 
                   b 
                 
               
               + 
               
                 
                   S 
                   B 
                 
                 × 
                 
                   w 
                   b 
                 
               
             
             ) 
           
         
       
     
         [0000]    where S is the size of the slice table, B is the size of a flash block, and r b  and w b  are the read and write latencies per block, respectively. This happens after H/s eff  entries are inserted to the hash table; all insertions up to this point are made in memory. Hence, the average insertion cost is 
         [0000]    
       
         
           
             
               ( 
               
                 
                   
                     S 
                     B 
                   
                   × 
                   
                     r 
                     b 
                   
                 
                 + 
                 
                   
                     S 
                     B 
                   
                   × 
                   
                     w 
                     b 
                   
                 
               
               ) 
             
             × 
             
               
                 s 
                 eff 
               
               H 
             
           
         
       
     
         [0088]    Replacing S by H*k, we get 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     
                       r 
                       b 
                     
                     + 
                     
                       w 
                       b 
                     
                   
                   ) 
                 
                 × 
                 
                   s 
                   eff 
                 
                 × 
                 k 
               
               B 
             
             , 
           
         
       
     
         [0000]    which is independent of the size of the hash table. 
         [0089]    For typical block read latency of 0.31 ms, a blocked write latency of 0.83 nearly seconds, s=16 Bytes, M=1 Gigabyte, F=32 Gigabytes, and u=80%, the average insertion cost is approximately 5.7 microseconds (μs), and thus still small. In contrast BufferHash has an average insertion latency of approximately 0.2 μs. 
         [0090]    Similarly, the worst-case insertion cost of slice hash is (0.31+083)×S/B milliseconds (ms). By configuring S to be the same size as B, we can control the worst-case insertion cost of the (0.31+083)=1.14 ms, slightly higher than the worst-case insertion cost (0.83 ms) of BufferHash. 
         [0091]    We consider a cuckoo hashing based hash table implementation with two hash functions. Suppose the success probability of the first lookup is p. For each lookup, a corresponding slice is read. We configure H, the size of an in-memory hash table, such that size of a slice is not more than a page. With this, the average lookup cost is r p +(1−p)×r p  or (2−p)×r p  assuming that almost all of the lookups go to SSD and only few requests are served by in-memory hash tables. For p=0.9, r p =0.15 ms, the average lookup cost is 0.16 ms. SILT and BufferHash, both have similar average lookup cost. 
         [0092]    The worst case condition may occur upon reading both pages corresponding to the two hash functions. The worst case lookup latency is 2×r p . For r p =0.15 ms, this cost is 0.3 ms. In contrast, BufferHash may have very high worst case lookup latency; in the worst case, it may have to scan all incarnations. For k=32, this cost would be 4.8 ms. 
         [0093]    The ratio of the number of insertions to the number of block writes to the SSD may be estimated as the ratio r write . A hash table becomes full after every H/s eff  inserts, after which the corresponding slice table on flash is modified. The number of blocks occupied by a slice table is S/B or kx H/B. Thus 
         [0000]    
       
         
           
             
               r 
               write 
             
             = 
             
               
                 
                   H 
                   
                     s 
                     eff 
                   
                 
                 × 
                 
                   B 
                   
                     k 
                     × 
                     H 
                   
                 
               
               = 
               
                 B 
                 
                   k 
                   × 
                   
                     s 
                     eff 
                   
                 
               
             
           
         
       
     
         [0094]    Thus, by increasing the number of incarnations k, the frequency of writes to SSD (which is inversely proportional to r write ) also increases. This in turn affects the overall performance. 
         [0095]    Slice hash increases the number of writes to the SSD which may impact its overall lifetime. The lifetime of an SSD may be estimated. For a given insert rate of R, the number of block writes to the SSD per second is R/r writes  or the average time interval between block writes is r writes /R. The SSD may supports E erase cycles. Assuming the wear leveling scheme for flash is perfect, then the lifetime (T) of the SSD could be approximately estimated as number of blocks, F/B times erase cycles E, times average time interval between block writes, r wrires /R, in other words, 
         [0000]    
       
         
           
             T 
             = 
             
               
                 
                   F 
                   × 
                   E 
                   × 
                   
                     r 
                     writes 
                   
                 
                 
                   R 
                   × 
                   B 
                 
               
               . 
             
           
         
       
     
       Bloom Filters: 
       [0096]    Bloom filters, including as described in “Network applications of bloom filters: A survey,” Internet Mathematics, A. Broder and M. Mitzenmacher, 2005, 1(4):485-509; “Bloomflash: Bloom Filter on Flash-Based Storage,” In ICDCS, B. K. Debnath, S. Sengupta, J. Li, D. J. Lilja, and D. H. C. Du., pages 635-644, 2011; and “Buffered Bloom Filters on Solid State Storage,” In ADMS, M. Canim, G. A. Mihaila, B. Bhattacharjee, C. A. Lang, and K. A. Ross, 2010, the contents of each of which are hereby incorporated by reference are traditionally used as in-memory data structures. 
         [0097]    Some recent studies have observed, with storage costs falling and data volumes growing into the peta- and exa-bytes, space requirements for Bloom filters constructed over such datasets are also growing commensurately. In limited memory environments, there is a need to maintain large Bloom filters on secondary storage. The techniques described above may be applied for supporting Bloom filters on flash storage efficiently, referred to as “slice bloom.” 
         [0098]    Similar to slice hash, several in-memory small Bloom filters and corresponding slice filters may be provided on flash, similar to slice tables in slice hash described above with respect to  FIG. 3 . The in-memory Bloom filters are written to flash as incarnations. Each slot in a slice filter contains the bits from all incarnations taken together. 
         [0099]    In traditional Bloom filters, a key lookup requires computing multiple hash functions and reading entries corresponding to the bit positions computed by the hash functions. Here, the corresponding in-memory Bloom filter partition may be first looked up, and then the corresponding slice filter on the flash storage for each hash function may be looked up. The number of hash functions would determine the number of page lookups, which could limit the throughput. 
         [0100]    Since flash storage is less expensive than conventional memory, such as DRAM, more space per entry on flash may be used, in other words, a larger m/n where m and n are the Bloom filter size and number of unique elements, respectively, and reduce the number of hash functions (k) while maintaining a similar overall false positive rate. For example, for a target false positive rate of 0.0008, instead of using m/n=15 and k=8, we can use m/n=32 and k=3. By reducing k, the number of page lookups may be reduced and performance improved. 
         [0101]    Locality Sensitive Hash Tables: 
         [0102]    Locality sensitive hashing, including as described in “Similarity Search in High Dimensions via Hashing,” In Proc. VLDB, 1999, A. Gionis, P. Indyk, and R. Motwani; “Image Similarity Search with Compact Data Structures,” In Proc. CIKM, 2004, Q. Lv, M. Charikar, and K. Li; and “Small Code and Large Image Databases for Recognition,” In Proc. CVPR, 2008, A. Torralba, R. Fergus, and Y. Weiss, the contents of each of which are hereby incorporated by reference, is a technique used in the multimedia community for finding duplicate videos and images at large scale. These systems use multiple hash tables. For each key, the corresponding bucket in each hash table is looked up. Then, all entries in the buckets are compared with the key to find the nearest neighbor based on a certain metric, for example, the Hamming distance or an L2 norm. Once again, the techniques discussed above may be applied to build large LSH hash tables efficiently on flash storage, referred to as “slice LSH.” 
         [0103]    Each of the LSH hash tables is designed as slice hash; when a query comes, it goes to all slice hash instances. We further optimize for LSH to exploit SSD-intrinsic parallelism. When we write in-memory LSH hash table partitions to flash, they are arranged on the flash such that each LSH slice table partition belongs to one channel and the hash tables are uniformly distributed over multiple channels. This ensures that multiple hash table lookups would be uniformly distributed over multiple channels, and the intrinsic parallelism of flash SSDs is maximally leveraged. 
         [0104]    One or more specific embodiments of the present invention have been described above. It is specifically intended that the present invention not be limited to the embodiments and/or illustrations contained herein, but include modified forms of those embodiments including portions of the embodiments and combinations of elements of different embodiments as come within the scope of the following claims. It should be appreciated that in the development of any such actual implementation, as in any engineering or design project, numerous implementation-specific decisions must be made to achieve the developers&#39; specific goals, such as compliance with system-related and business related constraints, which may vary from one implementation to another. Moreover, it should be appreciated that such a development effort might be complex and time consuming, but would nevertheless be a routine undertaking of design, fabrication, and manufacture for those of ordinary skill having the benefit of this disclosure. Nothing in this application is considered critical or essential to the present invention unless explicitly indicated as being “critical” or “essential.” 
         [0105]    Certain terminology is used herein for purposes of reference only, and thus is not intended to be limiting. For example, terms such as “upper,” “lower,” “above,” and “below” refer to directions in the drawings to which reference is made. Terms such as “front,” “back,” “rear,” “bottom,” “side,” “left” and “right” describe the orientation of portions of the component within a consistent but arbitrary frame of reference which is made clear by reference to the text and the associated drawings describing the component under discussion. Such terminology may include the words specifically mentioned above, derivatives thereof, and words of similar import. Similarly, the terms “first,” “second” and other such numerical terms referring to structures do not imply a sequence or order unless clearly indicated by the context. 
         [0106]    When introducing elements or features of the present disclosure and the exemplary embodiments, the articles “a,” “an,” “the” and “said” are intended to mean that there are one or more of such elements or features. The terms “comprising,” “including” and “having” are intended to be inclusive and mean that there may be additional elements or features other than those specifically noted. It is further to be understood that the method steps, processes, and operations described herein are not to be construed as necessarily requiring their performance in the particular order discussed or illustrated, unless specifically identified as an order of performance. It is also to be understood that additional or alternative steps may be employed. 
         [0107]    References to “a microprocessor” and “a processor” or “the microprocessor” and “the processor” can be understood to include one or more microprocessors that can communicate in a stand-alone and/or a distributed environment(s), and can thus be configured to communicate via wired or wireless communications with other processors, where such one or more processor can be configured to operate on one or more processor-controlled devices that can be similar or different devices. Furthermore, references to memory, unless otherwise specified, can include one or more processor-readable and accessible memory elements and/or components that can be internal to the processor-controlled device, external to the processor-controlled device, and can be accessed via a wired or wireless network. 
         [0108]    All of the publications described herein including patents and non-patent publications are hereby incorporated herein by reference in their entireties.