From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WuJRn-0005HU-0u for bitcoin-development@lists.sourceforge.net; Tue, 10 Jun 2014 10:38:31 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.219.50 as permitted sender) client-ip=209.85.219.50; envelope-from=mh.in.england@gmail.com; helo=mail-oa0-f50.google.com; Received: from mail-oa0-f50.google.com ([209.85.219.50]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1WuJRl-0007Cv-6f for bitcoin-development@lists.sourceforge.net; Tue, 10 Jun 2014 10:38:30 +0000 Received: by mail-oa0-f50.google.com with SMTP id n16so3310483oag.37 for ; Tue, 10 Jun 2014 03:38:23 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.47.77 with SMTP id b13mr31912323oen.40.1402396703439; Tue, 10 Jun 2014 03:38:23 -0700 (PDT) Sender: mh.in.england@gmail.com Received: by 10.76.71.162 with HTTP; Tue, 10 Jun 2014 03:38:23 -0700 (PDT) In-Reply-To: <20140608213534.GA4191@savin> References: <20140606081933.GA29458@savin> <20140606084852.GA30247@netbook.cypherspace.org> <20140606090441.GA19256@savin> <20140606104543.GA31085@netbook.cypherspace.org> <20140606164639.GB14891@savin> <20140606170524.GA29195@savin> <20140606174545.GB29195@savin> <20140608213534.GA4191@savin> Date: Tue, 10 Jun 2014 18:38:23 +0800 X-Google-Sender-Auth: S5eksyV1ZC1ERtD0myil8byAX9M Message-ID: From: Mike Hearn To: Peter Todd Content-Type: multipart/alternative; boundary=001a11c2111657c1dc04fb78ed0a X-Spam-Score: -0.5 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (mh.in.england[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1WuJRl-0007Cv-6f Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Bloom bait X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 10 Jun 2014 10:38:31 -0000 --001a11c2111657c1dc04fb78ed0a Content-Type: text/plain; charset=UTF-8 > > As I explained in the email you're replying to and didn't quote, bloom > filters has O(n) cost per query, so sending different bloom filters to > different peers for privacy reasons costs the network significant disk > IO resources. If I were to actually implement it it'd look like a DoS > attack on the network. > DoS attack? Nice try. Performance is subtle, disk iops especially so. I suspect you'd find - if you implemented it - that for the kinds of loads Bitcoin is processing both today and tomorrow prefix filtering either doesn't save any disk seeks or actively makes it worse. Consider a client that is syncing the last 24 hours of chain. bitcoind pre-allocates space for blocks in large chunks, so most blocks are laid out sequentially on disk. Almost all the cost of a disk read is rotational latency. Once the head is in place data can be read in very fast and modern kernels will attempt to adaptively read ahead in order to exploit this, especially if a program seems to be working through a disk file sequentially. The work of Bloom filtering parts of the chain for this client boils down to a handful of disk seeks at best and the rest of the work is all CPU/memory bound as the block is parsed into objects and tested against the filter. A smarter filtering implementation than ours could do SAX-style parsing of the block and avoid the overhead of turning it all into objects. Now consider a prefix filtering implementation. You need to calculate a sorted list of all the data elements and tx hashes in the block, that maps to the location in the block where the tx data can be found. These per-block indexes take up extra disk space and, realistically, would likely be implemented using LevelDB as that's a tool which is designed for creating and using these kinds of tables, so then you're both loading the block data itself (blocks are sized about right currently to always fit in the default kernel readahead window) AND also seeking through the indexes, and building them too. A smart implementation might try and pack the index next to each block so it's possible to load both at once with a single seek, but that would probably be more work, as it'd force building of the index to be synchronous with saving the block to disk thus slowing down block relay. In contrast a LevelDB based index would do the bulk of the index-building work on a separate core. At *some* block size and client load the additional data storage and increased pressure on the page cache would probably make it worthwhile. But I find it unlikely to be true at current traffic levels, or double or triple today's levels. So I'd rather we spend our very limited collective time on finding ways to increase usage rather than worrying about resources which are not presently scarce. (as an aside, some of the above analysis would be invalidated if most nodes end up running on SSDs, but I doubt most are. It'd be neat to export storage tech via some kind of stats message - LevelDB is designed for HDDs not SSDs so at some point a new storage subsystem might make sense if the network switched over). --001a11c2111657c1dc04fb78ed0a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
As I explained in the email you're replying = to and didn't quote, bloom
filters has O(n) cost per query, so sending different bloom filters to
different peers for privacy reasons costs the network significant disk
IO resources. If I were to actually implement it it'd look like a DoS attack on the network.

DoS attack? Nice= try.

Performance is subtle, disk iops especially = so. I suspect you'd find - if you implemented it - that for the kinds o= f loads Bitcoin is processing both today and tomorrow prefix filtering eith= er doesn't save any disk seeks or actively makes it worse.

Consider a client that is syncing the last 24 hours of = chain. bitcoind pre-allocates space for blocks in large chunks, so most blo= cks are laid out sequentially on disk. Almost all the cost of a disk read i= s rotational latency. Once the head is in place data can be read in very fa= st and modern kernels will attempt to adaptively read ahead in order to exp= loit this, especially if a program seems to be working through a disk file = sequentially. The work of Bloom filtering parts of the chain for this clien= t boils down to a handful of disk seeks at best and the rest of the work is= all CPU/memory bound as the block is parsed into objects and tested agains= t the filter. A smarter filtering implementation than ours could do SAX-sty= le parsing of the block and avoid the overhead of turning it all into objec= ts.

Now consider a prefix filtering implementation. You nee= d to calculate a sorted list of all the data elements and tx hashes in the = block, that maps to the location in the block where the tx data can be foun= d. These per-block indexes take up extra disk space and, realistically, wou= ld likely be implemented using LevelDB as that's a tool which is design= ed for creating and using these kinds of tables, so then you're both lo= ading the block data itself (blocks are sized about right currently to alwa= ys fit in the default kernel readahead window) AND also seeking through the= indexes, and building them too. A smart implementation might try and pack = the index next to each block so it's possible to load both at once with= a single seek, but that would probably be more work, as it'd force bui= lding of the index to be synchronous with saving the block to disk thus slo= wing down block relay. In contrast a LevelDB based index would do the bulk = of the index-building work on a separate core.

At some block size and client load the additiona= l data storage and increased pressure on the page cache would probably make= it worthwhile. But I find it unlikely to be true at current traffic levels= , or double or triple today's levels. So I'd rather we spend our ve= ry limited collective time on finding ways to increase usage rather than wo= rrying about resources which are not presently scarce.

(as an aside, some of the above analysis would be inval= idated if most nodes end up running on SSDs, but I doubt most are. It'd= be neat to export storage tech via some kind of stats message - LevelDB is= designed for HDDs not SSDs so at some point a new storage subsystem might = make sense if the network switched over).


--001a11c2111657c1dc04fb78ed0a--