Date: Tue, 13 Nov 2018 18:24:35 -0800
From: Noah Misch <noah@leadboat.com>
To: Tom Lane <tgl@sss.pgh.pa.us>,
	Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Pg Hackers <pgsql-hackers@postgresql.org>
Subject: Re: DSM segment handle generation in background workers
Message-ID: <20181114022435.GC1096408@rfd.leadboat.com>
References: 
 <CAEepm=2eJj_6=B+2tEpGu2nf1BjthCf9nXXUouYvJJ4C5WSwhg@mail.gmail.com>
 <CAEepm=1oRxe3n3a6bq23-2MQTSWagHTghPbpGJ1YcZEyZ_KWQA@mail.gmail.com>
 <17043.1539046409@sss.pgh.pa.us>
 <CAEepm=2RqzvRyEXWxq8B9zR8p45tt-xsvA4S8ZNKNwpiUzMVKA@mail.gmail.com>
 <CAEepm=1xxETRCZexNSxkABpNg-65U6Z2pxynJ8V0vURqob+Rqw@mail.gmail.com>
 <9879.1539233472@sss.pgh.pa.us>
 <CAEepm=20PEf5bM3FAtD=CL7x0_WxFXfQ4Se9N9nConKucsr8pg@mail.gmail.com>
 <20181112083358.GA1073796@rfd.leadboat.com>
 <CAEepm=1+1jZiNHuRKaHgKZz1f=RFd8BnFpSgVsxEFNafjsqWZg@mail.gmail.com>
 <32455.1542033541@sss.pgh.pa.us>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <32455.1542033541@sss.pgh.pa.us>
User-Agent: Mutt/1.5.24 (2015-08-30)
Precedence: bulk

On Mon, Nov 12, 2018 at 09:39:01AM -0500, Tom Lane wrote:
> Thomas Munro <thomas.munro@enterprisedb.com> writes:
> > On Mon, Nov 12, 2018 at 9:34 PM Noah Misch <noah@leadboat.com> wrote:
> >> Compared to the old code, the new code requires more wall time to visit every
> >> possible seed value.  New code xor's the PID bits into the fastest-changing
> >> timestamp bits, so only about twenty bits can vary within any given one-second
> >> period.  (That assumes a PID space of twenty or fewer bits; fifteen bits is
> >> the Linux default.)  Is that aspect of the change justified?
> 
> > Hmm, right.  How about applying pg_bswap32() to one of the terms, as
> > an easy approximation of reversing the bits?

That seems adequate, yes.  But why not just restore the old algorithm in the
new function?  (I'm not opposed to revising the algorithm, but I think a
revision should have explicit goals.  The ease of pg_bswap32() is not itself a
worthy goal, because the old BackendRun() algorithm was also quite easy.)

> I doubt that's a good idea; to a first approximation, it would mean that
> half the seed depends only on the PID and the other half only on the
> timestamp.  Maybe we could improve matters a little by left-shifting the
> PID four bits or so, but I think we still want it to mix with some
> rapidly-changing time bits.
> 
> I'm not really sure that we need to do anything though.  Basically,
> what we've got here is a tradeoff between how many bits change over
> a given timespan and how unpredictable those bits are.  I don't see
> that one of those is necessarily more important than the other.

What counts is the ease of predicting a complete seed.  HEAD's algorithm has
~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
from 98c5065 until 197e4af had no such bits.  You're right that the other 19
bits are harder to predict than any given 19 bits under the old algorithm, but
the complete seed remains more predictable than it was before 197e4af.

Goal I recommend: if connections arrive in a Poisson distribution of unknown
lambda, maximize the number of distinct seeds.

nm