Take the 2-minute tour ×
Ask Patents is a question and answer site for people interested in improving and participating in the patent system. It's 100% free, no registration required.

Reading this patent application it looks apparent that it is just rewriting log-structured-raid-arrays in some other words.

Log structured raid arrays were described in August 1995's conference about High Performance Distributed Computing. This PDF requires subscription (or you can just purchase that single copy). Please note that this paper also discusses compressing the data that it is not part of the patent.

Later it was published in books - look for chapter 4 in High Performance Mass Storage and Parallel I/O: Technology and Applications, edited by Hai Jin, Toni Cortes, and Rajkumar Buyya, IEEE Press and Wiley, 2001 - you can find the table of contents in the Amazon's "look inside". There is also a presentation from a course taught on the book at the university of Arkensas on 2002. The presentation does not describe all the details, but still a free material from over 10 years ago describing the invention.

Finally, the system is also described at US7055058 with slightly different terms.

The main difference in describing the system lies in the distinction of how to "garbage collect" the best available next stripe. In this algorithm, the write process starts with finding the stripe with the highest number of available blocks, and in the publications and previous granted patent there is a background process that finds the most empty block, reads the valid data into the cache, and then just writes into empty stripes. This is just a minor modification to the algorithm (combining two operations to a single operation in the new application) and not a novel invention.

The vast majority of the claims (and especially claims 1,2,13,14,26 that are the base for the rest) in the patent can be found from the following citations from the paper. Reading the full paper, of course, provides a much better understanding.

"The implication is that we can no longer have fixed, static locations for all the data. This, in turn, implies that the subsystem must keep a directory which it uses to locate data items in the subsystem." ...

... "Compressed records are stored in the controller cache. We assume a Non-Volatile cache and the use of Fast Write (as for RAID-5). When the record needs to be destaged, it is written along with other records of the same logical track." ...

... "One of the segment-columns of a segment contains the parity (XOR) of the remaining segment-columns of the segment. For performance reasons, the parity segment-columns are not all on the same disk, but are rotated among the disks." ...

... "The location of a logical track in an LSA changes over time A directory, called the LSA directory, indicates the current location of each logical track. The entire LSA directory is maintained in NVS in the disk controller, to avoid disk accesses when searching the directory" ...

... "However, LSA needs to do a process called garbage collection, since holes (garbage) form in segments that previously contained one or more of the logical tracks that were just written. To ensure that we always have an empty segment to write to, the controller garbage collects segments in the background. It selects for garbage collection those segments that have lots of holes (garbage) and/or those segments which are not anticipated to produce more holes for a long time. All logical tracks from a segment selected for garbage collection that are still in that segment (are still pointed to by the LSA directory) are read from disk and placed in a memory segment."

What do you think?

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.