public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v47 2/7] Add conditional lock feature to dshash 3+ messages / 3 participants [nested] [flat]
* [PATCH v47 2/7] Add conditional lock feature to dshash @ 2020-03-13 07:58 Kyotaro Horiguchi <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Kyotaro Horiguchi @ 2020-03-13 07:58 UTC (permalink / raw) Dshash currently waits for lock unconditionally. It is inconvenient when we want to avoid being blocked by other processes. This commit adds alternative functions of dshash_find and dshash_find_or_insert that allows immediate return on lock failure. --- src/backend/lib/dshash.c | 98 +++++++++++++++++++++------------------- src/include/lib/dshash.h | 3 ++ 2 files changed, 55 insertions(+), 46 deletions(-) diff --git a/src/backend/lib/dshash.c b/src/backend/lib/dshash.c index 520bfa0979..853d78b528 100644 --- a/src/backend/lib/dshash.c +++ b/src/backend/lib/dshash.c @@ -383,6 +383,10 @@ dshash_get_hash_table_handle(dshash_table *hash_table) * the caller must take care to ensure that the entry is not left corrupted. * The lock mode is either shared or exclusive depending on 'exclusive'. * + * If found is not NULL, *found is set to true if the key is found in the hash + * table. If the key is not found, *found is set to false and a pointer to a + * newly created entry is returned. + * * The caller must not lock a lock already. * * Note that the lock held is in fact an LWLock, so interrupts will be held on @@ -392,36 +396,7 @@ dshash_get_hash_table_handle(dshash_table *hash_table) void * dshash_find(dshash_table *hash_table, const void *key, bool exclusive) { - dshash_hash hash; - size_t partition; - dshash_table_item *item; - - hash = hash_key(hash_table, key); - partition = PARTITION_FOR_HASH(hash); - - Assert(hash_table->control->magic == DSHASH_MAGIC); - Assert(!hash_table->find_locked); - - LWLockAcquire(PARTITION_LOCK(hash_table, partition), - exclusive ? LW_EXCLUSIVE : LW_SHARED); - ensure_valid_bucket_pointers(hash_table); - - /* Search the active bucket. */ - item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash)); - - if (!item) - { - /* Not found. */ - LWLockRelease(PARTITION_LOCK(hash_table, partition)); - return NULL; - } - else - { - /* The caller will free the lock by calling dshash_release_lock. */ - hash_table->find_locked = true; - hash_table->find_exclusively_locked = exclusive; - return ENTRY_FROM_ITEM(item); - } + return dshash_find_extended(hash_table, key, exclusive, false, false, NULL); } /* @@ -439,31 +414,60 @@ dshash_find_or_insert(dshash_table *hash_table, const void *key, bool *found) { - dshash_hash hash; - size_t partition_index; - dshash_partition *partition; + return dshash_find_extended(hash_table, key, true, false, true, found); +} + + +/* + * Find the key in the hash table. + * + * "exclusive" is the lock mode in which the partition for the returned item + * is locked. If "nowait" is true, the function immediately returns if + * required lock was not acquired. "insert" indicates insert mode. In this + * mode new entry is inserted and set *found to false. *found is set to true if + * found. "found" must be non-null in this mode. + */ +void * +dshash_find_extended(dshash_table *hash_table, const void *key, + bool exclusive, bool nowait, bool insert, bool *found) +{ + dshash_hash hash = hash_key(hash_table, key); + size_t partidx = PARTITION_FOR_HASH(hash); + dshash_partition *partition = &hash_table->control->partitions[partidx]; + LWLockMode lockmode = exclusive ? LW_EXCLUSIVE : LW_SHARED; dshash_table_item *item; - hash = hash_key(hash_table, key); - partition_index = PARTITION_FOR_HASH(hash); - partition = &hash_table->control->partitions[partition_index]; - - Assert(hash_table->control->magic == DSHASH_MAGIC); - Assert(!hash_table->find_locked); + /* must be exclusive when insert allowed */ + Assert(!insert || (exclusive && found != NULL)); restart: - LWLockAcquire(PARTITION_LOCK(hash_table, partition_index), - LW_EXCLUSIVE); + if (!nowait) + LWLockAcquire(PARTITION_LOCK(hash_table, partidx), lockmode); + else if (!LWLockConditionalAcquire(PARTITION_LOCK(hash_table, partidx), + lockmode)) + return NULL; + ensure_valid_bucket_pointers(hash_table); /* Search the active bucket. */ item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash)); if (item) - *found = true; + { + if (found) + *found = true; + } else { - *found = false; + if (found) + *found = false; + + if (!insert) + { + /* The caller didn't told to add a new entry. */ + LWLockRelease(PARTITION_LOCK(hash_table, partidx)); + return NULL; + } /* Check if we are getting too full. */ if (partition->count > MAX_COUNT_PER_PARTITION(hash_table)) @@ -479,7 +483,8 @@ restart: * Give up our existing lock first, because resizing needs to * reacquire all the locks in the right order to avoid deadlocks. */ - LWLockRelease(PARTITION_LOCK(hash_table, partition_index)); + LWLockRelease(PARTITION_LOCK(hash_table, partidx)); + resize(hash_table, hash_table->size_log2 + 1); goto restart; @@ -493,12 +498,13 @@ restart: ++partition->count; } - /* The caller must release the lock with dshash_release_lock. */ + /* The caller will free the lock by calling dshash_release_lock. */ hash_table->find_locked = true; - hash_table->find_exclusively_locked = true; + hash_table->find_exclusively_locked = exclusive; return ENTRY_FROM_ITEM(item); } + /* * Remove an entry by key. Returns true if the key was found and the * corresponding entry was removed. diff --git a/src/include/lib/dshash.h b/src/include/lib/dshash.h index a6ea377173..5b8114d041 100644 --- a/src/include/lib/dshash.h +++ b/src/include/lib/dshash.h @@ -91,6 +91,9 @@ extern void *dshash_find(dshash_table *hash_table, const void *key, bool exclusive); extern void *dshash_find_or_insert(dshash_table *hash_table, const void *key, bool *found); +extern void *dshash_find_extended(dshash_table *hash_table, const void *key, + bool exclusive, bool nowait, bool insert, + bool *found); extern bool dshash_delete_key(dshash_table *hash_table, const void *key); extern void dshash_delete_entry(dshash_table *hash_table, void *entry); extern void dshash_release_lock(dshash_table *hash_table, void *entry); -- 2.27.0 ----Next_Part(Thu_Jan_21_12_03_48_2021_284)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v47-0003-Make-archiver-process-an-auxiliary-process.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* Commit Timestamp and LSN Inversion issue @ 2024-09-04 06:53 shveta malik <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: shveta malik @ 2024-09-04 06:53 UTC (permalink / raw) To: pgsql-hackers; +Cc: Amit Kapila <[email protected]>; Zhijie Hou (Fujitsu) <[email protected]>; shveta malik <[email protected]>; [email protected] Hello hackers, (Cc people involved in the earlier discussion) I would like to discuss the $Subject. While discussing Logical Replication's Conflict Detection and Resolution (CDR) design in [1] , it came to our notice that the commit LSN and timestamp may not correlate perfectly i.e. commits may happen with LSN1 < LSN2 but with Ts1 > Ts2. This issue may arise because, during the commit process, the timestamp (xactStopTimestamp) is captured slightly earlier than when space is reserved in the WAL. ~~ Reproducibility of conflict-resolution problem due to the timestamp inversion ------------------------------------------------ It was suggested that timestamp inversion *may* impact the time-based resolutions such as last_update_wins (targeted to be implemented in [1]) as we may end up making wrong decisions if timestamps and LSNs are not correctly ordered. And thus we tried some tests but failed to find any practical scenario where it could be a problem. Basically, the proposed conflict resolution is a row-level resolution, and to cause the row value to be inconsistent, we need to modify the same row in concurrent transactions and commit the changes concurrently. But this doesn't seem possible because concurrent updates on the same row are disallowed (e.g., the later update will be blocked due to the row lock). See [2] for the details. We tried to give some thoughts on multi table cases as well e.g., update table A with foreign key and update the table B that table A refers to. But update on table A will block the update on table B as well, so we could not reproduce data-divergence due to the LSN/timestamp mismatch issue there. ~~ Idea proposed to fix the timestamp inversion issue ------------------------------------------------ There was a suggestion in [3] to acquire the timestamp while reserving the space (because that happens in LSN order). The clock would need to be monotonic (easy enough with CLOCK_MONOTONIC), but also cheap. The main problem why it's being done outside the critical section, because gettimeofday() may be quite expensive. There's a concept of hybrid clock, combining "time" and logical counter, which might be useful independently of CDR. On further analyzing this idea, we found that CLOCK_MONOTONIC can be accepted only by clock_gettime() which has more precision than gettimeofday() and thus is equally or more expensive theoretically (we plan to test it and post the results). It does not look like a good idea to call any of these when holding spinlock to reserve the wal position. As for the suggested solution "hybrid clock", it might not help here because the logical counter is only used to order the transactions with the same timestamp. The problem here is how to get the timestamp along with wal position reservation(ReserveXLogInsertLocation). ~~ We can explore further but as we are not able to see any real-time scenario where this could actually be problem, it may or may not be worth to spend time on this. Thoughts? [1]: (See: "How is this going to deal with the fact that commit LSN and timestamps may not correlate perfectly?"). https://www.postgresql.org/message-id/CAJpy0uBWBEveM8LO2b7wNZ47raZ9tVJw3D2_WXd8-b6LSqP6HA%40mail.gma... [2]: https://www.postgresql.org/message-id/CAA4eK1JTMiBOoGqkt%3DaLPLU8Rs45ihbLhXaGHsz8XC76%2BOG3%2BQ%40ma... [3]: (See: "The clock would need to be monotonic (easy enough with CLOCK_MONOTONIC"). https://www.postgresql.org/message-id/a3a70a19-a35e-426c-8646-0898cdc207c8%40enterprisedb.com thanks Shveta ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Commit Timestamp and LSN Inversion issue @ 2024-09-09 06:11 Nisha Moond <[email protected]> parent: shveta malik <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Nisha Moond @ 2024-09-09 06:11 UTC (permalink / raw) To: shveta malik <[email protected]>; +Cc: pgsql-hackers; Amit Kapila <[email protected]>; Zhijie Hou (Fujitsu) <[email protected]>; [email protected] On Wed, Sep 4, 2024 at 12:23 PM shveta malik <[email protected]> wrote: > > Hello hackers, > (Cc people involved in the earlier discussion) > > I would like to discuss the $Subject. > > While discussing Logical Replication's Conflict Detection and > Resolution (CDR) design in [1] , it came to our notice that the > commit LSN and timestamp may not correlate perfectly i.e. commits may > happen with LSN1 < LSN2 but with Ts1 > Ts2. This issue may arise > because, during the commit process, the timestamp (xactStopTimestamp) > is captured slightly earlier than when space is reserved in the WAL. > > ~~ > > Reproducibility of conflict-resolution problem due to the timestamp inversion > ------------------------------------------------ > It was suggested that timestamp inversion *may* impact the time-based > resolutions such as last_update_wins (targeted to be implemented in > [1]) as we may end up making wrong decisions if timestamps and LSNs > are not correctly ordered. And thus we tried some tests but failed to > find any practical scenario where it could be a problem. > > Basically, the proposed conflict resolution is a row-level resolution, > and to cause the row value to be inconsistent, we need to modify the > same row in concurrent transactions and commit the changes > concurrently. But this doesn't seem possible because concurrent > updates on the same row are disallowed (e.g., the later update will be > blocked due to the row lock). See [2] for the details. > > We tried to give some thoughts on multi table cases as well e.g., > update table A with foreign key and update the table B that table A > refers to. But update on table A will block the update on table B as > well, so we could not reproduce data-divergence due to the > LSN/timestamp mismatch issue there. > > ~~ > > Idea proposed to fix the timestamp inversion issue > ------------------------------------------------ > There was a suggestion in [3] to acquire the timestamp while reserving > the space (because that happens in LSN order). The clock would need to > be monotonic (easy enough with CLOCK_MONOTONIC), but also cheap. The > main problem why it's being done outside the critical section, because > gettimeofday() may be quite expensive. There's a concept of hybrid > clock, combining "time" and logical counter, which might be useful > independently of CDR. > > On further analyzing this idea, we found that CLOCK_MONOTONIC can be > accepted only by clock_gettime() which has more precision than > gettimeofday() and thus is equally or more expensive theoretically (we > plan to test it and post the results). It does not look like a good > idea to call any of these when holding spinlock to reserve the wal > position. As for the suggested solution "hybrid clock", it might not > help here because the logical counter is only used to order the > transactions with the same timestamp. The problem here is how to get > the timestamp along with wal position > reservation(ReserveXLogInsertLocation). > Here are the tests done to compare clock_gettime() and gettimeofday() performance. Machine details : Intel(R) Xeon(R) CPU E7-4890 v2 @ 2.80GHz CPU(s): 120; 800GB RAM Three functions were tested across three different call volumes (1 million, 100 million, and 1 billion): 1) clock_gettime() with CLOCK_REALTIME 2) clock_gettime() with CLOCK_MONOTONIC 3) gettimeofday() --> clock_gettime() with CLOCK_MONOTONIC sometimes shows slightly better performance, but not consistently. The difference in time taken by all three functions is minimal, with averages varying by no more than ~2.5%. Overall, the performance between CLOCK_MONOTONIC and gettimeofday() is essentially the same. Below are the test results - (each test was run twice for consistency) 1) For 1 million calls: 1a) clock_gettime() with CLOCK_REALTIME: - Run 1: 0.01770 seconds, Run 2: 0.01772 seconds, Average: 0.01771 seconds. 1b) clock_gettime() with CLOCK_MONOTONIC: - Run 1: 0.01753 seconds, Run 2: 0.01748 seconds, Average: 0.01750 seconds. 1c) gettimeofday(): - Run 1: 0.01742 seconds, Run 2: 0.01777 seconds, Average: 0.01760 seconds. 2) For 100 million calls: 2a) clock_gettime() with CLOCK_REALTIME: - Run 1: 1.76649 seconds, Run 2: 1.76602 seconds, Average: 1.76625 seconds. 2b) clock_gettime() with CLOCK_MONOTONIC: - Run 1: 1.72768 seconds, Run 2: 1.72988 seconds, Average: 1.72878 seconds. 2c) gettimeofday(): - Run 1: 1.72436 seconds, Run 2: 1.72174 seconds, Average: 1.72305 seconds. 3) For 1 billion calls: 3a) clock_gettime() with CLOCK_REALTIME: - Run 1: 17.63859 seconds, Run 2: 17.65529 seconds, Average: 17.64694 seconds. 3b) clock_gettime() with CLOCK_MONOTONIC: - Run 1: 17.15109 seconds, Run 2: 17.27406 seconds, Average: 17.21257 seconds. 3c) gettimeofday(): - Run 1: 17.21368 seconds, Run 2: 17.22983 seconds, Average: 17.22175 seconds. ~~~~ Attached the scripts used for tests. -- Thanks, Nisha Attachments: [application/x-zip-compressed] clock_gettime_test.zip (2.0K, ../../CABdArM71Q6GYMBs19c_dVrwLub3CsaFNmR9Orf5c-agG6W1xFA@mail.gmail.com/2-clock_gettime_test.zip) download ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-09-09 06:11 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-03-13 07:58 [PATCH v47 2/7] Add conditional lock feature to dshash Kyotaro Horiguchi <[email protected]> 2024-09-04 06:53 Commit Timestamp and LSN Inversion issue shveta malik <[email protected]> 2024-09-09 06:11 ` Re: Commit Timestamp and LSN Inversion issue Nisha Moond <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox