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:mico...@gmail.com] Envoyé : mardi 4 avril 2017 17:12 À : Ginhoux, Patrick <patrick.ginh...@fr.unisys.com> Cc : 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, 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-boun...@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@lists.sip-router.org> <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 <mailto:sr-users@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>
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ 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
