[SR-Users] Why these 2 items in the same entry for a htable
Daniel-Constantin Mierla
miconda at gmail.com
Tue Apr 4 17:12:29 CEST 2017
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 <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 -- 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.sip-router.org/pipermail/sr-users/attachments/20170404/9e0154b7/attachment.html>
More information about the sr-users
mailing list