Is anyone clever enough to reinvent Ben's Method for improving disk performance?

Miscellaneous and Personal Stuff I Must Share
1

In the late 1980’s I came across a fun idea in the domain of disk storage design for computers. I’ll call it “Ben’s Method” because Ben was the inventor’s name. (Yes, it is a Method, not an Apparatus.) I thought “Aha!” when I first heard of the invention and wondered what leading questions I’d ask to guide a fellow computer buff to the joy of re-invention. To lay some context, I was myself an inventor, with dozens of U.S. patents (not even counting continuations-in-part). Though none of my patents were in the fields of disk storage or file system design, I had considerable experience therewith.

But road led onto road, and zig to zag, and here I am thirty years later, with the Method almost forgotten, wondering if any computer buff wants to enjoy the thrill of invention discovery. It would seem like a shame that this simple but “cute” method pass away completely unremembered.

But humor me please. When I heard of the invention, my reaction was “Could I have thought of that? What hints would someone need for that solution to pop into their mind?” If nobody takes up the challenge, fine — I’ll just let Ben’s Method pass into oblivion.

If you can detect that a large sequential file is gradually being read, aggregate performance may improve if you do “pre-caching” — if you speculatively read blocks from that large file that you expect to be requested since. Doing this when the disk is otherwise idle is trivial; a challenge arises when you must prioritize the pre-caching with other requests.

I’ll post yes/no answers if there’s interest in asking questions, but briefly: Ben’s Method was used in conjunction with pre-caching to improve net disk performance while simplifying firmware. (You don’t need to be a disk expert to grasp the Method — many computer nerds will know enough.)

AFAIK, Ben’s method was never implemented, never patented, never published, and is not generally known today. But I still wonder if, after all, the idea might have merit. (If you should apply the idea, please give credit to Ben!) Maybe the idea is flawed, but it’s still a nifty idea! And especially pleasing because of its utter simplicity. I posed this puzzle several months ago in the “53 bicycles: A lateral thinking puzzle” thread, but little progress was made. An SDMB disk expert answered

(As someone who was doing disk drive firmware forty years ago, I’d like to hear about some other mind-boggling methods! Post them in this thread if you wish. But RadioWave’s response only confirms that Ben’s Method is unknown.)

Hint: From one perspective, Ben’s Method is quite simple; so simple that some puzzlers might become disgruntled (“Is that all there is?”) It is that simplicity that makes the invention seem elegant to me.

Anyone want to challenge themselves? Ask a series of yes-no questions that will lead to a rediscovery of Ben’s clever invention.

2

All right, is it a scheme for choosing the physical layout of consecutive blocks of a file? For instance, staggering them on the track (or cylinder) so that they’ll pass the read head exactly when the controller is ready for them?

3

Yes! Though not that of you ‘for instance.’

4

I’ve done a lot of work on disk drivers and file systems, so I’ll be interested to hear what Ben’s method is. I don’t have time to play the guessing game though.

I once implemented a driver that used SSTF (Shortest Seek Time First) rather than the more common elevator algorithm. It was quite tricky because to be useful you have to know the actual time it will take to read a block, given the current position of the head and the rotational position of the platters. It’s not good enough to just estimate it based on the delta between the last block number and the requested one. This requires making a mathematical model of the disk including the number of platters, the layout of blocks across the platters, the number of sectors in each cylinder in each disk zone, the rotational speed of the disk, the time required to move the heads across N cylinders (including accelerating and decelerating the heads), etc. It was quite involved, but very interesting work (and it did make a big improvement in disk throughput).

5

Oh, and all this had to be deduced by doing test reads of selected blocks and observing how long each read took.

6

Does it work on SSDs or only spinning platters?

7

I’d thought of such things back in the 1980’s but rejected them as too complicated. Problems were generally more severe! :cool: For example, one major manufacturer of servers had gross driver bugs, and bugs in the interface to the seek “elevator” that led to huge performance degradation.

But it was precisely to avoid (at least in one case) the complexity of which you speak that Ben proposed his method.

I doubt it will be helpful on SSD’s (unless they’re similar to spinning platters) but am too unfamiliar to be sure. It might have been helpful on old CCD memories — are they still in use?

8

If you’re replying to me, the SSTF algorithm (and for that matter, the common elevator algorithm) is only relevant on spinning disks. In SSDs there is essentially no location-dependent overhead between reads, so these techniques are moot. At the time I did this work, all mass storage was spinning disks; SSDs did not exist yet.

9

Circa 1980 one company offered a high-speed big-box CCD replacement for disk and drum memories.* (Perhaps they sold very few of these boxes.) Does your work predate that?

    • I visited STC HQ circa 1980 in connection with their 4305, though I don’t remember details — it was some possible partnership between them and the company I was consulting for.
      .
10

I can’t think of any way you could read a disk faster than a single pass per track with sequential data, with the next data at a different platter of the same cylinder (repeat as needed) and next-next data at an adjacent cylinder. This would require an interleave of 0, so there would be one read pass per revolution per platter surface.

This can be done with a fast enough CPU and appropriate interface software. The only way to speed this up would be to increase the rotation speed, increase the number of heads that can be read simultaneously, or use a read-ahead buffer. If you are using a read-ahead RAM buffer, you need to take into account the time elapsed from the start of the entire read, or you are cheating to make the read speed look good.

Or maybe Ben’s plan was compressed data storage?

11

Suppose you have two discrete read requests pending on distant cylinders. You finish one read but you’ve somehow monitored activity enough to suspect that a read of neighboring data may be likely in the near future.

Do you read the speculative data, or part thereof, while you’re on that track, saving that data in a buffer? (Possibly thereby saving a future seek altogether.) Or do you hurry off to fulfill the existing request on a different cylinder?

With markn+'s method above you can calculate how much time you have until you need to initiate the seek, and get some speculative reads in “for free.” But in addition to the complexities markn+ mentions, you’ll have a slight quandary if a third unrelated request arrives while doing those speculative reads.

Ben’s method avoids these complexities.

12

The cache manager could give the firmware a wish list of sectors (or sector sequences) that it would like to read ahead. When the disk is busy, the firmware can return the sectors in question when the head happens to be on the right cylinder; when the disk becomes idle, it can seek and process whatever remains on the wish list.

13

SSDs are made of blocks (Like tracks. Like RAM.). You set up the block address, wait, then read the block. Which is why the random access speed of SSDs is not the same as the sequential access speed.

This is hidden because the integrated (ss) disk controller maps the actual disk sector address, but of course not totally hidden, because you can observe different random access and sequential access speeds.

(Then you normally read the block sequentially, so that’s like reading a sector.: it happens at bus speed, which is slower than memory speed, which is slower than cache speed)

14

@Melbourne, I haven’t worked with SSDs per se, but I’ve worked a lot with raw Flash (mostly NAND but some NOR; I designed a really cool filesystem for a NOR Flash system that I’m rather proud of). In the Flash controllers I’ve used, you set up the address and then read a whole block, as you say. Are you saying that in an SSD, after doing one block read, some blocks will be faster than others when you make the next request? That would be surprising to me based on my experience with Flash, but if it is true, then indeed there could be benefit in a nontrivial scheduling algorithm.

15

Don’t give up! The idea of Ben’s Method can be expressed in one simple sentence.
In may not be a good idea—after all, it’s never been implemented AFAIK, nor published, nor patented—but it does have a distinct “niftiness”!

Yes!! But you’ll need another sentence, or at least 2 or 3 key words, to Win the Brass Ring!

Again, here’s the problem Ben wanted to solve:

16

Is this somehow a Free Lunch effect, that will only improve performance, or does it improve average performance under certain assumptions that might not always hold?

The example of alternating between two long reads with a possible third read request that might come in while you’re busy optimizing those first two makes me think it has to be the latter. If so, what are the assumptions?

17

Is it anything to do with interleaving sectors or staggering the sectors on cylinders? Because both were well known when I was doing my IT degree in the late 80s.

18

You could stripe consecutive blocks of a file across different disk surfaces, but on the same sector. Block 1 of file A is at track 27, sector 33, disk surface 3. Block 2 of the same file is also at track 27, sector 33, but on disk surface 4, and so on. With an arrangement like this, if you have N heads, then up to N consecutive blocks are read in parallel by the controller, which can cache them if needed. The writing is a bit more complex than the usual scheme of filling each track serially.

(Isn’t this approach commonly used, though?)

19

Perhaps. Maybe this is part of the reason Ben’s method wasn’t enthusiastically adopted. :slight_smile:

To focus on the scenario for which Ben’s method may be optimal, imagine a disk kept busy concurrently reading two or more large sequential files (on different cylinders) in which the priorities are
(1) to respond quickly to the actual system requests, which come in quantum chunks; and
(2) to do anticipatory speculative reads without impacting priority (1).

~ ~ ~ ~ ~ ~ ~

AFAIK Ben’s Method has never been implemented nor published. Comments in the thread only confirm this.

20

Ben’s method was proposed for use with a Unix operating system. Some versions of the Unix file system issue their own anticipatory reads of sequential files, unbeknownst to and independent of, any “smarts” the disk controller may be attempting. Anticipatory reads at the disk controller level may supplement OR replace those kernel “pre-fetches.” Ben’s method is implemented at the disk controller level and may interact (sometimes unfavorably?) with kernel-initiated anticipatory reads.

“Quantum”? The applications issue read requests and then sleep until fulfillment. (Writes can be asynchronous or delayed, but not reads.)