Hello, Alexey! Thank you for your effort, the feature looks great!
Could you please give a bit more time to review it? Best regards, Mirza Aliev пт, 22 янв. 2021 г. в 10:19, Alex Plehanov <plehanov.a...@gmail.com>: > Hello, Igniters! > > Zhenya has already approved the patch that adds segmented-LRU and CLOCK > page replacement modes [1] (thanks for the review!). Would anyone else like > to review it? > I have plans to merge it next Monday if nobody else will be interested in > reviewing it. > > [1]: https://issues.apache.org/jira/browse/IGNITE-13761 > > пт, 25 дек. 2020 г. в 12:26, Alex Plehanov <plehanov.a...@gmail.com>: > > > Guys, > > > > I've implemented Segmented-LRU page replacement algorithm and benchmarked > > results, it gives some boost (5-10%) when page replacement is > > heavily used, but, unfortunately, when replacement is not used it gives > > about 2% drop compared to the current Random-LRU page replacement > > implementation. Due to this, I think Segmented-LRU can't be used as the > > only option or option by default. > > > > Also, I've implemented CLOCK page replacement algorithm (basic, > > not scan-resistant version) and benchmark results are much better. It > gives > > about the same performance as Segmented-LRU when page replacement is used > > and about the same performance as Random-LRU where there is no page > > replacement. There are advanced modifications of CLOCK algorithm exists, > > but usually, they require additional maintenance cost and we can again > get > > drop on environments without page replacements compared to Random-LRU. > I've > > written a benchmark with background full cache scans and even in this > case > > basic CLOCK version looks promising. > > > > So, my proposals: > > 1. Include all 3 implementations (Random-LRU, Segmented-LRU, CLOCK) to > the > > product. > > 2. Make page replacement algorithm configurable. > > 3. Recommend to use Random-LRU for environments with no page replacements > > (as it has zero maintenance cost). Recommend to use Segmented-LRU for > > environments with a high page replacement rate and a large amount of > > one-time scans (as it has near to optimal page to replace selection > policy > > and scan-resistant). Recommend to use CLOCK for all other cases (as it > has > > near to zero maintenance cost and efficiency of page replacement near to > > Segmented-LRU). > > 4. Set CLOCK as the default page replacement algorithm. > > > > WDYT? > > > > I've filled the IEP [1] for this discussion and create the pull request > > [2] for the last proposal. I would appreciate for review of the patch. > > > > [1]: > > > https://cwiki.apache.org/confluence/display/IGNITE/IEP-62+Page+replacement+improvements > > [2]: https://github.com/apache/ignite/pull/8513 > > > > пн, 23 нояб. 2020 г. в 11:12, Zhenya Stanilovsky > > <arzamas...@mail.ru.invalid>: > > > >> > >> > >> Nikolay, i hope such case ignite users already observed) > >> I suggest to: put data bigger then available, full scan, get data only > >> for available inmem data in loop, check PageReplacement metric, how > match > >> iterations will bring to zero this metric. > >> > >> >Hello, Alex. > >> > > >> >> Perhaps we can implement a special benchmark for this case with > >> manually triggered "batch page replacement" using yardstick (but I'm not > >> sure if ducktape can help here). > >> > > >> >I think we should carefully describe the issues with the current > >> approach and then we can choose right tool to benchmark improvements. > >> >You said: > >> > > >> >> we use Random-LRU algorithm … it has many disadvantages and affects > >> performance very much when replacement is started > >> > > >> >Can you list disadvantages of the Random-LRU? > >> > > >> >AFAIU the first benchmark should be: > >> > > >> >1. Start cluster with persistence and put data bigger then available > RAM > >> to it. > >> >2. Measure performance of the queries that selects one entry from the > >> cache. > >> >3. Make some queries that will iterate throw all data - `SELECT SUM(x) > >> FROM t` or something similar. > >> >4. Repeat step 2. in this time performance of random queries should be > >> lower due to the page replacement. > >> > > >> >Is this scenario correct? > >> > > >> >> 23 нояб. 2020 г., в 09:12, Alex Plehanov < plehanov.a...@gmail.com > > >> написал(а): > >> >> > >> >> Nikolay, Zhenya, > >> >> > >> >> Benchmark from IGNITE-13034 is fully synthetic, it makes random puts > >> >> uniformly. It can be used to compare different page replacement > >> algorithms > >> >> (random-LRU vs segmented-LRU), but it is totally inapplicable to > >> benchmark > >> >> batch page replacement. > >> >> Perhaps we can implement a special benchmark for this case with > >> manually > >> >> triggered "batch page replacement" using yardstick (but I'm not sure > >> >> if ducktape can help here). > >> >> > >> >>> I understand case you described, but who will pull the switch ? > Human, > >> >> artificial intelligence ? > >> >> As I described before, we can implement both manual and automatic > >> "batch > >> >> page replacement" triggering. For automatic triggering, there is no > >> >> artificial intelligence needed, just several conditions with > reasonable > >> >> thresholds. Automatic triggering also can be disabled by default. > >> >> > >> >> пт, 20 нояб. 2020 г. в 13:32, Zhenya Stanilovsky < > >> arzamas...@mail.ru.invalid > >> >>> : > >> >> > >> >>> > >> >>> > >> >>> > >> >>> > >> >>> > >> >>> > >> >>>> Zhenya, > >> >>>> > >> >>>>> Alexey, we already have changes that partially fixes this issue > [1] > >> >>>> IGNITE-13086 it's a minor improvement. We still have major problems > >> with > >> >>>> our page replacement algorithm (slow page selection and non-optimal > >> >>>> page-fault rate). I think changing from random 5 pages to 7 will > make > >> >>>> things even worse (it's better for page-fault rate, but page > >> selection > >> >>> will > >> >>>> be slower). > >> >>> All this words above need to be proven, i hope. + 1 with Nikolay, we > >> need > >> >>> correct reproduces or some graphs from 2.9 ver. > >> >>> > >> >>>> > >> >>>>> This approach still not applicable for real life > >> >>>> Why do you think batch replacement is not applicable for real-life? > >> It can > >> >>>> be applied for workloads, where some big amount of data > periodically > >> used, > >> >>>> but not very often. For example, when OLAP request over historical > >> data > >> >>>> raised pages to page-memory, and after such request this data is > not > >> >>> needed > >> >>>> for a long time. Or when OLTP transactions mostly add new data and > >> process > >> >>>> recent data but rarely touch historical data. In these cases with > the > >> >>>> current approach, we will enter "page replacement mode" after some > >> period > >> >>>> of time and never leave it. With batch page replacement there is a > >> chance > >> >>>> to prevent random-LRU page replacement or postpone it. > >> >>> I understand case you described, but who will pull the switch ? > Human, > >> >>> artificial intelligence ? > >> >>> You approach assume some triggering from inner, i don`t like this. > >> >>> > >> >>>> > >> >>>>> But request once more, do you really observe such problems with > 2.9 > >> ver > >> >>> ? > >> >>>> Any graphs maybe ? > >> >>>> I don't have production usage feedback after IGNITE-13086, but I > >> doubt > >> >>>> something changed significantly. > >> >>> > >> >>> Lets wait ?:) In any case (Nikolay, Alex) IGNITE-13086 includes > >> yardstik > >> >>> bench for PR proven, we can use it once more. > >> >>> > >> >>> Thanks ! > >> >>>> > >> >>>> > >> >>>> чт, 19 нояб. 2020 г. в 09:18, Zhenya Stanilovsky < > >> >>> arzamas...@mail.ru.invalid > >> >>>>> : > >> >>>> > >> >>>>> > >> >>>>> Alexey, we already have changes that partially fixes this issue > [1] > >> >>>>> Easy way: > >> >>>>> Looks like we already have converge in page replacement. > >> >>>>> If we change 5 times touch iterator from random lru algo into, for > >> >>>>> example — 7 we will obtain fast improvement from scratch. > >> >>>>> > >> >>>>> » Batch page replacement > >> >>>>> This approach still not applicable for real life if you wan`t to > >> observe > >> >>>>> ugly people for threshold (i.e. 12 h) interval. And, of course, > you > >> >>>>> understand that dramatically reduce of such interval gives > nothing? > >> >>>>> > >> >>>>> » Change the page replacement algorithm. > >> >>>>> That`s way i vote for ) But request once more, do you really > observe > >> >>> such > >> >>>>> problems with 2.9 ver ? Any graphs maybe ? > >> >>>>> > >> >>>>> thanks ! > >> >>>>> > >> >>>>> [1] https://issues.apache.org/jira/browse/IGNITE-13086 > >> >>>>>> Hello, Igniters! > >> >>>>>> > >> >>>>>> Currently, for page replacement (page rotation between > page-memory > >> and > >> >>>>>> disk) we use Random-LRU algorithm. It has a low maintenance cost > >> and > >> >>>>>> relatively simple implementation, but it has many disadvantages > and > >> >>>>> affects > >> >>>>>> performance very much when replacement is started. We even have > >> >>> warnings > >> >>>>> in > >> >>>>>> the log when page replacement started and a special event for > >> this. I > >> >>> know > >> >>>>>> Ignite deployments where administrators force to restart cluster > >> nodes > >> >>>>>> periodically to avoid page replacement. > >> >>>>>> > >> >>>>>> I have a couple of proposals to improve page replacement in > Ignite: > >> >>>>>> > >> >>>>>> *Batch page replacement.* > >> >>>>>> > >> >>>>>> Main idea: in some cases start background task to evict cold > pages > >> from > >> >>>>>> page-memory (for example, pages, last touched more than 12 hours > >> ago). > >> >>>>>> > >> >>>>>> The task can be started: > >> >>>>>> - Automatically, triggered by some events, for example, when we > >> expect > >> >>> a > >> >>>>>> start of Random-LRU page replacing soon (allocated more than 90% > of > >> >>>>>> page-memory) + we have enough amount of cold pages (we need some > >> >>> metric to > >> >>>>>> calculate the number of cold pages) + some time passed since last > >> batch > >> >>>>>> page replacement (to avoid too much resource consumption by > >> background > >> >>>>>> batch replacement). > >> >>>>>> - Manually (JMX or control.sh), if an administrator wants to > >> control > >> >>> the > >> >>>>>> time of batch replacement more precisely (for example, to avoid > the > >> >>> start > >> >>>>>> of this task during peak time). > >> >>>>>> > >> >>>>>> Batch page replacement will be helpful in some workloads (when > some > >> >>> data > >> >>>>>> much colder than another), it can prevent the starting of > >> Random-LRU > >> >>> page > >> >>>>>> replacement, or if Random-LRU already started it can provide > >> >>> conditions to > >> >>>>>> stop it. > >> >>>>>> > >> >>>>>> *Change the page replacement algorithm.* > >> >>>>>> > >> >>>>>> Good page replacement algorithm should satisfy the requirements: > >> >>>>>> - low page-fault rates for typical workload > >> >>>>>> - low maintenance cost (low resource consumption to maintain > >> additional > >> >>>>>> structures required for page replacement) > >> >>>>>> - fast searching of next page for replacement > >> >>>>>> - sequential scans resistance (one sequential scan should not > >> evict all > >> >>>>>> relatively hot pages from page-memory) > >> >>>>>> > >> >>>>>> Our Random-LRU has low maintenance cost and sequential scan > >> resistant, > >> >>> but > >> >>>>>> to find the next page for replacement in the best case we scan 5 > >> >>> pages, in > >> >>>>>> the worst case we can scan all data region segment. Also, due to > >> random > >> >>>>>> nature, it's not very effective in predicting the right page for > >> >>>>>> replacement to minimize the page-fault rate. And it's much time > >> >>> required > >> >>>>> to > >> >>>>>> totally evict old cold data. > >> >>>>>> > >> >>>>>> Usually, database management systems and operating systems use > >> >>>>>> modifications of LRU algorithms. These algorithms have higher > >> >>> maintenance > >> >>>>>> costs (pages list should be modified on each page access), but > >> often > >> >>> they > >> >>>>>> are effective from a "page-fault rate" point of view and have > O(1) > >> >>>>>> complexity for a searching page to replace. Simple LRU is not > >> >>> sequential > >> >>>>>> scan resistant, but modifications that utilize page access > >> frequency > >> >>> are > >> >>>>>> resistant to sequential scan. > >> >>>>>> > >> >>>>>> We can try one of the modifications of LRU as well (for example, > >> >>>>> "segmented > >> >>>>>> LRU" seems suitable for Ignite). > >> >>>>>> > >> >>>>>> Ignite is a memory-centric product, so "low maintenance cost" is > >> very > >> >>>>>> critical. And there is a risk that page replacement algorithm can > >> >>> affect > >> >>>>>> workloads, where page replacement is not used (enough RAM to > store > >> all > >> >>>>>> data). Of course, any page replacement solution should be > carefully > >> >>>>>> benchmarked. > >> >>>>>> > >> >>>>>> > >> >>>>>> Igniters, WDYT? If any of these proposals look reasonable to > you, I > >> >>> will > >> >>>>>> create IEP and start implementation. > >> >>>>>> > >> >>>>>> Also, I have a draft implementation of system view to determine > >> how hot > >> >>>>> are > >> >>>>>> pages in page-memory [1]. I think it will be useful for any of > >> these > >> >>>>>> approaches (and even if we decide to left page replacement as > is). > >> >>>>>> > >> >>>>>> [1]: https://issues.apache.org/jira/browse/IGNITE-13726 > >> >>>>>> > >> >>>>> > >> >>>>> > >> >>>>> > >> >>>>> > >> >>>> > >> >>> > >> >>> > >> >>> > >> >>> > >> > > >> > >> > >> > >> > > > > >
