OTOH, I just realized that you can not add a zeroed-out drive to the array and maintain DP. When you go from N to N+1 disks, you go from N+1 diagonal stripes to N+2, and not just an additional sector added to the existing N+1 stripes.  I'd like to be proven wrong here.....

 

Start with a maximum number of disks -- a static N.  32?  64?   The unused "disks" are just zeros, until a disk is placed in its slot.  This way, the only time you need to rebuild DP is when unRaid increases the maximum number of disks it supports.

 

OTOH, I just realized that you can not add a zeroed-out drive to the array and maintain DP. When you go from N to N+1 disks, you go from N+1 diagonal stripes to N+2, and not just an additional sector added to the existing N+1 stripes.  I'd like to be proven wrong here.....

 

I still haven't quite been able to wrap my head around the paper yet, but the Usenix paper from the Net App folks talks about implementing expandable arrays.  Basically, it sounds like you just pick a fixed prime number large enough for the maximum number of drives you'd ever want to support, and you just pretend the unused drives are filled with 0s.  

 

However, I'm not really sure the dual-parity approach described in that paper could be used in unRAID.  NetApp must have patented it, right?

Start with a maximum number of disks -- a static N.  32?  64? 

 

I thought of that, and just using a fixed 32 stripes, which would allow for up to 31 data disks, but there was some reason that had a problem --- but I can't remember what it was now.  I was up really late last night 

OTOH, I just realized that you can not add a zeroed-out drive to the array and maintain DP. When you go from N to N+1 disks, you go from N+1 diagonal stripes to N+2, and not just an additional sector added to the existing N+1 stripes.  I'd like to be proven wrong here.....

 

Start with a maximum number of disks -- a static N.  32?  64?   The unused "disks" are just zeros, until a disk is placed in its slot.  This way, the only time you need to rebuild DP is when unRaid increases the maximum number of disks it supports.

 

That would work.   You just need to have a method to map that array of potential disks to the physical ones.

 

I also like the idea of a simple file on the flash drive for the mapping of the DP "slots" to the actual disks.

 

Joe L.

I also like the idea of a simple file on the flash drive for the mapping of the DP "slots" to the actual disks.

 

That will also allow you to reorder your disks (i.e. change their unRAID slot) while maintaining DP, just as you can with SP today.

However, I'm not really sure the dual-parity approach described in that paper could be used in unRAID.  NetApp must have patented it, right?

 

Algorithms and abstract ideas are not patentable thanks to the recent reforms and spelled out in the interim guidance for determing subject matter eligibility for process claims since the Bilski v Kappos case. http://inventivestep.files.wordpress.com/2010/07/75fr43922.pdf

I'm certainly no patent lawyer.  But I see NetApp has filed for lots of patents.  It looks like patent numbers 7,203,892 and 7,627,715 and 7,409,625 relate to Netapp's RAID-DP.  You can find a long list of patents by NetApp employee Peter Corbett, the lead author of the Usenix paper.

 

I tried reading the Patent Office's interim guidelines.  However, since I'm not a patent lawyer, my legal opinions are about as valid as the guy on the corner screaming about the Fed being unconstitutional!  Having said that, I'll give my opinion. 

 

Everything I know about the Bilski v. Kappos case, and the interim guidance from the Patent Office (which is, of course, very limited and highly questionable) suggests that there wasn't a major shift.  Business methods are still patentable.  Software is still patentable.  From what I understand, abstract ideas have never been patentable, nor have algorithms.

 

Yet algorithms have been patented.  The RSA encryption algorithm was patented, and was successfully enforced.  Certicom has patents for formulas that provide efficient means of computing elliptic curve operations, which have been successfully enforced.  A key point in those issues is that the algorithms being patented have a direct, practical use, which is spelled out in the patent application.  It's my understanding that you have been able to get patents in those cases.  While I'm certainly no legal genius, I didn't see anything in Bilski v. Kappos or the Patent Office's interim guidance that's going to change that.

 

NetApp's RAID-DP patents seem to fall in the same category.  It's not an abstract idea.  It gives a practical solution to a specific real-world problem.  The math used in the patent isn't some high-level, abstract mathematical concept- it's the solution to the real-world problem.

 

I know software patents are a shaky area of law for lots of reasons. As far as I can tell, none of NetApp's patents have been issued yet, and maybe they never will.  Maybe there's prior art.  I don't really know.  But this seems like a potentially dangerous road for a some company, with presumably no legal department, to go down.  If I was Tom I would want to be very, very careful.

 

 

 

 

According to a friend that's a patent attorney, as long as you can represent the algorithm as a mechanical process, you can patent it.

 

There are literally dozens of patents on every flavor of RAID, and they relate even farther back to ECC algorythms.  I'm dubious as to the enforceability of any RAID patents, when they add very little on top of the underlying prior art.  Simply tweaking prior art to solve a specific problem is not enough.

 

To check, I just did a Westlaw search and found no examples of any litigation over a RAID patent (did have to deal with a bunch of hits on "patent raids" where LEO conducted a raid for patent violations).  It seems to be a non-issue as far as any actual litigation goes.

Disclaimer: I am not a lawyer, just someone involved in the software industry.

 

There seems to be a shift towards revoking software patents, it all depends in how the next year or two goes. At least that's the feeling that portrayed by the commentary related to patent industry commentators (GrokLaw for instance).

 

From my limited understanding, particular software implementations of algorithms fall under Copyright protection and not under Patent protection. It's abuse of the system. Since DP is a mathematical algorithm, the mathematics of it is not patentable, leaving it free to be re-implemented by anyone else.

 

 

A little digging shows that one of the main grandfathers of all the RAID patents looks to be Ouchi's 1978 patent 4,092,732 ... which has long since expired.  It is obviously broad enough to apply to any ordering of the stripe (serial, diagonal, horizontal, multidimensional, etc.)

From my limited understanding, particular software implementations of algorithms fall under Copyright protection and not under Patent protection. It's abuse of the system. Since DP is a mathematical algorithm, the mathematics of it is not patentable, leaving it free to be re-implemented by anyone else.

 

Like you said, we'll see what the next few years bring.  But even the recent Supreme Court case and the interim guidance seem to come down on the side of software patents.  The guidance referenced the case law:

 

Bilski reaffirmed Diehr’s holding that ‘‘while an abstract idea, law of nature, or mathematical formula could not be patented, ‘an application of a law of nature or mathematical formula to a known structure or process may well be deserving of patent protection.’ ’’

 

So, I'd be awfully surprised to see some dramatic shift from what's been done.  Mathematical algorithms have been patented.  The Diffie-Hellman, RSA and Certicom patents are essentially only mathematical algorithms, put in the context of a cryptographic machine to explain what functionality they provide.  Companies have certainly been sued for re-implementing those algorithms in other products.  These types of patents have been very problematic in standards activities for network protocols, cryptography, audio/visual compression and playback, etc.

 

I think copyright protection is used to protect IP in cases where there are multiple implementations of solutions to a single, specific problem.  For example, you can't patent your RAID5 storage array, but you certainly have copyright protection on the code you write.  I think the idea is if the algorithm you describe in your patent lets you create a machine with new desirable properties, you can patent it. 

 

If there are a different set of mathematical algorithms that give you the same properties claimed in the RAID-DP patent, that might invalidate the patent.  But that's probably not the case.  I think that's one of the reasons that patent applications usually contain a large number of claims.

 

It certainly seems like Lime Tech implementing RAID-DP in unRAID would at least go against patent law as it is currently understood.  Maybe it will change, maybe not.  But in the meantime, you can't argue unRAID's implementation of RAID-DP is a different application of the mathematical formulas than the application described in NetApp's patents.  In both cases you're just talking about creating a storage device with dual-parity protection.

 

And really, from a philosophical perspective, I'd side with NetApp and the patents on this one.  If NetApp is going to invest research and development money toward creating a better way to add redundancy to storage devices, I think they deserve patent protection if they manage to come up with something that works.

A little digging shows that one of the main grandfathers of all the RAID patents looks to be Ouchi's 1978 patent 4,092,732 ... which has long since expired.  It is obviously broad enough to apply to any ordering of the stripe (serial, diagonal, horizontal, multidimensional, etc.)

 

Perhaps, but I doubt it.  Claim 10 of that patent says its creating a machine that lets you recover from one drive failure.  The actual contents of the patent gets pretty specific about how that is accomplished.  Among other claims, the machine described by NetApp lets you recover from two failures. 

 

The RAID-DP certainly builds upon the earlier RAID patent, which is, of course, cited in the NetApp applications.  Regardless of whether or not the courts would agree, I think it would be a mistake to say that RAID-DP isn't a significant enough step beyond RAID to deserve patent protection.  But you never know what would happen.  I really don't think the original creators of RAID had something like RAID-DP in mind.

Except that DP is not a unique mathematical solution.... you can order the disks many ways other than the "diagonal" implementation.  You can't patent RAID.  To the extent it was patentable, that patent has expired, as well as a bunch of others.  Multiple-parity RAID, and recovery from multiple-disk failures (to the extent it was patentable, given prior art) also dates back to the 1980s, and is long expired now.

 

At best, the specific implementation, to the extent it is not subsumed in prior art, may have merit.  But there are multiple implementations that can be used.  To the extent the patent is sought to be construed to apply to all implementations, that's where it fails.

 

With all the RAID implementations out there, you would expect to see plenty of litigation if patent holders felt they had legs  - but it hasn't happened.

Just because prior software patents have been granted does not mean they are valid. Unfortunately the costs to call for re-examination to invalidate existing patents is too costly and time prohibitive to be done. The future should not be built upon the sins of the past.

Like you said, we'll see what the next few years bring.  But even the recent Supreme Court case and the interim guidance seem to come down on the side of software patents.  The guidance referenced the case law

 

That may seem to be the case, but their guidance does not allow for broad implementations on abstract machines. The system must be particular. It can and will be argued that the general computer is such an abstract machine. That's the take away from the anti-software patent opinions.

bubbaQ-

 

With all the RAID implementations out there, you would expect to see plenty of litigation if patent holders felt they had legs  - but it hasn't happened.

 

Yes, there are lots of non-standard RAID implementations out there.  Has any company blatantly used another company's patented non-standard RAID implementation?  There are often some similarities, but as far as I know there are always important little differences.  Before I decided to go with unRAID, I was seriously considering getting a ReadyNAS.  It was a bit more expensive than some other alternatives, but I thought X-RAID2 was a very nice feature.  QNAP has expansion abilities too, but they don't go quite as far as X-RAID.  If there really aren't any IP issues, why hasn't Thecus or QNAP picked up X-RAID as a feature?

 

I don't understand why you don't think RAID-like devices are patentable anymore. Maybe you're right, but I don't understand your argument.  For something you be patentable you don't need a unique solution to a problem (using "unique" in the mathematical sense).  Diffie and Hellman came up with the idea of public key crypto before the RSA algorithm was created and patented.  We already has a working public key algorithm when elliptic curve cryptography was patented.  We're still seeing more patents from elliptic curve cryptography even though the basic idea isn't changing, but people are simply coming up with more computationally efficient algorithms for computing elliptic curve operations.

 

Now, if you're just suggesting that RAID-DP isn't necessarily the only answer to our dual-parity woes, then of course I agree.  I'm not trying to suggest that any dual-parity approach is encumbered by patents, and I'm certainly not saying any dual-parity approach is encumbered by NetApp's RAID-DP patents.  But the direction this discussion seemed to be taking was an implementation of the dual-parity scheme described in Corbett's Usenix paper, which is (probably) covered by the NetApp patents.  Or, at least, NetApp tried to cover that with their patents.  And that's what I'm saying appears to be very dangerous.  Lime Tech would at least want to get an opinion from a competent patent attorney before going down that route.

 

Brit-

Just because prior software patents have been granted does not mean they are valid. Unfortunately the costs to call for re-examination to invalidate existing patents is too costly and time prohibitive to be done. The future should not be built upon the sins of the past.

 

Sure.  And certainly what's considered patentable will change over time.  Maybe software patents will change.  But unless you saw something I missed in the case law or the Patent Office guidance (you know, since we're both established experts in patent law  ), I didn't see anything specific suggesting a major change is in the works.  I brought up the RSA and Certicom patents because those are fairly well-known patents that have been extensively challenged in court.  Those aren't patents that flew under the radar of patent examiners and managed to sneak through when they shouldn't have.  That doesn't necessarily mean that those patents would fly now, but it seems like the USPO is handing out software patents now more than ever.

 

That may seem to be the case' date=' but their guidance does not allow for broad implementations on abstract machines. The system must be particular. It can and will be argued that the general computer is such an abstract machine. That's the take away from the anti-software patent opinions.[/quote']

 

That's been a longstanding argument, and the Supreme Court apparently intentionally avoided that subject.  Maybe those will eventually be struck down.  I think its a bad idea, but it could happen.  But if anyone successfully challenges those types of patents in court, its almost certainly going to be buy a well-funded corporation, or maybe a group like EFF, with an army of lawyers. 

 

Even so, I'm not sure that would even pose a problem for the NetApp patents.  Those patents aren't written like the machine is a general purpose computer.  Sure, in practice you'd implement the machine using something roughly equivalent to a general purpose computer, but the patent applications talk about a storage array.

 

Now, if you're just suggesting that RAID-DP isn't necessarily the only answer to our dual-parity woes, then of course I agree.  I'm not trying to suggest that any dual-parity approach is encumbered by patents, and I'm certainly not saying any dual-parity approach is encumbered by NetApp's RAID-DP patents.

 

That's my point.  The lesson of Bilski is that software patent holders can't have it both ways.  If the try to make it broad to cover other implementation algorithms, they will fail. I do not believe NA's patent is specific enough, or sufficiently inventive given prior art.

 

The patent battles in pharma have also resulted in recognizing that you can use patented methodologies in R&D, as part of a course to develop alternatives not covered by the existing IP.  Like studying RSA's algorithm, and even using it in your internal R&D code, while you develop a drop-in replacement for it that you then take to market.

 

 

I'm guessing that if you look hard enough, you'll probably find that unRaid, with it's use of RP to protect multiple disks of varying sizes, is likely already violating an existing patent.

 

I don't think the patents are a good enough reason to hold off implementation of RDP.

 

I'm guessing that if you look hard enough, you'll probably find that unRaid, with it's use of RP to protect multiple disks of varying sizes, is likely already violating an existing patent.

 

I don't think the patents are a good enough reason to hold off implementation of RDP.

 

my my, all this FUD over patents. The bottom line is that Limetech charges money for emhttp and shfs, which don't violate any RAID patents. Limetech won't have any problems if they do not charge $$ for DP.

 

the md driver is GPL'ed. anyone can modify the source and post a DP version. anyone can use a DP version, even if it violates patents. NetApp or EMC (or any RAID patent holder) can try to enforce their patents, and at best they will get a Cease&Decist order against any company trying to make money from either selling DP, or marketting a service/product based on DP (eg, providing a storage cloud service).  for the vast majority of unRAID users, i don't think NetApp/EMC/etc is going to take you to court.

 

there is a separate issue about how such code can be freely distributed... eg, Ubuntu excludes commercially-controversial code from their distribution, but you can add it yourself after installation.

 

back to tech talk, bubbaQ, I really love our dialog going on. thanks for the great feedback on pros and cons, it's certainly got me thinking.  i was looking through md.c and unraid.c last night, getting a feel for how much work it's going to be to add DP or RP. i still don't know the answer, but it will certainly become more apparent when i start recoding. the other issues we've discussed are also important and i'm glad we are exposing them early.

 

btw, is anyone willing to help test very early implementations of RP or DP? it most certainly won't be reliable, so it should only be done on a spare system. i happen to have a spare system right now (Acer h342 is my main unRAID box, while an h341 is my experimental platform). but i will need lots of testers, with a variety of disk configurations etc.

 

Guy

I have some algorithm ideas, but they depend on modulo function, and I'm still looking for an answer on the cost of the modulo function as compared to other math ops on x86 using gcc.

 

Assume you want to reserve up to 30 data drives, then the SP is included in the DP, so DP uses 31 drives, and thus has 32 stripes.

 

Using (X+driveID)%32 is a nice way to determine which of the 32 stripe patterns applies to a sector.

 

Or you can just use the lower 4 bits of X, add the driveID, and ignore overflow (probably faster).

 

Where S = the stripe pattern (0 to 31) determined by (X+driveID)%32, you can also have S represent the disk that is left out of the DP.

 

So if you are reading sector 1000 on disk3, DP will use stripe pattern 11, and disk11 would be the disk left out of the DP.

 

You would use sector 999 on disk2, sector 998 on disk1, sector 997 on parity... 1001 on disk4, 1002 on disk5, etc.... and substitute 0's for disk11.

 

The sector to write it to on the DP is also easy, X & FFFFFFF0 +S  (upper 28 bits of X + S)

 

 

I have some algorithm ideas, but they depend on modulo function, and I'm still looking for an answer on the cost of the modulo function as compared to other math ops on x86 using gcc.

 

I can't speak authoritatively, since I haven't investigated this myself, but I wouldn't worry about it:

a) sector calcs are done infrequently; the overhead of data transfer and vastly exceeds it

b) modulo should be pretty fast on most CPUs (even Atom-class CPUs)

c) gcc should strength-reduce modulo if it has a faster version; keeping one operand a constant (not variable) helps

 

Guy

modulo should be pretty fast on most CPUs (even Atom-class CPUs)

 

I wouldn't bet on it... modulo may use division except in certain optimum conditions.  It certainly is slower than ANDing a long int.... the question is how much slower.

 

If you set the number of stripes to 32, both the modulo and the floor division results are simple and operations.

 

I generally don't like doing bit operations unless they really save cycles... they can make code harder to read.  But since it avoids potentially two division operations, that could be a significant savings.

 

 

I think modulo is likely to be slow.  Like bubbq said, a modulo might just integer division.  I've heard integer division can take somewhere around 40 cycles, but that's probably the worst case on an older processor.  I think newer CPUs do faster integer divisions.  And I think its also been dependent on the dividend and divisor.  For small numbers it should be a lot faster.  Still, it's got to be a much slower operation than an XOR, AND, ROTATE and even an ADD.  I suspect bit operations will save a lot of cycles.

 

You could just try it out and have it count the cycles.

I have an Intel i3 530 and Atom D510 CPU I can run benchmark Linux C code on, should anyone come up with any to help provide numerical data points.