Re: [Patch][WiP] Tweaked LRU for shared buffers

Hi,

On 2/13/19 3:37 PM, Andrey Borodin wrote:
> Hi, hackers!
>
> We have held education project at Sirius edu center (Sochi, Russia)
> with mentors from Yandex. The group of 5 students was working on
> improving the shared buffers eviction algorithm: Andrey Chausov, Yuriy
> Skakovskiy, Ivan Edigaryev, Arslan Gumerov, Daria Filipetskaya. I’ve
> been a mentor for the group. For two weeks we have been looking into
> known caching algorithms and tried to adapt some of them for PostgreSQL
> codebase.
>
> While a lot of algorithms appeared to be too complex to be hacked in
> 2 weeks, we decided to implement and test the working version of
> tweaked LRU eviction algorithm.
>
> ===How it works===
> Most of the buffers are organized into the linked list. Firstly
> admitted pages jump into 5/8th of the queue. The last ⅛ of the queue is
> governed by clock sweep algorithm to improve concurrency.
>

Interesting. Where do these numbers (5/8 and 1/8) come from?

> ===So how we tested the patch===
> We used sampling on 4 Yandex.Cloud compute instances with 16 vCPU
> cores, 8GB of RAM, 200GB database in 30-minute YCSB-like runs with Zipf
> distribution. We found that on read-only workload our algorithm is
> showing consistent improvement over the current master branch. On
> read-write workloads we haven’t found performance improvements yet,
> there was too much noise from checkpoints and bgwriter (more on it in
> TODO section).
> Charts are here: [0,1]

That TPS chart looks a bit ... wild. How come the master jumps so much
up and down? That's a bit suspicious, IMHO.

How do I reproduce this benchmark? I'm aware of pg_ycsb, but maybe
you've used some other tools?

Also, have you tried some other benchmarks (like, regular TPC-B as
implemented by pgbench, or read-only pgbench)? We need such benchmarks
with a range of access patterns to check for regressions.

BTW what do you mean by "sampling"?

> We used this config: [2]
>

That's only half the information - it doesn't say how many clients were
running the benchmark etc.

> ===TODO===
> We have taken some ideas expressed by Ben Manes in the pgsql-hackers
> list. But we could not implement all of them during the time of the
> program. For example, we tried to make LRU bumps less write-contentious
> by storing them in a circular buffer. But this feature was not stable
> enough.

Can you point us to the thread/email discussing those ideas? I have
tried searching through archives, but I haven't found anything :-(

This message does not really explain the algorithms, and combined with
the absolute lack of comments in the linked commit, it'd somewhat
difficult to form an opinion.

> The patch in its current form also requires improvements. So, we
> shall reduce the number of locks at all (in this way we have tried
> bufferization, but not only it). “Clock sweep” algorithm at the last
> ⅛ part of the logical sequence should be improved too (see
> ClockSweepTickAtTheAnd() and places of its usage).
OK

> Unfortunately, we didn’t have more time to bring CAR and W-TinyLFU
> to testing-ready state.

What is CAR? Did you mean ARC, perhaps?

> We have a working implementation of frequency sketch [3] to make a
> transition between the admission cycle and LRU more concise with TinyLFU
> filter. Most probably, work in this direction will be continued.

OK

> Also, the current patch does not change bgwriter behavior: with a
> piece of knowledge from LRU, we can predict that some pages will not be
> changed in the nearest future. This information should be used to
> schedule the background writes better.

Sounds interesting.

> We also think that with proper eviction algorithm shared buffers
> should be used instead of specialized buffer rings.
>

Are you suggesting to get rid of the buffer rings we use for sequential
scans, for example? IMHO that's going to be tricky, e.g. because of
synchronized sequential scans.

> We will be happy to hear your feedback on our work! Thank you :)
>
> [0] LRU TPS https://yadi.sk/i/wNNmNw3id22nMQ
> [1] LRU hitrate https://yadi.sk/i/l1o710C3IX6BiA
> [2] Benchmark config https://yadi.sk/d/L-PIVq--ujw6NA
> [3] Frequency sketch code https://github.com/heyfaraday/postgres/commit/a684a139a72cd50dd0f9d031a8aa77f998607cf1
>
> With best regards, almost serious cache group.
>

cheers

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services