[SR-Users] Why these 2 items in the same entry for a htable
Ginhoux, Patrick
patrick.ginhoux at fr.unisys.com
Tue Apr 4 17:26:06 CEST 2017
Hi,
Thanks for these additional explanation on the htable.
Now I have to work more on this by myself.
Cordialement
Patrick GINHOUX
De : Daniel-Constantin Mierla [mailto:miconda at gmail.com]
Envoyé : mardi 4 avril 2017 17:12
À : Ginhoux, Patrick <patrick.ginhoux at fr.unisys.com>
Cc : Kamailio (SER) - Users Mailing List <sr-users at lists.sip-router.org>
Objet : Re: [SR-Users] Why these 2 items in the same entry for a htable
Hello,
On 04.04.17 14:11, Ginhoux, Patrick wrote:
Hi,
Thanks for the link I’ll take a lot more later.
Now a quick look seems funny :
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions <https://en.wikipedia.org/wiki/Collision_%28computer_science%29> where the hash function generates the same index for more than one key. Such collisions must be accommodated in some way.
If I understand well, this is typically the case I have. Am I correct ?
Yes, when there are collisions, then the slot has more than one item, stored as a linked list.
Actually, unlike the statements above, is quite common to have collisions, otherwise one cannot store more items than the number of allocated slots.
The main benefit is speeding up the searching. Imagine you have 1 000 000 items. Finding one by its name can take in the worse case 1 000 000 string comparisons. But if you use a hash table having 1 000 slots with a hashing functions that gives you fair distribution, it means that once the hash id (a number) is computed (fast in memory operations), the index of the slot holding the item is 'hashid module nr_of_slots' , then there can be maximum 1 000 string comparisons with the items in that slot.
In additions, by storing the hashid inside the item structure, we compare first the hashid values and if there is a match, then the string names, so practically there are number comparisons most of the time (very fast) and string comparisons (slower) only in very few occasions (typically only once, when matching the requested item).
Cheers,
Daniel
Cordialement
Patrick GINHOUX
De : sr-users [mailto:sr-users-bounces at lists.sip-router.org] De la part de Daniel-Constantin Mierla
Envoyé : mardi 4 avril 2017 12:45
À : Kamailio (SER) - Users Mailing List <mailto:sr-users at lists.sip-router.org> <sr-users at lists.sip-router.org>
Objet : Re: [SR-Users] Why these 2 items in the same entry for a htable
Hello,
if you are not familiar with hash table structure, take a bit of time to read about it, a good article on wikipedia:
- https://en.wikipedia.org/wiki/Hash_table
The dump prints only details of the slots (buckets) that have data on it (size>0). The entry field in the dump content is practically the index of the slot.
I hope it helps!
Cheers,
Daniel
On 04.04.17 08:49, Ginhoux, Patrick wrote:
Hi,
While working on the project to migrate my kamailio.cfg script from kamailio 3.3.1 to 5.0.x, I discovered that in there are 2 items in the same htable.
Below the figure that illustrate this case :
1) Content of the MBXRANGE table :
mysql> select * from mbxrange;
+-----+-------------+-------------------------------------------------+------------+----------+
| id | key_name | key_value | value_type | key_type |
+-----+-------------+-------------------------------------------------+------------+----------+
| 0 | VERSION | 120104-173400 | 0 | 0 |
| 101 | 1 | min=0100000000;max=0199999999;node=OPMVTS1VSE02 | 0 | 0 |
| 102 | 2 | min=0200000000;max=0299999999;node=OPMVTS1VSE02 | 0 | 0 |
| 103 | 3 | min=0300000000;max=0399999999;node=OPMVTS1VSE02 | 0 | 0 |
| 104 | 4 | min=0400000000;max=0499999999;node=OPMVTS1VSE02 | 0 | 0 |
| 105 | 5 | min=0500000000;max=0599999999;node=OPMVTS1VSE02 | 0 | 0 |
| 106 | 6 | min=0600000000;max=0699999999;node=OPMVTS1VSE02 | 0 | 0 |
| 107 | 7 | min=0700000000;max=0799999999;node=OPMVTS1VSE02 | 0 | 0 |
| 108 | 8 | min=0800000000;max=0899999999;node=OPMVTS1VSE02 | 0 | 0 |
| 109 | 9 | min=0900000000;max=0999999999;node=OPMVTS1VSE02 | 0 | 0 |
| 199 | maxmbxrange | 9 | 0 | 0 |
+-----+-------------+-------------------------------------------------+------------+----------+
11 rows in set (0.00 sec)
2) modparam instruction used in my kamailio.cfg script:
modparam("htable", "htable", "mbxrangeHash=>size=4;dbtable=mbxrange;")
3) Result of « kamctl fifo sht_dump mbxrangeHash » command with kamailio version 3.3.x:
[root at op52is4router1 ~]# kamctl fifo sht_dump mbxrangeHash
Entry:: 0
6:: min=0600000000;max=0699999999;node=OPMVTS1VSE02
Entry:: 1
7:: min=0700000000;max=0799999999;node=OPMVTS1VSE02
Entry:: 2
4:: min=0400000000;max=0499999999;node=OPMVTS1VSE02
Entry:: 3
5:: min=0500000000;max=0599999999;node=OPMVTS1VSE02
Entry:: 4
2:: min=0200000000;max=0299999999;node=OPMVTS1VSE02
Entry:: 5
3:: min=0300000000;max=0399999999;node=OPMVTS1VSE02
VERSION:: 120104-173400
Entry:: 6
maxmbxrange:: 9
Entry:: 7
1:: min=0100000000;max=0199999999;node=OPMVTS1VSE02
Entry:: 14
9:: min=0900000000;max=0999999999;node=OPMVTS1VSE02
Entry:: 15
8:: min=0800000000;max=0899999999;node=OPMVTS1VSE02
Result of « kamcmd htable.dump mbxrangeHash » command with kamailio version 5.0.x :
[root at vm-vse02-siprouter1 ~]# kamcmd htable.dump mbxrangeHash
{
entry: 0
size: 1
slot: {
item: {
name: 6
value: min=0600000000;max=0699999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 1
size: 1
slot: {
item: {
name: 7
value: min=0700000000;max=0799999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 2
size: 1
slot: {
item: {
name: 4
value: min=0400000000;max=0499999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 3
size: 1
slot: {
item: {
name: 5
value: min=0500000000;max=0599999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 4
size: 1
slot: {
item: {
name: 2
value: min=0200000000;max=0299999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 5
size: 2
slot: {
item: {
name: 3
value: min=0300000000;max=0399999999;node=OPMMMS1VSE02
type: str
}
item: {
name: VERSION
value: 120104-173400
type: str
}
}
}
{
entry: 6
size: 1
slot: {
item: {
name: maxmbxrange
value: 9
type: str
}
}
}
{
entry: 7
size: 1
slot: {
item: {
name: 1
value: min=0100000000;max=0199999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 14
size: 1
slot: {
item: {
name: 9
value: min=0900000000;max=0999999999;node=OPMMMS1VSE02
type: str
}
}
}
{
entry: 15
size: 1
slot: {
item: {
name: 8
value: min=0800000000;max=0899999999;node=OPMMMS1VSE02
type: str
}
}
}
So, I can see :
- The entry number is not incremental 1 by 1 ; there are entry #1 to #7, then #14 and #15 (all have size=1)
- For the entry #5, its size is of 2 and it contains 2 items
I don’t say here that this is a problem, but the way the htable is loaded seems strange to me.
So if there people who can explain me if what I see is normal or not, and how the htable load process works, I would appreciate.
Thanks in advance.
Cordialement
Patrick GINHOUX
_______________________________________________
SIP Express Router (SER) and Kamailio (OpenSER) - sr-users mailing list
sr-users at lists.sip-router.org <mailto:sr-users at lists.sip-router.org>
http://lists.sip-router.org/cgi-bin/mailman/listinfo/sr-users
--
Daniel-Constantin Mierla
www.twitter.com/miconda <http://www.twitter.com/miconda> -- www.linkedin.com/in/miconda <http://www.linkedin.com/in/miconda>
Kamailio Advanced Training - May 22-24 (USA) - www.asipto.com <http://www.asipto.com>
Kamailio World Conference - May 8-10, 2017 - www.kamailioworld.com <http://www.kamailioworld.com>
--
Daniel-Constantin Mierla
www.twitter.com/miconda <http://www.twitter.com/miconda> -- www.linkedin.com/in/miconda <http://www.linkedin.com/in/miconda>
Kamailio Advanced Training - May 22-24 (USA) - www.asipto.com <http://www.asipto.com>
Kamailio World Conference - May 8-10, 2017 - www.kamailioworld.com <http://www.kamailioworld.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.sip-router.org/pipermail/sr-users/attachments/20170404/66594fde/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 7886 bytes
Desc: not available
URL: <http://lists.sip-router.org/pipermail/sr-users/attachments/20170404/66594fde/attachment.bin>
More information about the sr-users
mailing list