Emmanuel Goossaert

FWIW: This seems to mostly be lore.
See http://www.nber.org/sys-admin/overwritten-data-guttman.html

Note also "Since writing the above, I have noticed a comment attributed to Gutmann conceding that overwritten sectors on "modern" (post 2003?) drives can not be read by the techniques outlined in the 1996 paper, but he does not withdraw the overwrought claims of the paper with respect to older drives."

(the comment is at http://seclists.org/bugtraq/2005/Jul/464)

As for SSD's, it's harder to say because of wear leveling and bad sector replacement. They internally have their own translation layers, and so the overwritten data may not end up where the original data was (this is itself a complicated topic. http://codecapsule.com/2014/02/12/coding-for-ssds-part-3-pages-blocks-and-the-flash-translation-layer/ is a reasonble intro)

However, one neat thing about them is that there are plenty of SSD's that do hardware encryption by default. When they get init'd, they set the key. You can reset the key, and then, pretty much, assuming the SSD's have not been backdoored by our security agencies, it doesn't matter what you do ;)

This assumes you just want to destroy all the data though, not just some of it.

Flash memory is different from a regular drive, and it's to do with how it writes. You can't alter a single bit, you must rewrite the whole block and those can be anywhere from 256KB to 4MB or more. http://codecapsule.com/2014/02/12/coding-for-ssds-part-2-architecture-of-an-ssd-and-benchmarking/

Adding new bits is cheap, though, so if you can come up with an append-only strategy for your system and periodically combine those into a new, pristine version you'll get far more life out of your SSD than if you go around randomly flipping bits. Is Redis using memory-mapped files the problem here? Treating a file like memory is all fine and good until your random bit-flipping has to be directly persisted.

I wonder if future SSD firmware implementations will avoid wear by having a small buffer reserved for little post-write patches that can absorb a few small changes before having to commit to rebuilding the whole block.

There's talk of "annealing" as a way of restoring cells to full life: https://www.extremetech.com/computing/142096-self-healing-self-heating-flash-memory-survives-more-than-100-million-cycles

Has anyone tried reflowing a worn out drive?

In addition to the answer from rndgermandude (which is also a reason why accessing a data structure in RAM, even in a world without cache lines, would be faster and more efficient if stored in a linear array rather than a tree), SSDs are themselves a complex data structure mapping data into erasure blocks in an attempt to minimize wear on the flash memory and increase efficiency. If the size of your fragments is smaller than the size of this block, you are going to take a performance penalty, and the size of this block is large: I did a search just now to find an article for you detailing this, and http://codecapsule.com/2014/02/12/coding-for-ssds-part-5-access-patterns-and-system-optimizations/ mentions 32 megabytes, and anything below that leads to a second layer of data structures on the SSD designed to map the high-level blocks to low-level blocks and incurs erasure penalties.

I read the section on sequential numbers as just illustrating a worst-case scenario of the case that could happen with either a naive hasher or malicious input.

As far as I can see all the graphs but one use random numbers, so hashing won't add anything given good randomness.

I've heard good arguments why linear probing should perform as well as quadratic probing when using Robin Hood bucket stealing, e.g. http://codecapsule.com/2013/11/11/robin-hood-hashing/#comment-44965

> Note that even if you reduce modulo a prime > n, you'll still have the identity over the first n numbers.

Which can be great! E.g. Python uses the identity function for number hashes, because if you're inserting mostly sequential numbers into a dict this gives you better cache performance.

Java still uses a linked list chaining until a threshold is met (8 currently) which it then switches the bucket to a tree. I wish java could switch to open address hashing, but without value types it wouldn't help much (there's work on adding them: http://cr.openjdk.java.net/~jrose/values/values-0.html).

Linear probing would likely be better than cuckoo hashing from a cpu cache perspective (all locations closer in memory). There are probing schemes which result in low number of checks and allow for higher loading factors similar to cuckoo hashing (e.g. robin hood hashing. See http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)

One thing I'm still puzzled about SSD over-provisioning, which is also mentioned by the tutorial (https://codecapsule.com/2014/02/12/coding-for-ssds-part-4-advanced-functionalities-and-internal-parallelism/) recommended by the article:

> A drive can be over-provisioned simply by formatting it to a logical partition capacity smaller than the maximum physical capacity. The remaining space, invisible to the user, will still be visible and used by the SSD controller.

Does the controller read the partition table to decide that the space beyond logic partition is safe to use as scrap?