News for hackers. Stuff that matters.
Re:Damn Cool Algorithms: Log structured storage (2009) by nostrademons on Tuesday May 30, 2017 @07:02PM (#14449276)
SSDs have even more unique access patterns - they give you (relatively) fast seek times, there's no particular penalty for random-access vs. sequential usage, but you really want to avoid writes, both to preserve the lifetime of the drive and because mixing reads & writes with a SSD lowers performance.

In practice (and I haven't worked in a big corp for a couple years now), I don't see SSDs replacing mechanical disks. Rather, they're being used for different functions. Disks are becoming a data warehouse; they're the new tape, but one that systems can write directly to, without needing scheduled backups. Operational serving is moving toward SSDs and RAM, with a periodic processing step that pulls data off disks and builds a pre-made shard that gets written all at once to the SSD. LSM trees are well-adapted to the data-warehousing part of this, which is why you continue to see big uptake of BigTable/Cassandra/Mongo. On the SSD end...most people are using custom algorithms & data structures, AFAIK, but you're seeing a resurgence of data structures like perfect hashes, bloom filters, and plain old sorted arrays, all of which have great read performance but can't be incrementally updated without rebuilding the whole data structure.

Re:Damn Cool Algorithms: Log structured storage (2009) by mattb314 on Tuesday May 30, 2017 @09:11PM (#14449831)
Do you think you could point me towards a source for "mixing reads & writes with a SSD lowers performance"? This seems reasonable, but I've never actually heard it before, and a cursory googling didn't turn much up. I have heard before that small, random writes on SSDs are much more expensive than sequential writes because random writes can produce write amplification and increase fragmentation. It was my impression that SSDs stand to benefit significantly from log structured filesystems despite the mixed read/write load, but I don't follow it that closely and could be wrong.
Re:Damn Cool Algorithms: Log structured storage (2009) by noahdesu on Tuesday May 30, 2017 @11:50PM (#14450303)
Re:Damn Cool Algorithms: Log structured storage (2009) by mattb314 on Wednesday May 31, 2017 @03:12AM (#14450863)
Thanks! This talk is pretty cool.

In case anyone else is interested, in addition to the above video, this [1] paper goes into some of the details, including this explanation:

"Reads and writes on SSDs can interfere with each other for many reasons. (1) Both operations share many critical resources, such as the ECC engines and the lock-protected mapping table, etc. Parallel jobs accessing such resources need to be serialized. (2) Both writes and reads can generate background operations internally, such as readahead and asynchronous write-back [6]. (3) Mingled reads and writes can foil certain internal optimizations. For example, flash memory chips often provide a cache mode [2] to pipeline a sequence of reads or writes. A flash memory plane has two registers, data register and cache register. When handling a sequence of reads or writes, data can be transferred between the cache register and the controller, while concurrently moving another page between the flash medium and the data register. However, such pipelined operations must be performed in one direction, so mingling reads and writes would interrupt the pipelining."

Also relevant to the "seek" conversation below: it turns out many SSDs have read-ahead caches built in, so sequential reads are much faster than random reads after an initial warm-up, just like hard disks (the difference, however is closer to ~5x than to 100x difference you see in HDDs).

[1] http://bit.csc.lsu.edu/~fchen/publications/papers/hpca11.pdf

Re:Damn Cool Algorithms: Log structured storage (2009) by dom0 on Wednesday May 31, 2017 @06:10AM (#14451396)
> there's no particular penalty for random-access vs. sequential usage

This is not really accurate; random access has a penalty compared to sequential access (that's just the physics of it folks™) — the unique characteristic would be that SSDs have more channels*banks than e.g. RAM, which has similar characteristics regarding access patterns. Thus, SSDs achieve close to sequential throughput with large numbers of independent random reads (i.e. high queue depth).

Re:Damn Cool Algorithms: Log structured storage (2009) by cat199 on Wednesday May 31, 2017 @10:05AM (#14452594)
SSDs achieve close to sequential throughput

^ potato =~ potato

Re:Damn Cool Algorithms: Log structured storage (2009) by bogomipz on Tuesday May 30, 2017 @08:27PM (#14449671)
>"SSDs have even more unique access patterns - they give you (relatively) fast seek times,

SSDs don't have seek times at all as there is no actuator arm and read/write head to "seek" into place in order to read/write data.

Re:Damn Cool Algorithms: Log structured storage (2009) by bogomipz on Tuesday May 30, 2017 @11:31PM (#14450245)
This is not a nitpick - the fact that SSDs do not have seek times is an important distinction when discussing storage engines.

You might want to read the following by Jay Kreps one of the authors of Kafka, Voldermort and Samza:

"SSDs and Distributed Data Systems"

>"On traditional hard drives the trade-off between in-place and log-structured storage is a bit of a wash. Write performance for log-structured storage is vastly better, but most applications have more reads than writes. Read performance may be better or worse depending on the details of the implementation (a traditional log-structured merge tree is definitely worse for reads since it does multiple seeks for each uncached read, but hashing variants or SSTables that use bloom filters to avoid unnecessary lookups need not be). However the move to SSDs completely changes this dynamic. Since SSDs have fast seek performance grouping data by key is much less important.

...

Here are the facts you need to know about SSDs:

They eliminate “seek time” and consequentially make random reads very, very fast"[1]

Source:

[1] http://blog.empathybox.com/post/24415262152/ssds-and-distrib...

Instead of downvoting maybe you could engage in a discussion?

Re:Damn Cool Algorithms: Log structured storage (2009) by fizwhiz on Wednesday May 31, 2017 @12:22AM (#14450411)
My guess is that nostrademons was just being somewhat fast and loose with the "seek" terminology. FWIW, your linked snippet by Jay Kreps ends with:

> ... Since SSDs have fast seek performance grouping data...

Clearly, Jay is aware that there is no "seek time" in SSDs :)

Re:Damn Cool Algorithms: Log structured storage (2009) by jorangreef on Wednesday May 31, 2017 @04:13AM (#14451044)
There is "seek time" in SSDs, just as there is "seek time" in RAM. It's just orders of magnitude faster.

Some of the principles remain the same across disk, SSD and RAM. Sequential access is usually faster than random ("seek") access.

Seek time from a storage point of view just means the lookup latency - the cost of jumping to a random source of data (an area on disk or in memory or in another datacenter). You could think of a hash table lookup as "seek time". It could be attributed to an L1/L2 cache reference, main memory reference, physical disk seek or network roundtrip etc.

Just because the concept of "seek time" originated with spinning rust does not mean it must remain there.

See: https://gist.github.com/jboner/2841832

Re:Damn Cool Algorithms: Log structured storage (2009) by bogomipz on Wednesday May 31, 2017 @11:02AM (#14453051)
No there is no seek time in SSDs at all, there is simply a constant latency. And no RAM does not have seek times either. The term "seek" is not some loose and fungible term that can be applied to different subsystems.

A seek is an agreed upon industry concept. A seek is composed of the following components[1]:

• start-up: the arm is accelerated, typically with constant torque (force) until it reaches half of the seek distance, or a fixed maximum velocity;

• coast: for a long seek, the arm will be allowed to coast across most of the distance at its maximum speed;

• slowdown: the arm is brought to rest, hopefully exactly on top of the desired track;

• settle: the disk controller uses servo positioning information to fine-tune the position of the head over the desired track on the selected surface.

Additionally a write seek takes slightly longer than a read seek on a rotating disk, this is because of settling described above. This has no corollary in SSDs.

Rotating disks also have something known as an Average latency which is calculated as the time it takes for the sector of the disk being accessed to rotate into position under a read/write head. The reason I bring this up is because seek and latency are two distinct measurements on mechanical disks and it is the latency measurement which could be applied to SSDs as it is a constant, it mechanical disk this would be gated on the rotational speed of the disk(RPMs)but this is a constant.

And the reason this all matters is that in order to calculate the average IOPS on a mechanical disk you use the following formula:

Divide 1 by the sum of the average latency in ms and the average seek time in ms (1 / (average latency in ms + average seek time in ms).

This formula is obviously meaningless in the context of SSDs.

And average seek time is also well understood to mean:

The average of all possible seek times which technically is the time to do all possible seeks divided by the number of all possible seeks, but in practice it is determined by statistical methods or simply approximated as the time of a seek over one-third of the number of tracks. This formula goes back to IBM and the Winchester drives I believe.

So no in SSDs there is no such thing as a seek. There is simply a latency and that latency is a constant.

[1] http://www.hpl.hp.com/techreports/93/HPL-93-68.pdf

Re:Damn Cool Algorithms: Log structured storage (2009) by ComodoHacker on Saturday June 03, 2017 @12:10AM (#14474967)
I think we can talk about "seek time" if we take FTL into account.