Re: [REVIEW] Re: Compression of full-page-writes

<div dir="ltr"><p dir="ltr"><br /> Em 14/09/2014 12:21, "Andres Freund" <<a href="mailto:andres@2ndquadrant.com"
target="_blank">andres@2ndquadrant.com</a>>escreveu:<br /> ><br /> > On 2014-09-13 20:27:51 -0500, <a
href="mailto:ktm@rice.edu"target="_blank">ktm@rice.edu</a> wrote:<br /> > > ><br /> > > > What we are
lookingfor here is uniqueness thus better error detection. Not<br /> > > > avalanche effect, nor
cryptographicallysecure, nor bit distribution.<br /> > > > As far as I'm aware CRC32C is unbeaten collision
wiseand time proven.<br /> > > ><br /> > > > I couldn't find tests with xxhash and crc32 on the same
hardwareso I spent<br /> > > > some time putting together a benchmark (see attachment, to run it just<br />
>> > start run.sh)<br /> > > ><br /> > > > I included a crc32 implementation using ssr4.2
instructions(which works on<br /> > > > pretty much any Intel processor built after 2008 and AMD built after
2012),<br/> > > > a portable Slice-By-8 software implementation and xxhash since it's the<br /> > > >
fastestsoftware 32bit hash I know of.<br /> > > ><br /> > > > Here're the results running the test
programon my i5-4200M<br /> > > ><br /> > > > crc sb8: 90444623<br /> > > > elapsed:
0.513688s<br/> > > > speed: 1.485220 GB/s<br /> > > ><br /> > > > crc hw: 90444623<br />
>> > elapsed: 0.048327s<br /> > > > speed: 15.786877 GB/s<br /> > > ><br /> > > >
xxhash:7f4a8d5<br /> > > > elapsed: 0.182100s<br /> > > > speed: 4.189663 GB/s<br /> > >
><br/> > > > The hardware version is insanely and works on the majority of Postgres<br /> > > >
setupsand the fallback software implementations is 2.8x slower than the<br /> > > > fastest 32bit hash
around.<br/> > > ><br /> > > > Hopefully it'll be useful in the discussion.<br /> ><br /> >
Notethat all these numbers aren't fully relevant to the use case<br /> > here. For the WAL - which is what we're
talkingabout and the only place<br /> > where CRC32 is used with high throughput - the individual parts of a<br />
>record are pretty darn small on average. So performance of checksumming<br /> > small amounts of data is more
relevant.Mind, that's not likely to go<br /> > for CRC32, especially not slice-by-8. The cache fooprint of the
large<br/> > tables is likely going to be noticeable in non micro benchmarks.<br /> ><p dir="ltr">Indeed, the
smallinput sizes is something I was missing. Something more cache friendly would be better, it's just a matter of
findinga better candidate.<p dir="ltr"> Although I find it highly unlikely that the 4kb extra table of sb8 brings its
performancedown to sb4 level, even considering the small inputs and cache misses.<p>For what's worth mysql, cassandra,
kafka,ext4, xfx all use crc32c checksums in their WAL/Journals.<br /><p dir="ltr">> > Also, while I understand
thatCRC has a very venerable history and<br /> > > is well studied for transmission type errors, I have been
unableto find<br /> > > any research on its applicability to validating file/block writes to a<br /> > >
diskdrive.<br /> ><br /> > Which incidentally doesn't really match what the CRC is used for<br /> > here. It's
usedfor individual WAL records. Usually these are pretty<br /> > small, far smaller than disk/postgres' blocks on
average.There's a<br /> > couple scenarios where they can get large, true, but most of them are<br /> > small.<br
/>> The primary reason they're important is to correctly detect the end of<br /> > the WAL. To ensure we're
interpretinghalf written records, or records<br /> > from before the WAL file was overwritten.<br /> ><br />
><br/> > > While it is to quote you "unbeaten collision wise", xxhash,<br /> > > both the 32-bit and
64-bitversion are its equal.<br /> ><br /> > Aha? You take that from the smhasher results?<br /> ><br /> >
>Since there seems to be a lack of research on disk based error<br /> > > detection versus CRC polynomials, it
seemslikely that any of the<br /> > > proposed hash functions are on an equal footing in this regard. As<br />
>> Andres commented up-thread, xxhash comes along for "free" with lz4.<br /> ><br /> > This is pure
handwaving.<br/> ><br /> > Greetings,<br /> ><br /> > Andres Freund<br /> ><br /> > --<br /> >
 AndresFreund                     <a href="http://www.2ndQuadrant.com/"
target="_blank">http://www.2ndQuadrant.com/</a><br/> >  PostgreSQL Development, 24x7 Support, Training &
Services<br/></div>