4 Apr
2017
4 Apr
'17
2:49 a.m.
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
4 Apr
4 Apr
6:45 a.m.
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 sizeis 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(a)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
8:11 a.m.
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_(computer_science)> 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 ?
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(a)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(a)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>
11:12 a.m.
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@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(a)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(a)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 -- 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
11:26 a.m.
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@gmail.com]
Envoyé : mardi 4 avril 2017 17:12
À : Ginhoux, Patrick <patrick.ginhoux(a)fr.unisys.com>
Cc : Kamailio (SER) - Users Mailing List <sr-users(a)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@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(a)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(a)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>
2877
days inactive
2877
days old
4 comments
2 participants
participants (2)
-
Daniel-Constantin Mierla -
Ginhoux, Patrick