Emmanuel Goossaert

This one is my favorite guide about SSD internals for programmers. https://codecapsule.com/2014/02/12/coding-for-ssds-part-1-introduction…

i found this (https://codecapsule.com/?s=hashing) to be quite instructive as an overview of various hashing techniques. check it out for some fun ?

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-fun… 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?

I found the following link to be an interesting read on the topic: http://codecapsule.com/2014/10/18/implementing-a-key-value-store-part-… The author also has a 6-part series on programming for SSDs: here's a more descriptive blog post for general SSD access patterns and optimizations: http://codecapsule.com/2014/02/12/coding-for-ssds-part-5-access-patter…

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.

The post mentions using tombstones for deletion, but I was under the impression that the variance benefits of Robin Hood hashing weren't realized unless you performed a backwards shift on the remaining elements instead of using a tombstone. See these posts for more information: http://codecapsule.com/2013/11/11/robin-hood-hashing/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-de… Unfortunately there's not great information around the overall CPU performance impact of using a shift vs. tombstone.

Companies generally do not publish their algorithms, unless they are filing for a patent. I came across this great blog post a while back that will give you a pretty solid foundation for NAND management: http://codecapsule.com/2014/02/12/coding-for-ssds-part-1-introduction-… You can google more if you find any of the sections interesting. Yes, I did work for Micron! I'm doing data science now, though, so I'm not currently in the storage industry.

What's interesting to me is that if you read the summary (http://codecapsule.com/2014/02/12/coding-for-ssds-part-6-a-summary-wha… most of the recommendations are exactly the same as when programming against a traditional spinning-oxide hard drive: read and write entire blocks if you can, combine block writes, &c. It's nice to know that all that work on high-performance IO in databases doesn't need to be thrown away just yet.

A more detailed explanation of "backward shift deletion": https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-d…

Implementing a Key-Value Store http://codecapsule.com/2012/11/07/implementing-a-key-value-store-part-… Let's Make a Voxel Engine https://sites.google.com/site/letsmakeavoxelengine/

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-de…

From the docs page [0] for std::collections::HashMap, Rust uses backwards shift deletion [1] instead of the tombstone method. [0] https://doc.rust-lang.org/std/collections/struct.HashMap.html [1] http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-de…

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-patter… 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.

Depends on the implementation. Some algorithms[1] have a load factor no more than 0.80 before insert/lookup performance starts to degrade significantly. Others, like the algorithm used in Rust[2], can achieve load factors in excess of 0.98 without breaking a sweat. [1] http://netjs.blogspot.com.au/2015/05/how-hashmap-internally-works-in-j… [2] - http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-de…

Why does this link have a 2-stage redirection? The content is at: http://codecapsule.com/2014/02/12/coding-for-ssds-part-6-a-summary-wha… Oh, I wouldn't be surprised if someone complains that this should be tagged [2014]. The date it has is "2014 February 12".

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-… 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… Has anyone tried reflowing a worn out drive?

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-… 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.