Hello,
Please CC: replies to me, since I am not subscribed.
>> http://citeseer.nj.nec.com/63909.html
> The "resistance to scanning" seemed interesting, maybe one-time
> activities like a "find" run or big cat/dd will have less impact with
> this.
Exactly. But not only that.
I have made some experimental tests. When you have totally random access
to data, you get degradation to LRU performance (but no worse). However,
when doing normal work, results are quite encouraging. Speedup percentage
is computed assuming processing in-memory buffer takes x and loading
on-disk buffer takes 100x time:
#blocks buffers P hitLRU hit2Q 2Q+ speedup
262400 16384 8 19.29% 24.89% 29% 7.365%
262400 16384 4 11.56% 14.23% 23% 3.084%
1024K 16384 32 16.90% 22.82% 35% 7.573%
1024K 16384 16 9.00% 11.94% 33% 3.305%
1024K 16384 8 4.94% 6.38% 29% 1.515%
4096K 16384 64 8.40% 11.39% 36% 3.339%
4096K 16384 32 4.32% 5.79% 34% 1.536%
I used reasonable figures for filesystem size (1G, 4G and 16G) and buffer
cache (64MB), with blocksize 4K. All simulations used 10% for A1in and 25%
for A1out queues. Almost all simulations show over 30% better hit rate as
LRU, translating to ~3% real time speedup for normal workload. Speedup for
scanning type workload (find, cat large file, etc.) should be even better
- write access pattern generator and try it :-)
Constant P determines "randomness" of accesses as follows:
int x = random() % (NR * LEVEL);
for (int i = LEVEL - 1; i > 0; --i)
if (x >= NR * i) x = (x - NR * i) / (i + 1);
where x is generated block # to be accessed, LEVEL is P and NR is # of
disk blocks.
I attach a crude program to simulate LRU, 2Q and FIFO buffer management
policies. If you want, you can play with parameters a little bit and
simulate other workloads (e.g., record what's going on in the system and
then simulate real system block accesses).
I would like to hear from you if you have some interesting results.
-- Ivan Schreter is@zapwerk.com
This archive was generated by hypermail 2b29 : Fri Jun 15 2001 - 21:00:24 EST