At Thu, 07 Apr 2022 14:14:59 +0300, Yura Sokolov <y.soko...@postgrespro.ru> wrote in > В Чт, 07/04/2022 в 16:55 +0900, Kyotaro Horiguchi пишет: > > Hi, Yura. > > > > At Wed, 06 Apr 2022 16:17:28 +0300, Yura Sokolov <y.soko...@postgrespro.ru> > > wrot > > e in > > > Ok, I got access to stronger server, did the benchmark, found weird > > > things, and so here is new version :-) > > > > Thanks for the new version and benchmarking. > > > > > First I found if table size is strictly limited to NBuffers and FIXED, > > > then under high concurrency get_hash_entry may not find free entry > > > despite it must be there. It seems while process scans free lists, other > > > concurrent processes "moves etry around", ie one concurrent process > > > fetched it from one free list, other process put new entry in other > > > freelist, and unfortunate process missed it since it tests freelists > > > only once. > > > > StrategyGetBuffer believes that entries don't move across freelists > > and it was true before this patch. > > StrategyGetBuffer knows nothing about dynahash's freelist. > It knows about buffer manager's freelist, which is not partitioned.
Yeah, right. I meant get_hash_entry. > > > To fix this issues I made following: > > > > > > # Concurrency > > > > > > First, I limit concurrency by introducing other lwlocks tranche - > > > BufferEvict. It is 8 times larger than BufferMapping tranche (1024 vs > > > 128). > > > If backend doesn't find buffer in buffer table and wants to introduce > > > it, it first calls > > > LWLockAcquireOrWait(newEvictPartitionLock, LW_EXCLUSIVE) > > > If lock were acquired, then it goes to eviction and replace process. > > > Otherwise, it waits lock to be released and repeats search. > > > > > > This greately improve performance for > 400 clients in pgbench. > > > > So the performance difference between the existing code and v11 is the > > latter has a collision cross section eight times smaller than the > > former? > > No. Acquiring EvictPartitionLock > 1. doesn't block readers, since readers doesn't acquire EvictPartitionLock > 2. doesn't form "tree of lock dependency" since EvictPartitionLock is > independent from PartitionLock. > > Problem with existing code: > 1. Process A locks P1 and P2 > 2. Process B (p3-old, p1-new) locks P3 and wants to lock P1 > 3. Process C (p4-new, p1-old) locks P4 and wants to lock P1 > 4. Process D (p5-new, p4-old) locks P5 and wants to lock P4 > At this moment locks P1, P2, P3, P4 and P5 are all locked and waiting > for Process A. > And readers can't read from same five partitions. > > With new code: > 1. Process A locks E1 (evict partition) and locks P2, > then releases P2 and locks P1. > 2. Process B tries to locks E1, waits and retries search. > 3. Process C locks E4, locks P1, then releases P1 and locks P4 > 4. Process D locks E5, locks P4, then releases P4 and locks P5 > So, there is no network of locks. > Process A doesn't block Process D in any moment: > - either A blocks C, but C doesn't block D at this moment > - or A doesn't block C. > And readers doesn't see simultaneously locked five locks which > depends on single Process A. Thansk for the detailed explanation. I see that. > > + * Prevent "thundering herd" problem and limit concurrency. > > > > this is something like pressing accelerator and break pedals at the > > same time. If it improves performance, just increasing the number of > > buffer partition seems to work? > > To be honestly: of cause simple increase of NUM_BUFFER_PARTITIONS > does improve average case. > But it is better to cure problem than anesthetize. > Increase of > NUM_BUFFER_PARTITIONS reduces probability and relative > weight of lock network, but doesn't eliminate. Agreed. > > It's also not great that follower backends runs a busy loop on the > > lock until the top-runner backend inserts the new buffer to the > > buftable then releases the newParititionLock. > > > > > I tried other variant as well: > > > - first insert entry with dummy buffer index into buffer table. > > > - if such entry were already here, then wait it to be filled. > > > - otherwise find victim buffer and replace dummy index with new one. > > > Wait were done with shared lock on EvictPartitionLock as well. > > > This variant performed quite same. > > > > This one looks better to me. Since a partition can be shared by two or > > more new-buffers, condition variable seems to work better here... > > > > > Logically I like that variant more, but there is one gotcha: > > > FlushBuffer could fail with elog(ERROR). Therefore then there is > > > a need to reliable remove entry with dummy index. > > > > Perhaps UnlockBuffers can do that. > > Thanks for suggestion. I'll try to investigate and retry this way > of patch. > > > > And after all, I still need to hold EvictPartitionLock to notice > > > waiters. > > > I've tried to use ConditionalVariable, but its performance were much > > > worse. > > > > How many CVs did you use? > > I've tried both NUM_PARTITION_LOCKS and NUM_PARTITION_LOCKS*8. > It doesn't matter. > Looks like use of WaitLatch (which uses epoll) and/or tripple > SpinLockAcquire per good case (with two list traversing) is much worse > than PgSemaphorLock (which uses futex) and single wait list action. Sure. I unintentionally neglected the overhead of our CV implementation. It cannot be used in such a hot path. > Other probability is while ConditionVariable eliminates thundering > nerd effect, it doesn't limit concurrency enough... but that's just > theory. > > In reality, I'd like to try to make BufferLookupEnt->id to be atomic > and add LwLock to BufferLookupEnt. I'll test it, but doubt it could > be merged, since there is no way to initialize dynahash's entries > reliably. Yeah, that's what came to my mind first (but with not a LWLock but a CV) but gave up for the reason of additional size. The size of BufferLookupEnt is 24 and sizeof(ConditionVariable) is 12. By the way sizeof(LWLock) is 16.. So I think we don't take the per-bufentry approach here for the reason of additional memory usage. > > I don't think that causes significant performance hit, but I don't > > understand how it improves freelist hit ratio other than by accident. > > Could you have some reasoning for it? > > Since free_reused_entry returns entry into random free_list, this > probability is quite high. In tests, I see stabilisa Maybe. Doesn't it improve the efficiency if we prioritize emptied freelist on returning an element? I tried it with an atomic_u32 to remember empty freelist. On the uin32, each bit represents a freelist index. I saw it eliminated calls to element_alloc. I tried to remember a single freelist index in an atomic but there was a case where two freelists are emptied at once and that lead to element_alloc call. > > By the way the change of get_hash_entry looks something wrong. > > > > If I understand it correctly, it visits num_freelists/4 freelists at > > once, then tries element_alloc. If element_alloc() fails (that must > > happen), it only tries freeList[freelist_idx] and gives up, even > > though there must be an element in other 3/4 freelists. > > No. If element_alloc fails, it tries all NUM_FREELISTS again. > - condition: `ntries || !allocFailed`. `!allocFailed` become true, > so `ntries` remains. > - `ntries = num_freelists;` regardless of `allocFailed`. > Therefore, all `NUM_FREELISTS` are retried for partitioned table. Ah, okay. ntries is set to num_freelists after calling element_alloc. I think we (I?) need more comments. By the way, why it is num_freelists / 4 + 1? > > > `free_reused_entry` now returns entry to random position. It flattens > > > free entry's spread. Although it is not enough without other changes > > > (thundering herd mitigation and probing more lists in get_hash_entry). > > > > If "thudering herd" means "many backends rush trying to read-in the > > same page at once", isn't it avoided by the change in BufferAlloc? > > "thundering herd" reduces speed of entries migration a lot. But > `simple_select` benchmark is too biased: looks like btree root is > evicted from time to time. So entries are slowly migrated to of from > freelist of its partition. > Without "thundering herd" fix this migration is very fast. Ah, that observation agree with the seemingly unidirectional migration of free entries. I remember that it is raised in this list several times to prioritize index pages in shared buffers.. > > Up to about 15%(?) of gain is great. > > Up to 35% in "2 socket 3 key 1GB" case. > Up to 44% in "2 socket 1 key 128MB" case. Oh, more great! > > I'm not sure it is okay that it seems to slow by about 1%.. > > Well, in fact some degradation is not reproducible. > Surprisingly, results change a bit from time to time. Yeah. > I just didn't rerun whole `master` branch bench again > after v11 bench, since each whole test run costs me 1.5 hour. Thans for the labor. > But I confirm regression on "1 socket 1 key 1GB" test case > between 83 and 211 connections. It were reproducible on > more powerful Xeon 8354H, although it were less visible. > > Other fluctuations close to 1% are not reliable. I'm glad to hear that. It is not surprising that some fluctuation happens. > For example, sometimes I see degradation or improvement with > 2GB shared buffers (and even more than 1%). But 2GB is enough > for whole test dataset (scale 100 pgbench is 1.5GB on disk). > Therefore modified code is not involved in benchmarking at all. > How it could be explained? > That is why I don't post 2GB benchmark results. (yeah, I'm > cheating a bit). If buffer replacement doesn't happen, theoretically this patch cannot be involved in the fluctuation. I think we can consider it an error. It might come from placement of other variables. I have somethimes got annoyed by such small but steady change of performance that persists until I recompiled the whole tree. But, sorry, I don't have a clear idea of how such performance shift happens.. regards. -- Kyotaro Horiguchi NTT Open Source Software Center
