Google Linux servers hit with $5m patent infringement verdict (The Register)

There's some big oil companies there, but they're drilling elsewhere. I believe the biggest find by far in the US (in recent years), is the Bakken formation in Montana. Last assessment was about 22 billion barrels of oil (2008 USGS survey) - but only about 3-5 billion are recoverable. And yes, this is mostly from the last New Yorker.

But Wikipedia seems to agree:
http://en.wikipedia.org/wiki/Oil_reserves_in_the_United_S...

So,yah, bye bye Texas :)

Even better - with no say in our government, we could finally actually tax the oil companies, via tariffs, all the drilling they do elsewhere, etc.

You've never been to Texas, have you?

For people that are native residents being Texan is a often a extreme point in pride. They, quite literally, believe that they are the best people in the world. They will take it as a personal insult if you ask them if they are from Texas or not... and will actually get upset about it. You should know instinctively!

But really, Texas does kick ass in a lot of ways. I would actually be very happy to live there. It really is better then most other states.

The patent issue, however, is a federal issue. Not state. Since USA law is based a lot on case precedent it's often quite a bit by accident what jurisdictions are more patent-friendly or not.

> I am really disgusted how there seems to be more and more of a free for all in blatant anti US bigottism displayed here on LWN. I don't care that it is against the US, I am just annoyed at how ugly the behavior is and how people seem to think ugly behavior is OK for some reason if directed against some US entity.

They are ignorant. That is what makes them bigoted. They don't realize that the USA is a easy scapegoat that their media and governments use to divert attention away from their own shit policies and bad decisions. They don't realize that most of their civilization for the past 60 years has been prompt up by American-style capitalism.

They also don't realize that USA government != USA people. Also states are separate entities from the federal government. Our two-party system is a pile of shit and we are paying the price for it with our failing economy. They don't understand that the people that are resentful and irritated at the USA government are the ones fighting against the badness that USA produces in the world.

One of the these days thy will start to fully realize that the only reason our government's bad decisions are hurting them so much is because their economies and governments have become so utterly dependent on USA.
They know this partially already and it burns. It's natural that this dependencies lead to resentment.

The essential claims in the patent are very specific about the situation in which they arise.

With regard to other observations about what is obvious or not, nothing we say here will impact the validity of the patent.

Google attempted to convince a jury that the patent was invalid and failed. I don't know what their argument was and whether they had any prior art to offer.

Google also failed to convince the jury that the patent was not being infringed, valid or not. They would have had to parade out the code and experts to explain it to accomplish that. Don't know how they failed at that either.

Now, we know that there appear to be some jurisdictions in Texas that are very friendly to patent-infringement suits. (This is where Microsoft ran up against i4i, for example.) But even so, it is not clear, based on the experience of others, that there is much room in the appeal process to over-rule the jury's findings of fact.

Whatever Google and other defendants end up paying, the only thing that will keep Linux as unencumbered FOSS is if the alleged infringement is cured by working around the essential claims of the patent so there is no infringement. If the patent were to be over-turned, put the code back if it is appropriate. Otherwise, just move on, I say.

I am far more concerned about Linux staying unfettered than I am about Google's pocketbook.

I want to re-implement a pick-style datastore, actually, and storing time stamps and expiring data was something I planned to do - I thought it was blatantly obvious! However, I would have done it as part of writing a record, because that's an obvious point at which to compact a bucket.

The original Pick model didn't include disk storage, it viewed it as a permanent virtual memory, and everything was based on hashed files, including RAM! This goes back to about 1967 - Pick is pretty much the same age as Unix :-)

Going forward to Prime INFORMATION, that had 2k buckets which can easily hold several records, depending on how big they are (stuff that was large than - by default - 1600 bytes got pushed to a secondary store). So, every time I add a record to a bucket, it's possible - even probable - that I need to compact the bucket to make room inside the 2k. (Deleting records, I would probably just flag them - not worth compacting them at that point.)

As for your surprise at the way of handling overflow buckets, you're thinking in terms of memory. And you badly misunderstand the hashing technique if you think expanding buckets will avoid collisions! :-) In a Prime Technical Paper I've got, they give the example of "number of buckets equals number of records", record id is sequential unique, BUT they add the records from 0 to 16 in random order. So at the end, with 17 records in seventeen buckets, there are no collisions. But if let's say the first two records to be added are both odd, 1 and 3 for example, they will both hash to bucket 1, and bucket 0 will be empty.

Linear hashing doesn't guarantee your file won't be lumpy. But the maths I've seen says that - absent a pathological situation - given a known key you need to access on average less than 1.05 buckets to find your record (or, more importantly, to know that it doesn't exist!) If every bucket access is a disk read, then that's damn fast! I don't know of any non-hashing technique that can come close. That's why, for pretty much ALL database sizes, a Pick system will leave pretty much any other database in the dust for speed.

My favourite war story is the company that ported their database from UniVerse (a Pick derivative) to Oracle. The Oracle consultants, after spending six months tweaking a particularly nasty SQL query, proudly announced to management that their new system was now ten percent faster than the system they were replacing. Unfortunately, they did it within earshot of the guy maintaining the old system, who scornfully responded "you're proud that your twin Xeon 800 is only 10% faster than my Pentium 90?" !!!

And that speed discrepancy is typical. I've seen loads of comments from people who can't believe how fast Pick systems are. We ran 32 users on a MIPS 3000 (equivalent to a 386) with 16Mb of RAM. System response was pretty good, although I don't think we hammered the system the way some people did. And watching the hard disk light, that machine was thrashing like mad ... !!! (Management didn't want to pay for a ram upgrade - until a ram chip failed and I wangled an upgrade with the support people :-)

Cheers,
Wol

The load factor definition I use has to do with the average number of keys that have the same hash in the set of possible hashes (actually, same buckets).

I should clarify what I mean by same-hash. Typically, the adjustable bucket function that works with linear hashing is something like

bf(key,level) = hash(key) mod (N*2^level)

where N is the minimum (starting) number of buckets and level is initially 0.

Once splitting starts, there are at any time at most two of these functions being used.

Let M (not less than N-1) be the highest number of the buckets currently in use and let let N*2^level be the least integer greater than M.

Then the rule for finding the correct bucket is,

bucket(key,level) = if bf(key,level) > M then bf(key,level-1) else bf(key,level)

Note that for the pathological case, I had hash(key) be what was constant. It doesn't matter what constant, but 0 is easiest to visualize.

In the simplest linked-list in-memory case, a buck holds one record directly (in the head entry of the linked list) and anything else is linked from that. An empty bucket has some sort of special NULL entry so it can be distinguished for a bucket holding onto one record. Note that if N is a power of 2, the bucket(key, level) algorithm becomes very simple since masking can be used instead of division but there needs to be more attention to the quality of hash(key). I prefer that case because masking can be used to dramatically speed up the entire process of getting to a specific bucket through whatever the bucket director structure is.

If we are talking about disk spill, and on-disk buckets, the overflow case is different and different load factor values are more important. For example, one would like to know the average number of disk blocks taken for buckets corresponding to the same hash, on the assumption that one wants to minimize the number of buckets with overflows to the point where the extra hit has a negligible impact on performance. I imagine for tuning purposes, the load factor as I described it also matters because it gives a clue as to how much empty space is carried in the first/primary disk block of a bucket, since having too many disk blocks that are nearly empty has its own performance consequences. It looks like these load factors (being estimates) are derivable from each other assuming primary and overflow blocks are all of the same size.

We've wandered a distance from workarounds for '120, which I think are more-easily handled without going to linear hashing if it is not already being used in the Linux kernel code that infringes an essential claim. Thanks for the exploration though.

I got tired looking through it, and I don't think one can find actual exhibits or expert testimony.

What is interesting is that some of these companies have extensive web farms for their own operations. We know that Google's uses Linux. I presume these other users do also.

It is interesting that hosting services are included. I assume because they are engaging in commerce by leasing the use of LAMP-based hosted sites, etc. So my hosting service could easily make it onto this list, not to mention sites where I am an user (Facebook, amazon.com, etc.). Ick.

I suppose free cloud services (E.g., my Amazon Cloud Drive) may not be very free for long. And we all wait patiently to learn there has been a workaround that removes the infringing code from the Linux kernel.

I'm not very adept at analyzing patent claims; e.g. means-plus-function and anticipation, both of which I would guess were fairly critical to this case.