5 ms·

A disk is a bunch of bits

61 points by dmazin 3y ago

omnicognate 3y ago
Nice article. I grew up when it wasn't really possible to be into computers and not have a visceral sense of this. Presumably nowadays it would be possible to get very far into programming (maybe into a career in it!) without practically encountering storage-as-bunch-of-bits, although surely people know that's what's there.
- JohnFen 3y ago
  > it would be possible to get very far into programming (maybe into a career in it!) without practically encountering storage-as-bunch-of-bits I increasingly meet devs who have no such knowledge (beyond a vague understanding). They sometimes don't even understand bitwise operations or when to use them and why. It completely boggles my mind.
  - gumby 3y ago
    I really hoped for the democratization of programming and now it's happened I sometimes have a WTF like that. But there's still a lot of call for programmers who understand the hardware and/or low-level protocols. We write the stuff the other people use to get their work done.
    - JohnFen 3y ago
      Oh, I agree. I don't think such devs are lesser in some way. They're just working at a high enough level of abstraction that such things aren't that relevant to what they're doing. The old fart in me does struggle to understand how people can learn to be devs without learning bit-level stuff, but that's just me noticing the strange new ways of a strange new world. And for devs like myself, who are happiest when working close to the metal, it's a professional advantage. As the pool of devs who know how to (and enjoy) twiddle bits shrinks, those of us who are left have more work and can command higher pay rates. The software industry is maturing and, like other industries that have matured, the people in it are increasingly specialists. My bit-twiddling ways are just a different specialty.
      - _1rth 3y ago
        I'm one of those new programmers. I'll sometimes do low level dev, but I don't use bitwise operations much. I guess I just don't recognise where they're useful. I'm always a bit awed when people chain a few for massive speedups. How can I learn?
        gumby 3y ago
        Read a lot of code and work with someone who does that kind of thing. Also you might want to brush up on math and algos: a lot of this "skill" is really just thinking about what the actual computation is. And that just comes from experience.
        JohnFen 3y ago
        Heh, that is probably more useful advice than the freaking essay I wrote in response.
        dmvdoug 3y ago
        False. Your freaking essay was a great read for me. But I’m not a developer/programmer, just a very interested outsider.
        JohnFen 3y ago
        I've been doing this from well before the internet was a thing, so I'm not actually familiar with good online resources to help. But I can give very general search suggestions. I tend to think of there being two classes of problems that are addressed at the bitwise level. The first is optimization and the second is hardware control. The techniques the two use are rather different. Optimization is a tricky topic, because you can't always get great gains there though bitwise operations, but when you can, the gains can be huge. This is because (for compiled languages) modern compilers tend to be very good at this sort of optimization and will do things in very efficient way to begin with. You taking the bits into your own hands aren't likely to improve on them. Also, there are processors where certain optimizations don't apply. For example, shifting a value one bit to the left is the same as multiplying by 2, and to the right is the same as dividing by 2. In many processors, the bit shift is much faster than the multiplication operation, so there's a win to be had there. In others, however, there is not such a huge speed difference. It all depends. In terms of hardware control, what you want to know is more obvious: what is the most efficient way to work with single or small groups of bits? What's the fastest way to count bits? That sort of thing. As an aside -- where I currently work, one of the interview problems is to have the applicant write code that counts how many bits are set in a word. Even high-level programmers will generally know how to do this -- but the method they use tells you a lot about the focus of their training and skillset. Bonus points if you can say why this is a useful thing to do, and what the Big O for your method is. In any case, I would suggest reading up on Boolean algebra to start to get a handle on this stuff. If you want to really wow people (at least ones who aren't graybeards), then a fun trick is to learn to model things (system states, whatever) as boolean networks (linking together AND, OR, XOR, etc. "gates" that result in a desired truth table), then use Karnaugh maps to reduce the network to the smallest possible number of components. I learned this as a way of reducing component counts in digital logic circuits, but I still find use for them to this day in purely software applications and often get called a wizard for being able to produce complex decision-making code that is very fast. The price you pay, of course, is that such code is not easy to follow for the poor souls who have to work with it later.
- toast0 3y ago
  It certainly is; my interview problem deals with bytes and optionally bits and I can't assume candidates have any knowledge of things at that level, because a lot of candidates don't. Kind of weird, IMHO, but not really a big deal, they can treat bytes as abstract constructs for the most part and go through the question well enough to show me if they can understand a problem described in words, figure out an output format and calculate example output given example input, and then write a program that does what they said it would do. The details of how bytes work can be explained on the way as needed.
- vba616 3y ago
  >I grew up when it wasn't really possible to be into computers and not have a visceral sense of this "A disk is a bunch of bits" doesn't seem to me like an accurate characterization of microcomputers at any time, really, in the last 50 years. I started to say that I think things got really complicated with SSDs, but spinning hard and floppy disks were never that simple either. I don't mean to nitpick, and I'm no expert, but I think the non-bit-array nature of storage had a lot of implications for users doing low level stuff - for example, copy protection sometimes exploited the hardware to try to make an uncopyable disc. Or if you were setting up partitions on a hard drive, you'd need to know about more than just "disk = bits". https://en.wikipedia.org/wiki/Cylinder-head-sector https://en.wikipedia.org/wiki/Cylinder-head-sector https://en.wikipedia.org/wiki/Logical_block_addressing https://en.wikipedia.org/wiki/Logical_block_addressing https://en.wikipedia.org/wiki/Modified_frequency_modulation https://en.wikipedia.org/wiki/Modified_frequency_modulation "Commodore's Amiga used an unusual format which got closer to the disk's raw (unformatted) capacity by eliminating the gaps between sectors and simplifying the identification data. This meant that individual sectors could not be rewritten; the Amiga would simply rewrite the entire track." https://en.wikipedia.org/wiki/Floppy_disk_format https://en.wikipedia.org/wiki/Floppy_disk_format I also remember that audio CDs, even though you could read them on a computer, were very, very much not bit arrays. Despite their vaunted "digital" nature, you couldn't rely on getting the same bitstream every time if you were ripping them to disk. https://en.wikipedia.org/wiki/Cdparanoia https://en.wikipedia.org/wiki/Cdparanoia
gumby 3y ago
These days SSD "disks" are just an array of bits. In the Old Days the disk driver had to know the physical geometry of the drive to optimise read/write head movement etc. Then the drive manufacturers made an array-like abstraction and did that work for you. Even today the SSD may remap your request for wear leveling and to avoid bad blocks, but they are so fast you can ignore that. (I wonder if the time delay due to remapping could be used as a covert channel? Probably not).
- tetha 3y ago
  > (I wonder if the time delay due to remapping could be used as a covert channel? Probably not). Ach darn. They invoked it. I guess now we need a name, a logo and a migration plan back to spinning rust over the next two weeks for security reasons.
- somat 3y ago
  It is not just the ssd, the pc bios had design problems in it's allocation for drive geometry (Cylinders, Heads, Sectors) and the first limit found was that it was unable to represent drives larger than about 500 Megabytes. Drives very quickly(early 90's) started lying about their geometry to get around this limit. There were various schemes of this and it finally ended up with abandoning physical(CHS) addresses entirely and just let the drive figure it out by moving to a flat address model(Logical Block Addressing), note that LBA mode was around long before SSD's http://www.steunebrink.info/bioslim.htm http://www.steunebrink.info/bioslim.htm
  - gumby 3y ago
    LBA was what I described as an “array-like abstraction”
anyfoo 3y ago
It's interesting to note that it wasn't always like that. IBM mainframes had a thing called "CKD", which stands for "count, key, data": https://en.wikipedia.org/wiki/Count_key_data https://en.wikipedia.org/wiki/Count_key_data In this scheme, you'd ask the hard disk[1] not for the bits/byte/word at a given position, but actually for a key associated with a record. The hardware would then give you the variable length record associated with that key back. Now you may argue, "yes, but the data on that disk/DASD was, on a low level, still an array of bits". And... well, sort of. I don't know the full details[2], but it looks like the records were separated similarly to how nowadays sectors are separated on modern (spinny) hard disks: By "gaps". Those are technically also bits, but they are recognized by lower level hardware and abstracted away from what reaches the "computer". Nowadays, CKD is still supported, but merely emulated on pretty boring commodity disks (sorry, "DASDs") that are addressed using sectors and tracks (or actually just sector number, since we started abstracting actual disk geometry away a few decades ago), arranged in a rigid sequential order. [1] Aside, IBM calls a hard disk "DASD": direct-access storage device. [2] The full details are here: https://web.archive.org/web/20200330172847/http://bitsavers.org/pdf/ibm/dasd/2314/A26-3599-4_2314_Sep69.pdf https://web.archive.org/web/20200330172847/http://bitsavers....
- tenebrisalietum 3y ago
  And here I am thinking KV drives were something new.
netsharc 3y ago
Then again, nowadays, what you read from /dev/sdd1 isn't necessarily the 1's and 0's stored on the memory cells, because many SSDs have encryption, and even if you haven't enabled the protection, there's still en/decryption keys on the controller. https://www.trentonsystems.com/blog/self-encrypting-drives https://www.trentonsystems.com/blog/self-encrypting-drives
- anyfoo 3y ago
  That's transparent though, and there always have been low level details which were abstracted away from what reaches the "computer". Spinny disks for example pretty much always had encoding (MFM, GCR...) that is private between the actual platter and the disk controller. You cannot have a long string of only 0 or 1 bits on a magnetic medium, so the encoding makes sure this does not happen. You have to draw the line somewhere, usually at the interface between "computer" and "disk controller" (or at what view the kernel presents to you), otherwise you may as well go down until you reach the quantum physics of it. In a sibling comment, I elaborated on IBM's "CKD" scheme, which was interesting in that regard because it did not present a sequential array of bits/bytes/words to the computer, so the usual "bunch of bits" point of view broke down in this particular case.
dmvdoug 3y ago
This is actually a superb introduction. My only criticism is that it mixes levels of expected knowledge when it jumps to C structs, but even that is helpfully explained. Very well done! [Edited to add: Good enough for me throw it into the ole NetNewsWire hopper.]
- dmazin 3y ago
  Thank you!
beeburrt 3y ago
So relieved to finally rule-out the flat elf theory
jiggawatts 3y ago
Yes, but... no. It's a "leaky abstraction" to think of a disk as a flat array of bits. For one, very few block devices are byte addressable! The hint is in the name. For example, if you change byte number 124567, then you're most likely actually reading a block of 512 bytes from offset 124416 to 124928, modifying it, and then writing it back. This matters a lot for concurrent access, locking, and database transaction log integrity. Many disks these days are layers upon layers of abstractions: they might be physically striped, deduplicated, compressed, shared, encrypted, or remote on a network somewhere. Performance is complicated as well. For example, SSDs have different performance-optimal block sizes for reads and writes. The shingled magnetic recording (SMR) hard drives are even more complex. Not to mention that disks can have block-level failures. It's possible for a disk to have a "hole" where it's a series of bytes... an error... and then a series of bytes. There are three values: "0", "1", and "bad sector"! Issues like this have caused a lot of software errors.
kalleboo 3y ago
I remember having that Eureka moment when I was a kid playing around with our Mac Classic. No modem so all you had to do was what was on your hard disk. And one of those things was Norton Utilities, which had a program called "Disk Editor". You could page through the sectors of the disk, one by one, and when there was some file-system-related data (HFS at the time) that it knew how to decode, you'd get a decoded view of it (WireShark-style) along with a pretty educational description of what it meant and was used for, which would also link file entries to the block where the file info was stored, etc. edit: since I couldn't find any online, I booted up the ol' PowerBook 540c and took some screenshots! https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_bootblocks.gif https://kalleboo.com/retrotech/software/norton_utilities/nor... https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_master_directory_block.gif https://kalleboo.com/retrotech/software/norton_utilities/nor... https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_extents_tree.gif https://kalleboo.com/retrotech/software/norton_utilities/nor... It also introduced me to trivia like how the names of developers were encoded into the file system, which felt like being let in on some secret https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_disk_type.gif https://kalleboo.com/retrotech/software/norton_utilities/nor...

61 points by dmazin 3y ago

Nice article. I grew up when it wasn't really possible to be into computers and not have a visceral sense of this. Presumably nowadays it would be possible to get very far into programming (maybe into a career in it!) without practically encountering storage-as-bunch-of-bits, although surely people know that's what's there.

JohnFen 3y ago
> it would be possible to get very far into programming (maybe into a career in it!) without practically encountering storage-as-bunch-of-bits I increasingly meet devs who have no such knowledge (beyond a vague understanding). They sometimes don't even understand bitwise operations or when to use them and why. It completely boggles my mind.
- gumby 3y ago
  I really hoped for the democratization of programming and now it's happened I sometimes have a WTF like that. But there's still a lot of call for programmers who understand the hardware and/or low-level protocols. We write the stuff the other people use to get their work done.
  - JohnFen 3y ago
    Oh, I agree. I don't think such devs are lesser in some way. They're just working at a high enough level of abstraction that such things aren't that relevant to what they're doing. The old fart in me does struggle to understand how people can learn to be devs without learning bit-level stuff, but that's just me noticing the strange new ways of a strange new world. And for devs like myself, who are happiest when working close to the metal, it's a professional advantage. As the pool of devs who know how to (and enjoy) twiddle bits shrinks, those of us who are left have more work and can command higher pay rates. The software industry is maturing and, like other industries that have matured, the people in it are increasingly specialists. My bit-twiddling ways are just a different specialty.
    - _1rth 3y ago
      I'm one of those new programmers. I'll sometimes do low level dev, but I don't use bitwise operations much. I guess I just don't recognise where they're useful. I'm always a bit awed when people chain a few for massive speedups. How can I learn?
      - gumby 3y ago
        Read a lot of code and work with someone who does that kind of thing. Also you might want to brush up on math and algos: a lot of this "skill" is really just thinking about what the actual computation is. And that just comes from experience.
        JohnFen 3y ago
        Heh, that is probably more useful advice than the freaking essay I wrote in response.
        dmvdoug 3y ago
        False. Your freaking essay was a great read for me. But I’m not a developer/programmer, just a very interested outsider.
      - JohnFen 3y ago
        I've been doing this from well before the internet was a thing, so I'm not actually familiar with good online resources to help. But I can give very general search suggestions. I tend to think of there being two classes of problems that are addressed at the bitwise level. The first is optimization and the second is hardware control. The techniques the two use are rather different. Optimization is a tricky topic, because you can't always get great gains there though bitwise operations, but when you can, the gains can be huge. This is because (for compiled languages) modern compilers tend to be very good at this sort of optimization and will do things in very efficient way to begin with. You taking the bits into your own hands aren't likely to improve on them. Also, there are processors where certain optimizations don't apply. For example, shifting a value one bit to the left is the same as multiplying by 2, and to the right is the same as dividing by 2. In many processors, the bit shift is much faster than the multiplication operation, so there's a win to be had there. In others, however, there is not such a huge speed difference. It all depends. In terms of hardware control, what you want to know is more obvious: what is the most efficient way to work with single or small groups of bits? What's the fastest way to count bits? That sort of thing. As an aside -- where I currently work, one of the interview problems is to have the applicant write code that counts how many bits are set in a word. Even high-level programmers will generally know how to do this -- but the method they use tells you a lot about the focus of their training and skillset. Bonus points if you can say why this is a useful thing to do, and what the Big O for your method is. In any case, I would suggest reading up on Boolean algebra to start to get a handle on this stuff. If you want to really wow people (at least ones who aren't graybeards), then a fun trick is to learn to model things (system states, whatever) as boolean networks (linking together AND, OR, XOR, etc. "gates" that result in a desired truth table), then use Karnaugh maps to reduce the network to the smallest possible number of components. I learned this as a way of reducing component counts in digital logic circuits, but I still find use for them to this day in purely software applications and often get called a wizard for being able to produce complex decision-making code that is very fast. The price you pay, of course, is that such code is not easy to follow for the poor souls who have to work with it later.
toast0 3y ago
It certainly is; my interview problem deals with bytes and optionally bits and I can't assume candidates have any knowledge of things at that level, because a lot of candidates don't. Kind of weird, IMHO, but not really a big deal, they can treat bytes as abstract constructs for the most part and go through the question well enough to show me if they can understand a problem described in words, figure out an output format and calculate example output given example input, and then write a program that does what they said it would do. The details of how bytes work can be explained on the way as needed.
vba616 3y ago
>I grew up when it wasn't really possible to be into computers and not have a visceral sense of this "A disk is a bunch of bits" doesn't seem to me like an accurate characterization of microcomputers at any time, really, in the last 50 years. I started to say that I think things got really complicated with SSDs, but spinning hard and floppy disks were never that simple either. I don't mean to nitpick, and I'm no expert, but I think the non-bit-array nature of storage had a lot of implications for users doing low level stuff - for example, copy protection sometimes exploited the hardware to try to make an uncopyable disc. Or if you were setting up partitions on a hard drive, you'd need to know about more than just "disk = bits". https://en.wikipedia.org/wiki/Cylinder-head-sector https://en.wikipedia.org/wiki/Cylinder-head-sector https://en.wikipedia.org/wiki/Logical_block_addressing https://en.wikipedia.org/wiki/Logical_block_addressing https://en.wikipedia.org/wiki/Modified_frequency_modulation https://en.wikipedia.org/wiki/Modified_frequency_modulation "Commodore's Amiga used an unusual format which got closer to the disk's raw (unformatted) capacity by eliminating the gaps between sectors and simplifying the identification data. This meant that individual sectors could not be rewritten; the Amiga would simply rewrite the entire track." https://en.wikipedia.org/wiki/Floppy_disk_format https://en.wikipedia.org/wiki/Floppy_disk_format I also remember that audio CDs, even though you could read them on a computer, were very, very much not bit arrays. Despite their vaunted "digital" nature, you couldn't rely on getting the same bitstream every time if you were ripping them to disk. https://en.wikipedia.org/wiki/Cdparanoia https://en.wikipedia.org/wiki/Cdparanoia

gumby 3y ago

These days SSD "disks" are just an array of bits. In the Old Days the disk driver had to know the physical geometry of the drive to optimise read/write head movement etc. Then the drive manufacturers made an array-like abstraction and did that work for you. Even today the SSD may remap your request for wear leveling and to avoid bad blocks, but they are so fast you can ignore that. (I wonder if the time delay due to remapping could be used as a covert channel? Probably not).

tetha 3y ago
> (I wonder if the time delay due to remapping could be used as a covert channel? Probably not). Ach darn. They invoked it. I guess now we need a name, a logo and a migration plan back to spinning rust over the next two weeks for security reasons.
somat 3y ago
It is not just the ssd, the pc bios had design problems in it's allocation for drive geometry (Cylinders, Heads, Sectors) and the first limit found was that it was unable to represent drives larger than about 500 Megabytes. Drives very quickly(early 90's) started lying about their geometry to get around this limit. There were various schemes of this and it finally ended up with abandoning physical(CHS) addresses entirely and just let the drive figure it out by moving to a flat address model(Logical Block Addressing), note that LBA mode was around long before SSD's http://www.steunebrink.info/bioslim.htm http://www.steunebrink.info/bioslim.htm
- gumby 3y ago
  LBA was what I described as an “array-like abstraction”

anyfoo 3y ago

It's interesting to note that it wasn't always like that. IBM mainframes had a thing called "CKD", which stands for "count, key, data": https://en.wikipedia.org/wiki/Count_key_data https://en.wikipedia.org/wiki/Count_key_data In this scheme, you'd ask the hard disk[1] not for the bits/byte/word at a given position, but actually for a key associated with a record. The hardware would then give you the variable length record associated with that key back. Now you may argue, "yes, but the data on that disk/DASD was, on a low level, still an array of bits". And... well, sort of. I don't know the full details[2], but it looks like the records were separated similarly to how nowadays sectors are separated on modern (spinny) hard disks: By "gaps". Those are technically also bits, but they are recognized by lower level hardware and abstracted away from what reaches the "computer". Nowadays, CKD is still supported, but merely emulated on pretty boring commodity disks (sorry, "DASDs") that are addressed using sectors and tracks (or actually just sector number, since we started abstracting actual disk geometry away a few decades ago), arranged in a rigid sequential order. [1] Aside, IBM calls a hard disk "DASD": direct-access storage device. [2] The full details are here: https://web.archive.org/web/20200330172847/http://bitsavers.org/pdf/ibm/dasd/2314/A26-3599-4_2314_Sep69.pdf https://web.archive.org/web/20200330172847/http://bitsavers....

tenebrisalietum 3y ago
And here I am thinking KV drives were something new.

netsharc 3y ago

Then again, nowadays, what you read from /dev/sdd1 isn't necessarily the 1's and 0's stored on the memory cells, because many SSDs have encryption, and even if you haven't enabled the protection, there's still en/decryption keys on the controller. https://www.trentonsystems.com/blog/self-encrypting-drives https://www.trentonsystems.com/blog/self-encrypting-drives

anyfoo 3y ago
That's transparent though, and there always have been low level details which were abstracted away from what reaches the "computer". Spinny disks for example pretty much always had encoding (MFM, GCR...) that is private between the actual platter and the disk controller. You cannot have a long string of only 0 or 1 bits on a magnetic medium, so the encoding makes sure this does not happen. You have to draw the line somewhere, usually at the interface between "computer" and "disk controller" (or at what view the kernel presents to you), otherwise you may as well go down until you reach the quantum physics of it. In a sibling comment, I elaborated on IBM's "CKD" scheme, which was interesting in that regard because it did not present a sequential array of bits/bytes/words to the computer, so the usual "bunch of bits" point of view broke down in this particular case.

dmvdoug 3y ago

This is actually a superb introduction. My only criticism is that it mixes levels of expected knowledge when it jumps to C structs, but even that is helpfully explained. Very well done! [Edited to add: Good enough for me throw it into the ole NetNewsWire hopper.]

dmazin 3y ago
Thank you!

beeburrt 3y ago

So relieved to finally rule-out the flat elf theory

jiggawatts 3y ago

Yes, but... no. It's a "leaky abstraction" to think of a disk as a flat array of bits. For one, very few block devices are byte addressable! The hint is in the name. For example, if you change byte number 124567, then you're most likely actually reading a block of 512 bytes from offset 124416 to 124928, modifying it, and then writing it back. This matters a lot for concurrent access, locking, and database transaction log integrity. Many disks these days are layers upon layers of abstractions: they might be physically striped, deduplicated, compressed, shared, encrypted, or remote on a network somewhere. Performance is complicated as well. For example, SSDs have different performance-optimal block sizes for reads and writes. The shingled magnetic recording (SMR) hard drives are even more complex. Not to mention that disks can have block-level failures. It's possible for a disk to have a "hole" where it's a series of bytes... an error... and then a series of bytes. There are three values: "0", "1", and "bad sector"! Issues like this have caused a lot of software errors.

kalleboo 3y ago

I remember having that Eureka moment when I was a kid playing around with our Mac Classic. No modem so all you had to do was what was on your hard disk. And one of those things was Norton Utilities, which had a program called "Disk Editor". You could page through the sectors of the disk, one by one, and when there was some file-system-related data (HFS at the time) that it knew how to decode, you'd get a decoded view of it (WireShark-style) along with a pretty educational description of what it meant and was used for, which would also link file entries to the block where the file info was stored, etc. edit: since I couldn't find any online, I booted up the ol' PowerBook 540c and took some screenshots! https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_bootblocks.gif https://kalleboo.com/retrotech/software/norton_utilities/nor... https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_master_directory_block.gif https://kalleboo.com/retrotech/software/norton_utilities/nor... https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_extents_tree.gif https://kalleboo.com/retrotech/software/norton_utilities/nor... It also introduced me to trivia like how the names of developers were encoded into the file system, which felt like being let in on some secret https://kalleboo.com/retrotech/software/norton_utilities/norton_disk_editor-HFS_disk_type.gif https://kalleboo.com/retrotech/software/norton_utilities/nor...