Patent issues and 8.1

On Tue, 25 Jan 2005, Bruce Momjian wrote:

pgman wrote:

Not yet --- I suggested it but didn't get any yeas or nays. I don't
feel this is solely core's decision anyway ... what do the assembled
hackers think?

I am not in favor of adjusting the 8.1 release based solely on this
patent issue. I think the probability of the patent being accepted and
enforced against anyone using PostgreSQL to be very unlikely. I would
also like to come up with a procedure that would scale to any other
patent problems we might have. What if someone finds another patent
problem during 8.1 beta? Do we shorten the 8.2 development cycle too?

What I would like to do is to pledge that we will put out an 8.0.X to
address any patent conflict experienced by our users. This would
include ARC or anything else. This way we don't focus just on ARC but
have a plan for any patent issues that appear, and we don't have to
adjust our development cycle until an actual threat appears.

One advantage we have is that we can easily adjust our code to work
around patented code by just installing a new binary. (Patents that
affect our storage format would be more difficult. A fix would have to
perhaps rewrite the on-disk data.)

One problem in working around the GIF format patent is that you had to
create a file that was readable by many of the existing GIF readers.
With PostgreSQL, only we read our own data files so we can more easily
make adjustments to avoid patents.

I did not see any reaction to my ideas above. Is this a good plan?

No, as an 8.0.x is mean to be for minor changes/fixes/improvements ...
'addressing a patnt conflict', at least in ARC's case, is a major change,
which is why we are looking at a short dev cycle for 8.1 ...

----
Marc G. Fournier Hub.Org Networking Services (http://www.hub.org)
Email: scrappy@hub.org Yahoo!: yscrappy ICQ: 7615664

Marc G. Fournier wrote:

One problem in working around the GIF format patent is that you had to
create a file that was readable by many of the existing GIF readers.
With PostgreSQL, only we read our own data files so we can more easily
make adjustments to avoid patents.

I did not see any reaction to my ideas above. Is this a good plan?

No, as an 8.0.x is mean to be for minor changes/fixes/improvements ...
'addressing a patnt conflict', at least in ARC's case, is a major change,
which is why we are looking at a short dev cycle for 8.1 ...

So if we have to address it we call it 8.0.7 or something. My point is
that we don't need to address it until we actually find out the patent
is being enforced against someone, and that possibility is quite unlikely.

By changing our development cycle just on the threat of a problem we are
basically saying any patent holder can hinder PostgreSQL development by
suggesting there is a patent problem but not actually doing anything
that will give them bad press. The threat of bad press might be the
only thing that is prevents us from being attacked by patents.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

On Tue, 25 Jan 2005, Bruce Momjian wrote:

Marc G. Fournier wrote:

One problem in working around the GIF format patent is that you had to
create a file that was readable by many of the existing GIF readers.
With PostgreSQL, only we read our own data files so we can more easily
make adjustments to avoid patents.

I did not see any reaction to my ideas above. Is this a good plan?

No, as an 8.0.x is mean to be for minor changes/fixes/improvements ...
'addressing a patnt conflict', at least in ARC's case, is a major change,
which is why we are looking at a short dev cycle for 8.1 ...

So if we have to address it we call it 8.0.7 or something. My point is
that we don't need to address it until we actually find out the patent
is being enforced against someone, and that possibility is quite unlikely.

Ah, so you are advocating waiting *until* the problem exists, even *after*
we know a) there may be a problem and b) we know that we can fix it ... ?

----
Marc G. Fournier Hub.Org Networking Services (http://www.hub.org)
Email: scrappy@hub.org Yahoo!: yscrappy ICQ: 7615664

Bruce Momjian wrote:

So if we have to address it we call it 8.0.7 or something. My point is
that we don't need to address it until we actually find out the patent
is being enforced against someone, and that possibility is quite unlikely.

IMHO, the patent issue is *not* a "potential problem" for a lot of
people, it *is* a problem -- it makes people uncomfortable to be
deploying software that they know might cause them legal headaches down
the line. It also makes life difficult for people distributing
commercial versions of PostgreSQL.

I've posted a patch to -patches that replaces ARC with LRU. The patch is
stable -- I'll post some code cleanup for it tomorrow, but I've yet to
find any bugs despite a fair bit of testing. The patch also reverts the
code to being quite close to 7.4, which is another reason to have some
confidence in its correctness.

I think the best solution is to replace ARC with LRU in 8.0.1 or 8.0.2,
and develop a better replacement policy during the 8.1 development cycle.

-Neil

Neil Conway <neilc@samurai.com> writes:

I've posted a patch to -patches that replaces ARC with LRU. The patch is
stable -- I'll post some code cleanup for it tomorrow, but I've yet to
find any bugs despite a fair bit of testing. The patch also reverts the
code to being quite close to 7.4, which is another reason to have some
confidence in its correctness.

I've already pointed out a couple reasons why I don't have any
confidence in its correctness. This may be the right path to go for
8.0.* ... but we must NOT suppose that we can just push it out without
a full beta test cycle.

regards, tom lane

Tom Lane wrote:

I've already pointed out a couple reasons why I don't have any
confidence in its correctness.

Well, you've suggested that I should try and reduce the API churn caused
by the patch. As I said on -patches, I don't really see this as an issue
if we just apply the patch to REL8_0_STABLE. You never replied to my
-patches mail -- AFAIK that's where the issue stands.

I think the biggest area of concern with the LRU patch is how it changes
bgwriter behavior. To review, the bgwriter currently does the following
each time it is invoked:

(1) acquire BufMgrLock
(2) sweep through the entire buffer pool in LRU order, adding dirty
pages to a list
(3) examine a subset of the computed list according to bgwriter_maxpages
and bgwriter_percent
(4) for each element in the subset:
(a) drop BufMgrLock
(b) flush page to disk
(c) reacquire BufMgrLock

This is tricky to implement with LRU; we only record the recency of last
access for unpinned pages, so we can't get the list in #2 (we can either
get all dirty pages, as required for checkpoint, or all the unpinned
dirty pages in LRU order). Besides which, the ARC behavior has some
issues that were raised prior to the 8.0 release: scanning the whole
buffer pool with the BufMgrLock held is bad.

So the LRU patch changes the bgwriter to:

(1) acquire the BufMgrLock
(2) sweep through the free list (the list of unpinned buffers) in LRU
order, adding up to bgwriter_maxpages dirty pages to the list
3) for each element in the list, write it out as in #4 above

That means we don't hold the BufMgrLock for as long and the bgwriter
doesn't consider flushing pinned pages (both a good idea IMHO), but it
also means there's no consideration of bgwriter_percent. I'm not at all
sure that this is the best compromise, however, so some comments would
be welcome.

Perhaps it would be best to keep bgwriter_percent, but redefine it to
mean "the % of the buffer pool scanned by the bgwriter, at most." (I
think this was Simon's idea originally.)

This may be the right path to go for
8.0.* ... but we must NOT suppose that we can just push it out without
a full beta test cycle.

Yeah, I think a beta period would be a good idea (not nearly as long as
the 8.0 beta period was, though).

I think it would be better to have a few weeks of beta prior to 8.0.2
and resolve the problem here and now, rather than crippling the 8.1
cycle (as the no-initdb policy would) or waiting for the problem to
*really* become serious (as the "no action needed now" policy would).

-Neil

Neil Conway wrote:

IMHO, the patent issue is *not* a "potential problem" for a lot of people,
it *is* a problem -- it makes people uncomfortable to be deploying
software that they know might cause them legal headaches down the line. It
also makes life difficult for people distributing commercial versions of
PostgreSQL.

I live in Europe, and right now, the patent, if granted, would not have any
effect on me. Even if Europe will have patents on software, I doubt that
this ARC algorithm will be patentable in Europe.

I've posted a patch to -patches that replaces ARC with LRU. The patch is
stable -- I'll post some code cleanup for it tomorrow, but I've yet to
find any bugs despite a fair bit of testing. The patch also reverts the
code to being quite close to 7.4, which is another reason to have some
confidence in its correctness.

I think the best solution is to replace ARC with LRU in 8.0.1 or 8.0.2,
and develop a better replacement policy during the 8.1 development cycle.

I have not much confidence in such changes in a minor release, seeing that
there is really not much more testing on them than regression testing (am I
wrong?) an perhaps simple benchmarking in this case. I believe many really
annoying or dangerous bugs have only been found in field testing.

Don't get me wrong, Neil, I trust your coding skills. But replacing ARC with
LRU seems a rather big change, which could introduce new bugs and have
performance issues. And the change also effects bgwriter behaviour.

Please don't rush out untested core components, and perhaps think about the
people who are quite comfortable with ARC (e.g. us guys in Europe over
here).

If ARC replacement can be done in a 8.0.* release, it doesn't have to be now
in a rush, does it?

Best Regards,
Michael Paesold

Ühel kenal päeval (kolmapäev, 26. jaanuar 2005, 15:38+1100), kirjutas
Neil Conway:

Bruce Momjian wrote:

So if we have to address it we call it 8.0.7 or something. My point is
that we don't need to address it until we actually find out the patent
is being enforced against someone, and that possibility is quite unlikely.

IMHO, the patent issue is *not* a "potential problem" for a lot of
people, it *is* a problem -- it makes people uncomfortable to be
deploying software that they know might cause them legal headaches down
the line.

If people see we are scared by so little, I fear that someone will pop
up another "potential patent problem" just after we have reverted to
LRU. Or even better - a day or two before releasing 8.0.x withr RLU fix.

It also makes life difficult for people distributing
commercial versions of PostgreSQL.

Simple repackaging should not be a basis of "commercial" version. If
they want it, they could

a) distribute OSS version and sell support

b) test your LRU backpatch and sell (a likely worse performing) version
with that.

c) implement a better-than-ARC cache replacement scheme, and sell that.
If they are really pissed off at PGDG they could even apply for a patent
to that scheme and gain "competitive advantage" in their investors eyes.

I've posted a patch to -patches that replaces ARC with LRU. The patch is
stable -- I'll post some code cleanup for it tomorrow, but I've yet to
find any bugs despite a fair bit of testing.

Have you done any performance comparisons with your LRU patch our 8.0
PgARC implementation.

IIRC the differences between 7.4 and 8.0 were best visible on really
heavy workloads, like the ones tested at OSDL.

If the performance does not matter, the simplest solution would be
setting postgres internal cache to 0 bytes and rely just on OS buffers.
That stops infringement immediately as one is not *using* any patented
technologies then.

I think the best solution is to replace ARC with LRU in 8.0.1 or 8.0.2,
and develop a better replacement policy during the 8.1 development cycle.

That could be the best solution for those worried about it (commercial
distributors mainly) but for the others a better tested and stable ARC-
like solution we have implemented and tested now is probably still
better.

AN UNRELATED SUGGESTION:

Could anybody take the patent application and comment it claim-by-claim
marking up things having prior art (like claim 1 - keeping two lists),
so that when we start designing our ARC replacement, we know what points
we can safely "infringe" (IIRC some points involved doing LRU-like
stuff, so if we decide to be unconditionally terrified by the patent
application we should avoid LRU as well).

Then we could put up the commented version on our website or perhaps
havet it up at http://www.groklaw.net/ for comments from larger
community already familiar with IP issues ;).

Slashdot would be another place to ask for comments/prior art.

My point is, that while the IBM's patent as a whole could be worth
patent protection, each and every claim in it separately is probably
not.

--
Hannu Krosing <hannu@tm.ee>

I live in Europe, and right now, the patent, if granted, would not
have any effect on me. Even if Europe will have patents on software, I
doubt that this ARC algorithm will be patentable in Europe.

Is it possible to have an abstraction api where we can plug different
algorithms.
With two plugins : LRU, ARC. ARC in a contrib module on european server
only. ;-)
So any people get the best in regard to their local law. ;-/

It is a trick, a work-around, ok.
BUT, a general way to have some plugins for cache, database file
format, etc (like the one for new type/operator) could be very
interesting :
a) as a patent workaround
b) as a framework to test new feature

Cordialement,
Jean-Gérard Pailloncy

Ühel kenal päeval (teisipäev, 25. jaanuar 2005, 21:10-0400), kirjutas
Marc G. Fournier:

On Tue, 25 Jan 2005, Bruce Momjian wrote:

So if we have to address it we call it 8.0.7 or something. My point is
that we don't need to address it until we actually find out the patent
is being enforced against someone, and that possibility is quite unlikely.

Ah, so you are advocating waiting *until* the problem exists, even *after*
we know a) there may be a problem and b) we know that we can fix it ... ?

It may be my englisk skills, as I'm not a native speaker, but your
temporal logic escapes me ...

... waiting *until* the problem exists ... there *may be* a problem ...

so *bruce* advocates waiting *until* there *is* a problem, *we* know it
*may be* (*there* ?) and we know we *can* fix the problem that *may
be* ?

--
Hannu Krosing <hannu@tm.ee>

Neil Conway <neilc@samurai.com> writes:

Well, you've suggested that I should try and reduce the API churn caused
by the patch. As I said on -patches, I don't really see this as an issue
if we just apply the patch to REL8_0_STABLE.

If we do that then the patch will go out with essentially no testing
beyond your own; an idea that doesn't fill me with confidence.

I think the biggest area of concern with the LRU patch is how it changes
bgwriter behavior.

The easiest way to handle that is to keep storing a full list of all the
buffers in freelist.c, instead of reverting to the pre-8.0 data structure.
(Of course, if we decide we *want* to change the bgwriter behavior, it's
a different story.)

I think it would be better to have a few weeks of beta prior to 8.0.2
and resolve the problem here and now, rather than crippling the 8.1
cycle (as the no-initdb policy would) or waiting for the problem to
*really* become serious (as the "no action needed now" policy would).

I'm leaning in that direction too, but I think that the only way to get
any meaningful testing is to have the patch in HEAD as well as the back
branch. So I want something that doesn't undo more than the minimum
necessary to remove the ARC algorithm.

I don't have time to deal with this today or tomorrow, but once the
security releases are out, I will look at developing an LRU patch that
fits with my ideas about how to do it.

regards, tom lane

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

--0-918242224-1106762583=:81692
Content-Type: TEXT/PLAIN; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Wed, 26 Jan 2005, Hannu Krosing wrote:

=DChel kenal p=E4eval (teisip=E4ev, 25. jaanuar 2005, 21:10-0400), kirjut=

as

Marc G. Fournier:

On Tue, 25 Jan 2005, Bruce Momjian wrote:

So if we have to address it we call it 8.0.7 or something. My point is
that we don't need to address it until we actually find out the patent
is being enforced against someone, and that possibility is quite unlike=

ly.

Ah, so you are advocating waiting *until* the problem exists, even *afte=

r*

we know a) there may be a problem and b) we know that we can fix it ... =

?

It may be my englisk skills, as I'm not a native speaker, but your
temporal logic escapes me ...

... waiting *until* the problem exists ... there *may be* a problem ...

so *bruce* advocates waiting *until* there *is* a problem, *we* know it
*may be* (*there* ?) and we know we *can* fix the problem that *may
be* ?

Now you've totally confused me *shakes head*

Bruce is advocating waiting until the Patent has been Granted, instead of=
=20
doing something about it now, when we know the patent is going through the=
=20
system (and will likely get granted) ... a "reactive" vs "proactive"=20
response to the problem.

Basically, after the patent is granted, we are going to scramble to get=20
rid of the ARC stuff, instead of taking the time leadign up to the=20
granting to get rid of it so that when granted, it isn't something we have=
=20
to concern ourselves with ...

----
Marc G. Fournier Hub.Org Networking Services (http://www.hub.org)
Email: scrappy@hub.org Yahoo!: yscrappy ICQ: 7615664
--0-918242224-1106762583=:81692--

Hello all,

With this "paten issue" on hand, can't we come up with a "pluggable" API
and pluggable cache-replacement modules so that folks who care not for US
patents can simply download and load in the "PgARC" module, and those who
can't, just load the "NeilLRU", or a "BetterThanARCCacheReplacement"
module that don't violate those pattents. If the modules all conform to
the same pg-cache-replacement API, they could be swapped on the fly. I
believe the API and the two modules: ARC of Jan and LRU of Neil, can be
implemented for 8.0.1 and be less invasive than just ARC yanked out and
replaced with LRU.

I believe, PGDG does not need to concern itself with removing and all
traces of ARC from CVS or otherwise; on the conrary, it still can ship the
ARC module as an add-on to those who wish. This is possible because the
project is NOT hosted in the US (if I am wrong correct me).

This idea will also help the commercial vendros of PG to write up their
own modules they think best, of if they can't, just always load in LRU in
their commerical deployments of PG in the US.

--
Serguei A. Mokhov | /~\ The ASCII
Computer Science Department | \ / Ribbon Campaign
Concordia University | X Against HTML
Montreal, Quebec, Canada | / \ Email!

Hello all,

As I got the next digest of pg hackers, I see that Jean-Gerard Pailloncy
has already advocated this idea. In no means I meant to copy :) as I am
on the digest mode. However, I think it's a good path to go anyway as two
people at least came up with it. Please do not disregard this idea.

-s

On Wed, 26 Jan 2005, Serguei A. Mokhov wrote:

Date: Wed, 26 Jan 2005 14:51:49 -0500 (EST)
From: Serguei A. Mokhov <mokhov@cs.concordia.ca>
To: pgsql-hackers@postgresql.org
Subject: Re: Patent issues and 8.1

Hello all,

With this "paten issue" on hand, can't we come up with a "pluggable" API
and pluggable cache-replacement modules so that folks who care not for US
patents can simply download and load in the "PgARC" module, and those who
can't, just load the "NeilLRU", or a "BetterThanARCCacheReplacement"
module that don't violate those pattents. If the modules all conform to
the same pg-cache-replacement API, they could be swapped on the fly. I
believe the API and the two modules: ARC of Jan and LRU of Neil, can be
implemented for 8.0.1 and be less invasive than just ARC yanked out and
replaced with LRU.

I believe, PGDG does not need to concern itself with removing and all
traces of ARC from CVS or otherwise; on the conrary, it still can ship the
ARC module as an add-on to those who wish. This is possible because the
project is NOT hosted in the US (if I am wrong correct me).

This idea will also help the commercial vendros of PG to write up their
own modules they think best, of if they can't, just always load in LRU in
their commerical deployments of PG in the US.

--
Serguei A. Mokhov | /~\ The ASCII
Computer Science Department | \ / Ribbon Campaign
Concordia University | X Against HTML
Montreal, Quebec, Canada | / \ Email!

Bruce Momjian wrote:

pgman wrote:

...

What I would like to do is to pledge that we will put out an 8.0.X to
address any patent conflict experienced by our users. This would
include ARC or anything else. This way we don't focus just on ARC but
have a plan for any patent issues that appear, and we don't have to
adjust our development cycle until an actual threat appears.

This "pledge" sounds like an open-ended commitment of an infinite number
of development hours. I don't think you can pledge to address "any"
patent conflict. There is a limit to the number of tgl-hours in a day :).

One advantage we have is that we can easily adjust our code to work
around patented code by just installing a new binary. (Patents that
affect our storage format would be more difficult. A fix would have to
perhaps rewrite the on-disk data.)

"easily"? Maybe, maybe not. I don't think you can assume that the fix to
as-yet-unknown patent conflicts is necessarily going to be easy. Even
the USPTO occasionally grants patents on things that aren't trivial.

Just my AUD0.02, which should probably be worth even less given the size
of my contribution to postgresql to date.

Tim

--
-----------------------------------------------
Tim Allen tim@proximity.com.au
Proximity Pty Ltd http://www.proximity.com.au/
http://www4.tpg.com.au/users/rita_tim/

On Wed, 2005-01-26 at 02:09, Neil Conway wrote:

Tom Lane wrote:

This may be the right path to go for
8.0.* ... but we must NOT suppose that we can just push it out without
a full beta test cycle.

Yeah, I think a beta period would be a good idea (not nearly as long as
the 8.0 beta period was, though).

I think it would be better to have a few weeks of beta prior to 8.0.2
and resolve the problem here and now, rather than crippling the 8.1
cycle (as the no-initdb policy would) or waiting for the problem to
*really* become serious (as the "no action needed now" policy would).

I don't think it is worth breaking the expectation that only minor
changes get committed in revision level releases even with a beta. I
especially hate to think about support and tuning information that has
the potential to be quit different depending on if your running 8.0.1 or
8.0.2 or some such division.

I still feel a better plan is to use the short dev cycle for 8.1 to
replace ARC and include any non-initdb changes and to branch an 8.2 now
if people with initdb changes don't want to wait to do further
development. This allows people to move away from arc using a proper
release with out having to do dump/reload; certainly the path of least
resistance for users. It is also cleaner for folks in non-patent
countries.

Of course this isn't something that has to be fixed in the next 4
months... if enough initdb level changes are close now, we could commit
to a 6 month initdb/arc replace dev cycle followed by a 3 month beta for
8.1 and release before the end of the year. That might be best anyway
since I think we probably have 3-4 major changes already waiting to go
that can certainly be finished within 6 months (2PC, autovacuum, Devrims
work, ARC replacement, potential pitr replication changes) which would
be plenty enough to warrant a new release. It's not as good as the
8.1/8.2 plan but better than the 8.0.x plan (IMHO).

Robert Treat
--
Build A Brighter Lamp :: Linux Apache {middleware} PostgreSQL

Robert Treat <xzilla@users.sourceforge.net> writes:

I don't think it is worth breaking the expectation that only minor
changes get committed in revision level releases even with a beta.

Ordinarily I would agree with you, but what happens to someone who is
still running 8.0.* when IBM's patent gets issued? (It seems very
likely to me that the patent will be issued before 8.0 disappears from
the wild.) We really have to have an answer for that, and that means
that an algorithm change has to get back-patched into 8.0.*.

I'm coming around to the viewpoint that we should do this as a
back-patch rather than try to release a file-compatible 8.1. The reason
is that people who are hesitant to move up to a new release are hesitant
not only because of dump/reload costs; they also worry about whether a
new version will break their existing applications. If 8.1 has a pile
of new features, or even simple behavioral changes such as flipping the
with_oids default, then it will look like a hazard to them even without
a dump/reload cycle.

What's really being debated here is how we can have adequate confidence
in a change that is admittedly larger than we like to back-patch. It's
not an unprecedented thing mind you; we have back-patched some fairly
large bug fixes in the past. But it's a bit galling to be taking any
such risk for purely legal rather than technical reasons.

regards, tom lane

On Thu, 27 Jan 2005, Tom Lane wrote:

What's really being debated here is how we can have adequate confidence
in a change that is admittedly larger than we like to back-patch. It's
not an unprecedented thing mind you; we have back-patched some fairly
large bug fixes in the past. But it's a bit galling to be taking any
such risk for purely legal rather than technical reasons.

How hard would it be to do as several have suggested already ... abstract
out the ARC/LRU stuff into an API? Then, we wouldn't have to remove ARC,
per se, only shift it? Wouldn't that be a smaller patch overall? Then,
for our non-US users, they could continue to use ARC even after the patent
(myself included), while a plug-in replacement could be available for US
users?

----
Marc G. Fournier Hub.Org Networking Services (http://www.hub.org)
Email: scrappy@hub.org Yahoo!: yscrappy ICQ: 7615664

"Marc G. Fournier" <scrappy@postgresql.org> writes:

How hard would it be to do as several have suggested already ... abstract
out the ARC/LRU stuff into an API?

That was basically my objection to Neil's draft patch: it didn't make
any effort to abstract out a cleaner API. I'll try to look into this
after we have the security releases out of the way.

regards, tom lane