How does the partitioned lock manager works?

Hi,
When the lock manager's data structures were split into "partitions",
how many such data structures can one partition control? Since we use
LOCKTAG's hash value to decide the partition which the lock should in, can
all locks be split into ONE partition?

Regards,
ranc.

rancpine cui wrote:
> When the lock manager's data structures were split into "partitions",
> how many such data structures can one partition control?

The number of partitions is 16 (NUM_LOCK_PARTITIONS). The total size of
the lock hash table is max_locks_per_xact * (max_connections +
max_prepared_xacts). So the number of "lock slots" per partition is
(max_locks_per_xact * (max_connections +
max_prepared_xacts))/NUM_LOCK_PARTITIONS.

> Since we use
> LOCKTAG's hash value to decide the partition which the lock should in, can
> all locks be split into ONE partition?

In theory, yes. It's extremely unlikely to happen in practice.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

---------- Forwarded message ----------
From: rancpine cui <rancpine(at)gmail(dot)com>
Date: 2007-4-27 下午9:22
Subject: Re: [HACKERS] How does the partitioned lock manager works?
To: Heikki Linnakangas <heikki(at)enterprisedb(dot)com>

Thanks for your reply. :-)
I've seen from the README that
"The shared-memory hash tables for LOCKs and PROCLOCKs are organized
so that different partitions use different hash chains, and thus there
is no conflict in working with objects in different partitions."
What does "hash chains" mean?
As the dynahash.c's "partitioned table" mechanism suggests, a lock's
bucket number can be calculated from its hash value, then it will be
inserted into that bucket,so how does partition number works?
Is it only a flag which suggests the partition the lock belongs to when
we want to use that lock? I can't find a way to manage locks via
partition...

rancpine cui escribió:

> I've seen from the README that
> "The shared-memory hash tables for LOCKs and PROCLOCKs are organized
> so that different partitions use different hash chains, and thus there
> is no conflict in working with objects in different partitions."
> What does "hash chains" mean?

Each "hash chain" is a different, separate, independent hash struct.

> As the dynahash.c's "partitioned table" mechanism suggests, a lock's
> bucket number can be calculated from its hash value, then it will be
> inserted into that bucket,so how does partition number works?

Which hash is used depends on the partition number.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
> rancpine cui escribi:
>> What does "hash chains" mean?

> Each "hash chain" is a different, separate, independent hash struct.

It's pretty much equivalent to "hash bucket" --- this comment says chain
because it's focusing on the physical representation of the bucket as a
linked list, whereas "bucket" doesn't presume anything about how the
elements in the bucket are stored.

regards, tom lane

2007/4/27, Alvaro Herrera <alvherre(at)commandprompt(dot)com>:
>
>
> Which hash is used depends on the partition number.

So the method of calculating the bucket number can promise
that all items in the bucket link list belong to ONE partition?

"rancpine cui" <rancpine(at)gmail(dot)com> writes:
> So the method of calculating the bucket number can promise
> that all items in the bucket link list belong to ONE partition?

It's not that hard: the bucket number is some number of low-order bits
of the hash value, and the partition number is some smaller (or at most
equal) number of low-order bits of the hash value.

regards, tom lane

Ah... It seems that a item is calculated its hash value, get the bucket
number from it and insert into that bucket "chain". The insertion has
nothing to do with partition number(but Alvaro says "which hash is
used depends on the partition number". I haven't really understood
this: how can we get a hash value without deciding which hash to
use? ). However, when we travel along a chain to get a item, we can
infer its partition number from its hash value.

My problem is, I'm not so sure about the process stated above,
because in that way, items in ONE chain may belong to different
partitions,and it is obviously conflicted with "so that different
partitions use different hash chains" as README mentioned.

2007/4/28, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>:

> It's not that hard: the bucket number is some number of low-order bits
> of the hash value, and the partition number is some smaller (or at most
> equal) number of low-order bits of the hash value.
>
> regards, tom lane
>

Insertion algorithm in a nutshell:

1. Calculate hash value
2. Take 4 least-significant bits of the hash value. These tell you which
partition the value belongs to.
3. Lock that partition
4. Take the X (X > 4) least significant bits of the hash value. These
tell you which hash bucket the value belongs to.
5. Add value to that hash bucket. A bucket is implemented as a linked
list. Also called a "hash chain" in the README.
6. Unlock partition

Cui Shijun wrote:
> Ah... It seems that a item is calculated its hash value, get the bucket
> number from it and insert into that bucket "chain". The insertion has
> nothing to do with partition number(but Alvaro says "which hash is
> used depends on the partition number". I haven't really understood
> this: how can we get a hash value without deciding which hash to
> use? ). However, when we travel along a chain to get a item, we can
> infer its partition number from its hash value.
>
> My problem is, I'm not so sure about the process stated above,
> because in that way, items in ONE chain may belong to different
> partitions,and it is obviously conflicted with "so that different
> partitions use different hash chains" as README mentioned.
>
> 2007/4/28, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>:
>
>> It's not that hard: the bucket number is some number of low-order bits
>> of the hash value, and the partition number is some smaller (or at most
>> equal) number of low-order bits of the hash value.
>>
>> regards, tom lane
>>
>

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

2007/4/28, Heikki Linnakangas <heikki(at)enterprisedb(dot)com>:

> 3. Lock that partition
> 6. Unlock partition

I suddenly realize that LW locks are used to manage the lock hash table.So
when a item is to be inserted into hash table, we must gain that partition
lock
first to change that table.
As the insertion algorithm described, a specific partition lock manage some
items, but these items can be stored in anywhere of the hash table,not
necessarily in a bucket chain.
So there are some problems with "different partitions use different hash
chains",
a partition can use different hash chains,too. Am I right?

Cui Shijun wrote:
> As the insertion algorithm described, a specific partition lock manage some
> items, but these items can be stored in anywhere of the hash table,not
> necessarily in a bucket chain.
> So there are some problems with "different partitions use different hash
> chains",
> a partition can use different hash chains,too. Am I right?

No, you're still confused. Each bucket in the hash table is a chain.
Each chain can have 0, 1, or more items.

I'd suggest that you study how the normal non-partitioned hash tables
work first. The partitioning is a straightforward extension of that.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com