Re: [Blocks-development] V0.16 progress

[Blat F. <pet...@ho...>]

>From: "Michael Spencer Jr." <bl...@ms...>
>To: "Erik Moeller" <mo...@sc...>,        
><blo...@li...>
>Subject: Re: [Blocks-development] V0.16 progress
>Date: Thu, 24 Aug 2000 22:59:04 -0500
>
>My thought is...LRU cache entry expiry (which is what we had been using,
>right) is pretty universally a good thing.  LRU flushes out the things that
>haven't been used in a while, by definition.  So if all blocks are weighted
>equally (like in a hard disk) LRU is pretty close to optimal.

LRU was the original intention but thats not quite the way it
works right now. As you might have noticed in the source code
there is a lot of "// TODO: move to top of list?" comments.
These are (some of) the places that would need to be adjusted
to implement a LRU cache.

At the moment the cache is just a big FIFO ring which isnt
as bad as it sounds. The distributed nature of Blocks means
that files which expire will get replicated due to routing
if they are really popular, and the cacheing system itself
means that LRU wouldnt necessarily favour the most popular
files... just the most popular node for that file.

There is probably a thesis here somewhere :-)

>
>However, blocks are not evenly weighted, because of two things:
>
>1)  if the server's user placed a file there himself, he's probably more
>interested in keeping that file available than he is in using the space to
>cache other files.  So those blocks are special.

Thats the 'sticky' file idea. However, by marking the blocks
as special you lose plausible deniability that the file
was proxied into cache and can therefore be held liable
for publishing. Of course, in order to prove this your
computer would have to be captured while its actively running
the server since the cache is encrypted, but that might
be too much for some. Currently you can swear under oath
that you dont know whether or not you uploaded the file
since any file you might have uploaded may have been
expired and replaced.

This is a good issue for debate. Are sticky files a
good idea?

>
>2)  if a file is composed of multiple blocks, if you expire one block 
>you've
>made the whole file unavailable.  This doesn't count if you actually have 
>no
>idea that all these blocks go together...but if you have some concept that
>the blocks all form one file, then you should weight the blocks together 
>and
>expire them all at once.

Blocks stores files as header and data blocks in its FIFO cache
like this...

HDDDDDDDDDDDDDD...

so the header block expires before the data blocks do. This
effectively expires the whole file. However, should a request
to a further away server be routed through the server with
this cache, the server may intercept the requests for data
blocks that it has... therefore speeding up the download
and avoiding the problems of people downloading 90% of
a huge file before they find out that the end has expired :-)

>
>So I think together this yields:
>
>Sticky files and blocks.  Already being worked on.
>
>Different LRU behavior?  Perhaps take a weighted average of block age vs.
>block-group size -- a 500 block file that's 1 day old will have similar
>weight to a 100 block file that's 5 days old.  So larger files 'gain 
>weight'
>:) faster and drop off the cache sooner.
>
>Does this scenario fail easily?

Hmmm... a 1Gb file consists of 20000 blocks... video archives
might have a short lifespan.

>
>Suppose I have a 2 GB cache, filled 1.99 GB full of sticky user-uploaded
>files.
>
>I now have 160 blocks to fill with data as it comes around.  Suppose 
>someone
>transfers a 159 block file through me, finishes the file...I advertise
>it...and I recognize that file to be a whole file, not a disconnected bunch
>of blocks.  No other traffic is going through me while this file is being
>transferred through me.
>
>Then suppose it's a popular file.  Lots of people start requesting it from
>me...so I'm servicing at least one request for at least one part of the 
>file
>at all times.  It's pretty much impossible for that file to gain any
>'discard weight' -- any file size multiplied by zero age is still zero.  So
>that file is effectively locked in my cache until people stop requesting it
>for even one second.

Remember its quite difficult to acertain what a 'popular' file
is at any one server.

>
>So what do I have with that one-block cache?  A complete inability to
>download anything.  (Right?)  I can only route blocks for other people.  
>And
>only one block at a time -- if someone has a 1k/sec connection to me, that
>will be the only block (besides the popular file and the files I'm sharing)
>I can transfer until the transfer is done.  I will also not be publishing
>any new files -- I would need both the header and all of the (non-zero) 
>data
>blocks...and I can't store that in one block.

Sticky files will probably have to exist out-of-cache or
there has to be at least some safeguards that the public
cache space is big enough. Zero length files are not allowed.

>
>Is that graceful degradation, in those extreme circumstances?  Is it
>considered graceful, considering that this one popular file is being
>downloaded *constantly* multiple times.  If that's all my node is good
>for...is that enough?
>
>BTW, if this seems costly to compute...you can just start purging by LRU
>when the free cache hits a low water mark, and keep purging until you hit a
>high water mark.
>
>What do you think?

There are 16384 blocks per Gb of cache, and each cache entry
uses (at least) 16bytes to store the block ID (1Mb per Gb).
But in order to encourage large caches we dont really have
that much CPU available to do housekeeping so ideally we
need an incremental algorithm to do this. There are lots of
good and useful observations in what you have said above,
but I dont think we have a crystal clear view of the
complete problem set to be solved (yet).

Yet another thesis for someone :-)

ttfn

PG.

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com