4 ms·
I'm not sure if drives do this, but it's theoretically possible to linearize a random write workload, with the disadvantage that when you come to read the data,
by londons_explore 7y ago
I'm not sure if drives do this, but it's theoretically possible to linearize a random write workload, with the disadvantage that when you come to read the data, a sequential read becomes a random read.
Typically stuff you write randomly (small files, databases) one tends to read randomly, so it's usually worth linearizing writes.
The only case where you are at a performance disadvantage is when you did random writes followed by more than one linear read.
Things like LogFS do this, as do most SSD's. I'm pretty surprised modern HD's don't do it internally too.
- mikepurvis 7y ago> theoretically possible to linearize a random write workload Are there filesystems or databases which are specially designed to optimize for this constraint? It would basically boil down to structuring your whole system as a set of interlinked mostly-append journals.
- barrkel 7y agoYes, they're called log-structured file systems. Been around for decades, lots of research.
- londons_explore 7y agoBigtable is exactly this. An entire database is saved in a small number of files which are are append-only (and therefore can be written fully linearly). Reads of a single record usually only read a single disk block. In-memory indexes to locate the block are fairly small, even for 1B+ records. Reads of a range of records do N range reads of blocks, where N is typically < 5, and the number of bytes read compared to the number of bytes returned to the user is typically <10% overhead.
- deleted 7y ago[deleted]
- pwg 7y agoYes, see this at least as one reference: https://en.wikipedia.org/wiki/Log_structured_filesystem https://en.wikipedia.org/wiki/Log_structured_filesystem
- jandrese 7y ago> it's theoretically possible to linearize a random write workload In fact OSes have been doing this for years now. Over a decade. There is a drawback however. To make this work you need to buffer your writes in a cache, typically in volatile memory, so they can be sorted before being written to the drive. The larger the cache the more improvement you see (although there are diminishing returns on this), but also the more data you lose in the event of power loss or kernel crash. So it is a tradeoff between speed and resilience. Interesting thought about how this changes for SSDs. While you don't have seek times to consider anymore, if you have two writes that happen to fall on the same block in the SSD it is a big win to combine them, so SSDs still want to buffer data and have to make the speed/resilience tradeoff.
- londons_explore 7y agoYou're talking about something else here. Linearized writes means write the data immediately, but rather than write the data to the 'correct' location on disk, just write the data immediately after the last bit of data you wrote. Then keep some accounting information elsewhere to map the real location of data to the place it would have been written had linearization not been done.
- jandrese 7y agoThat sounds awful from a fragmentation standpoint, but I guess it would be ok for write-mostly data. That metadata map would get pretty gnarly if you have a lot of interleaved writes though.