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 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@lists.sip-router.org] De la part de Daniel-Constantin Mierla
Envoyé : mardi 4 avril 2017 12:45
À : Kamailio (SER) - Users Mailing List <sr-users@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@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@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@lists.sip-router.org
http://lists.sip-router.org/cgi-bin/mailman/listinfo/sr-users



-- 
Daniel-Constantin Mierla
www.twitter.com/miconda -- www.linkedin.com/in/miconda
Kamailio Advanced Training - May 22-24 (USA) - www.asipto.com
Kamailio World Conference - May 8-10, 2017 - www.kamailioworld.com

-- 
Daniel-Constantin Mierla
www.twitter.com/miconda -- www.linkedin.com/in/miconda
Kamailio Advanced Training - May 22-24 (USA) - www.asipto.com
Kamailio World Conference - May 8-10, 2017 - www.kamailioworld.com