Re: Disk cache

Arvid Norberg wrote:
> On Apr 10, 2006, at 20:53, Radu Hociung wrote:
> 
>> Hello Arvid, and all,
>>
>> I think caching at the application level can be far more efficient  than
>> at the O/S level, as the application typically can manage
>> characteristics of the dataflow, whereas the O/S cannot. Please see 
>> below.
> 
> 
> Yes, this is true in general, my concern is that the characteristics  of
> the dataflow in the bittorrent case is very close to completely  random.
> Talking about the request pattern, the only exception to  randomness is
> the rarest first-algorithm. But this algorithm will  also make sure that
> the distribution among the peers is as uniform as  possible at all time,
> keeping the request pattern as random as possible.
> 
> It is true though, that in the case where the swarm has tendencies of 
> being "serialized", it is very common to request pieces which were  just
> made available from a peer. But I'm not sure that is a very  common
> case. Obviously some data is needed here.

The serialized downloads make sense in at least two scenarios:

a. well-seeded torrents, and/or
b. applications where it is desirable to start playback as soon as
possible after the download starts. Obviously this makes sense mainly
for media-type torrents.

You're right, without more data, I find it hard to agree that randomness
is a good thing. In the case of a well-established torrent (ie,
long-lived, aggregate upload capacity balanced with aggregate download
capacity), the arrival time of new clients is random, and even though
their individual download pattern could be serialized, the request
pattern seen by individual seeds would be random.

But I think this is a topic big enough to deserve its own thread/research.

I will use the good/bad/perfect torrent taxonomy defined at
http://azureus.aelitis.com/wiki/index.php/Good_Torrents and probably
elsewhere too.

>> I will use "cheap data" and "expensive data" to refer to in-buffer and
>> on-disk data respectively.
>>
>> The theory of Nash equilibrium applies very much to torrents, I think.
>> Downloading torrents is a non-cooperative game, in that each client is
>> concerned with ensuring only its own success, and the strategy it must
>> employ is of maximizing the chance for success while minimizing its  cost
>> of achieving success.
> 
> 
> true.
> 
>> Please see below for my comments on caching.
>>
>> Arvid Norberg wrote:
>>
>>> There has been some discussion on the IRC channel about benefits and
>>> possible cache algorithms for a disk cache in libtorrent. I'm posting
>>> this hoping that somebody could comment on some of the techniques or
>>> assumptions.
>>>
>>> The way I see it, there are two problems that a cache aims to solve:
>>>
>>> 1. seeding on a high speed connection will make the hard drive seek a
>>> lot back and forth, just to do short reads.
>>>
>>> 2. downloading on a high speed connection will make the hard  drive 
>>> seek
>>> a lot back and forth.
>>>
>>>
>>> For 1, one assumption that can be made is that if block 0 is   requested
>>> from a piece, it's very likely that many more blocks from  that piece
>>> will be requested soon. So caching the entire piece at  once would
>>> probably be a good idea.
>>>
>>> This is exactly what a normal OS' disk cache does. It reads ahead   into
>>> the cache. So I don't really see any benefit if caching this at
>>> application level. One possible optimization would be if the disk  
>>> cache
>>> could be bypassed so that only one piece was cached (since the  disk
>>> cache in the OS may cache more than the piece we're reading   from).
>>> This
>>> would be hard to do, and especially hard to do in a  platform
>>> independent manner.
>>>
>>> Is this a reasonable assumption?
>>
>>
>> If the application is able to fill the available outgoing bandwidth  with
>> cheap data, there is no benefit to reading more/other data from the
>> disk, is there?
>>
>> I think it would be a good idea for the library to prefer to  respond to
>> requests for cheap data, and postpone responses to requests for
>> expensive data until the utilization of the available outgoing  bandwidth
>> drops. Clients that request expensive data should be choked until  cheap
>> data can no longer fill the outgoing pipe, and it becomes necessary to
>> read expensive data to fill the pipe.
> 
> 
> The client isn't completely free of choosing who to upload to/whose 
> requests to respond do. In order to maximize download speed, it has  to
> upload to those that it can download from. I also think that the  most
> common case is that the output pipe very seldom is saturated.  So, I'm
> not sure weighting peers depending on the pieces they request  would
> work very well, it would affect the behavior of the client in  other ways.
> 
> Your distinction of cheap and expensive data doesn't take seek  distance
> into account. I think that may be the most important thing  to
> concentrate on, at least when it comes to writing.

I thought your number 1 aim deals with seeds on high-speed links, hence
no downloading.

Since there are different scenarios which have distinct properties,
maybe caching behaviour could be altered as necessary. The 4 scenarios
I'm thinking of are:

a. seeding with out pipe saturated
b. seeding with out pipe underutilized
c. downloading from torrent "good" or better
d. downloading from torrent "acceptable" or worse

The key difference between a-b is that the data being requested is
likely available cheaper from another seed.

The key difference between c-d is that a random dl pattern is
unnecessary in c.

> 
>>> Number 2 is a little bit more interesting though. Since every block
>>> that is downloaded has to be written to disk, and since every  block  is
>>> only downloaded once, you cannot really optimize away disk  writes. 
>>> What
>>> you can do though, is to optimize the disk seeking.
>>
>>
>> Absolutely. Also, since while downloading, the client also uploads, it
>> would be more disk efficient to only seek for disk writes, but  never for
>> disk reads. Ie, the client should prefer to respond to requests for  data
>> is has freshly downloaded, instead of reading other data from disk.
>> Assuming that the client downloads least-common data first, it's a
>> reasonable assumtion that the data it holds in memory buffers is still
>> rare to other clients.
> 
> 
> Yes, at least to a certain degree. One thing to keep in mind though,  is
> that the number of pieces in a torrent is generally much more than  the
> number of peers that a client can see. How rare a piece is is  quantized
> to the number of peers that has it. This means that the  number of
> equally rare pieces is usually very high, far higher than a  write cache
> would be.

I think you're making the (healthy) assumption that a client would cache
 one, or very few pieces for upload? This is very good for lowering
memory footprints of the client.

What I am thinking is that as soon as a client advertises a completed
piece, many swarm members would request it immediately, instead of
requesting other pieces. The just-downloaded piece is cheap data, and
the downloading client would prioritize its upload.

In an ideal swarm, each piece in a torrent would be read from a disk
exactly once, and written to disk exactly N-1 times (for N clients in
the swarm). A torrent that is well seeded ("good" or better) should be
able to approach this ideal, without risking the availability of any
piece to be so low as to endanger the torrent. For a torrent that is
"acceptable" or worse, the rarest-first approach may be given a higher
preference than the ideal.


>> In this case, the library should write to disk when downloaded pieces
>> are complete, but do not free the buffers until other clients have
>> downloaded them enough to cause the uplink utilization to drop.
>>
>> I have thought about optimizing the dataflow a lot. I believe there  are
>> at least two good reasons for improving caching of torrents:
>>
>> 1. Fewer seeks == less noise == drives lasting longer.
>> 2. Fewer seeks == drive is more responsive to other apps that run
>> concurently.
> 
> 
> Definitely, I think the disk perfomance is very important.
> 
> I might add that there's a huge difference for me (OSX 10.4) when 
> downloading in full allocation mode and compact allocation mode. The 
> compact allocation mode will have the effect that most reads and  writes
> are kept relatively close to each other. They will spread out  over time
> of course though. But just downloading with client_test  will saturate
> my connection at slightly above 1 MB/s if I'm in  compact mode. In full
> allocation mode though, I will not get above  about 600 kB/s, and my
> drive is really making a noise and slowing  down the computer to be
> virtually useless.

Fascinating! This would seem to support compact/serialized downloading.

>> I believe the on-drive cache is better than nothing, O/S cache is  better
>> than the on-drive cache, and application cache is better than O/S  cache.
>> The closer the cache is to the data generation/consumption algorithm,
>> the more information is available for optimizing it.
>>
>> I think this approach to caching gives an answer to multiple-torrent
>> caching as well.
> 
> 
> What do you mean? Do you think there would be a point of having a 
> shared cache for all torrents?
> 
> One benefit would be that if you have 100 torrents but only 2 of them 
> are active, they will get all the cache for themselves.

This, and more. Each client could quantify the quality of the torrents
it serves, and even chose to (temporarily) not service well-seeded
torrents, while allocating upload bandwidth and cache to the
less-healthy torrents. In this case, a torrent client serving a large
collection of torrents (50+) could do so by dynamically choosing which
torrents to serve now, and which are safe to download. A possible
criteria for serving a torrent would be "always serve only the 1/2 worst
torrents". It is very likely that the client would have no trouble
maxing its upload pipe on bad torrents (thus healing them the fastest).
This approach somewhat ignores the download needs.

A slightly better approach would be "serve the 1 worst torrent, with max
cache, and the worst torrent which allows me to max my download
capacity". Ie. if we have for instance 50 torrents, numbered in the
order of their quality, with 1 being seeds-only, and 50 being mostly
leaches", the client would pick torrent 50 to dedicate its cache to, and
torrent 21 for maxing its download. (say that on torrent 1 we get a 1/6
dl/ul speed, while on torrent 21, which has many seeds, we get 4/1, and
the two add up such that both up and down bandwidths are both
maximized). In this case, there are many disk writes caused by torrent
21, but no disk reads, and very few disk writes from torrent 50, and no
reads. The heads will rarely seek to the torrent 50 file, but stay on
the 21 file most of the time. Given that most of the cache is allocated
to torrent 50 and that it is downloading serialized, when it needs to
write to disk, it writes infrequently and in big chunks. Seek time is
thus minimized as well.

>> One more thing:
>>
>> I have considered working on a test-bench that is able to run a swarm.
>> The testbench would be able to report disk-access efficiency, by
>> measuring some metrics, like how far apart the written pieces are in
>> memory (ie, seek throw), total number of accesses, etc. The idea is  that
>> it can be calculated empirically what the minimum number of accesses,
>> and long seeks is to fully download a file, while saturating the  output
>> link. The metrics given by the testbench could be compared to the  ideal,
>> and a measure of client efficiency would thus be obtained. (Naturally,
>> min-long-seeks = 0, and min-accesses = file-size/buffer-size)
>>
>> The test-bench would hook O/S calls in a manner similar to strace, and
>> would be able to run multiple makes/brands/versions of clients, such
>> that swarm behaviour can be observed. This would be very useful to  study
>> potential protocol changes and their effect on older-version clients.
> 
> 
> That sounds like it could be very useful!

I wonder if there would be any volunteers to donate some time to help
with the cause.

>> I am very interested in your thoughts and comments on caching,
> 
> 
> Ditto :)
> 
> So, I think my first attempt will be to cache pieces, and only write 
> whole pieces instead of blocks to disk. To see if the performance is 
> improved. I don't know how to measure it though, maybe I could try 
> saturating my download link in full allocation mode and see if it 
> increases.

But would this not increase the memory footprint of the application,
seeing how as many download buffers are needed as there are parallel
downloads, while none of these buffers can be used to upload from, as
their data has not been checksummed until they have completed downloading?

> Do you have any other suggestions that are reasonably easy to try out?

I think the first thing to do in studying the effects of libtorrent
caching would be to disable the O/S cache, in order to make comparisons
between versions relevant.

It would be interesting to find out how much riskier it is for a client
to serialize its downloads on poor torrents. Obviously it is safest to
do rarest-first on such torrents, but I am curious as to the difference
between rarest-first and serialized.

Also, we should not forget of the relationship between memory footprint
and caching effectiveness. It's easy to get more effective by allowing
increased memory use, but we should resist increased memory use when
possible.

How are you able to get 1MB/s ? Do you have torrents running on a test
network? Are the experiments reproducible? Would you mind describing
your test setup?

Greetings,
Radu.



-------------------------------------------------------
This SF.Net email is sponsored by xPML, a groundbreaking scripting language
that extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding territory!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642