Microsoft flash research inspires EMC
Data Domain flash-based dedupe coming
EMC is using Microsoft research into flash use as a memory tier between DRAM and disk drives to speed up Data Domain deduplication.
FlashStore  is a Microsoft research project that batches up flash writes in a server's main memory and then writes them as a page or block, in effect turning random flash writes into sequential ones and avoiding block erase/write cycles that are otherwise endemic to flash.
Such cycles both slow down flash writes and can shorten its working life by increasing the number of block erase/write cycles in a time period, flash blocks having a finite erase/write cycle capacity.
The Microsoft researchers Sudipta Sengupta, Jin Li and intern Biplob Debnath said FlashStore minimises its DRAM footprint by using an index to access the data in the flash cache.
This is a key:value store using a hash-table index. Microsoft tells us it saves space on both the vertical and horizontal dimensions of the table by using a version of cuckoo hashing - where keys in table slots serve as eggs pushed out of the nest - to reduce the number of slots and slot sizes in the hash table.
In cuckoo hashing, as we understand it, for any key value two hash functions are used instead of one, giving the key two possible locations in the table instead of one. Any pre-resident key in that slot is booted out and it is then put in its alternative slot, booting out any already resident key until an empty slot is found.
Apparently this saves up on lookup time, with just two slot inspections needed. But the table has to be less than half full and, if it gets full, it has to be rebuilt because there isn't an empty slot for the last displaced key value hash.
Returning from computer science territory
The researchers say that the FlashStore DRAM table is frugal in its use of DRAM and provides fast access time with an average of a single flash read per lookup. This means servers using it can perform many times faster; "several tens of factors of increased data throughput" is the phrasing they use.
Sengupta says this about applications with high IOPS needs: "You could replace 10 to 20 hard drives with one flash drive using FlashStore for such applications.
"That gives you a capital-expenditure savings, power savings, and operational-expenditure savings, as well, and you also get much faster throughput: an all-win situation on the three metrics of price, power, and performance.”
It sounds like deduplication could use this technique. Microsoft's FlashStore paper says: "FlashStore also achieved significantly better results than a RAM/hard drive or a flash drive when tested with the task of performing data-chunk indexing for data deduplication."
The research team produced a paper in 2010 describing such use with a project called ChunkStash (pdf) . That paper said:
ChunkStash uses one flash read per chunk lookup and works in concert with RAM prefetching strategies. It organises chunk metadata in a log-structure on flash to exploit fast sequential writes. It uses an in-memory hash table to index them, with hash collisions resolved by a variant of cuckoo hashing.
Having gained his PhD, Debnath joined EMC last November, as a senior software engineer. He is working in the Backup and Recovery Systems division, the one that houses Data Domain and Avamar. Debnath's LinkedIn entry  says his "main focus is to build a scalable index to support large-capacity deduplication systems".
EMC doesn't currently employ servers with cache installed. It does have storage arrays with an enterprise flash drive (EFD) storage tier and this can be used as a general FastCache (flash cache) for the array, caching the array's I/Os in pretty much the same was as NetApp's controller-located FlashCache, and caching both reads and writes unlike the NetApp technology which is a read cache only.
What we might look for from EMC is the provision of Data Domain controllers which have PCIe-connected flash, possibly using Fusion-io, STEC or Violin Memory flash product, and having faster deduplication performance.
As an aside there is potential here for Microsoft to use FlashStore in its own storage products, such as Windows Storage Server. That would require, as per the Microsoft server model, server suppliers to step up with X86 servers incorporating a flash memory tier. Noting that Dell is using Fusion-io  in this way already and has bought specialised image and file deduper Ocarina, it isn't too much of a stretch to imagine Dell could be shipping FlashStore-like systems in the future.
In fact, El Reg prognosticators think deduplication system controllers and servers for IOPS-intensive applications could have a flash memory tier as a matter of course in a year or two. ®