[SR-Users] Strange behavior with $shtinc
Daniel-Constantin Mierla
miconda at gmail.com
Fri Jun 1 09:15:09 CEST 2018
Hello,
as Alex explaining, having more than one item in a slot is ok, this is
the design of htables, it is not possible to ensure that one slot has a
single item. Even if you define the hash table with 1000 slots (entries)
and you add two items, they can get on the same slot, if the hashing
function over the key results in conflicting slots due to hash ids. You
can read more about hash table structures at:
- https://en.wikipedia.org/wiki/Hash_table
If there is a conflict in the slots, the search is linear (Alex pointed
that as well), however, the search match first the hash id, then the
length of the key and then the value of the key, so it is rather fast to
rule out not-matching key.
For example, lets say that you have two keys, Alice and Bob, the hash
ids for them can be 2010 and 4010. The selected slots is hashid %
hashmaxslots, respectively 2010%1000 and 4010%1000, so for both the slot
is 10. But matching will also be done on 2010 and 4010, so the value
will be matched only once, which is done also for the case there is a
single item on slot. That means the difference in performance is one
more integer comparison (very fast) plus one move-to-next item.
Going back to your issue, use kamctl to dump the content of the hash
table, it gives you a proper json document, as opposite to kamcmd, which
is a binrpc client, not a jsonrpc one.
Cheers,
Daniel
On 31.05.18 23:27, Alex Balashov wrote:
> PS. As a general rule of thumb, the size (in terms of buckets) of the
> htable should be at least 2x the maximum number of entries you expect to
> put in it, and the bigger the better.
>
> Hash tables are inherently inefficient in that regard; it would require
> a perfect hash algorithm and a perfect variance in keys to get unique
> bucket hits in a situation where size(htable) =~ entry count N.
>
> On Thu, May 31, 2018 at 05:22:43PM -0400, Alex Balashov wrote:
>
>> Hi,
>>
>> I might be mistaken in my interpretation of the situation, but my first
>> guess would be multiple entries ending up in the same slot is simply a
>> reflection of some values being hashed to the same bucket. Hash table
>> implementations usually deal with collisions by implementing a linked
>> list attached to the bucket/slot, and search algorithms will traverse
>> that list linearly looking for an exact key match. The general
>> expectation is that collisions won't be too common and that the average
>> depth of a collision chain will be low.
>>
>> If this is the case, increasing the size of the htable will help. What
>> is the value of the 'size' parameter for that htable definition now?
>>
>> -- Alex
>>
>> On Thu, May 31, 2018 at 08:07:18PM +0000, Brooks Bridges wrote:
>>
>>> Apologies if the initial report was unclear. The issue isn't with the actual counts (which appear to be accurate), but that we are intermittently ending up with 2 keys in the same entry instead of one per entry.
>>>
>>> This makes parsing the data very difficult, and I cannot determine a reason it would be doing this instead of putting each one in its own entry like it appears to do for almost all of the values until it has run for a while.
>>>
>>> Brooks Bridges | Engineering Manager
>>> O1 Communications
>>> 4359 Town Center Boulevard, Suite 217
>>> El Dorado Hills, California 95762
>>> office: 916.235.2097 | main: 888.444.1111, Option 2
>>> email: bbridges at o1.com<mailto:bbridges at o1.com> | web: www.o1.com<http://www.o1.com/>
>>>
>>> From: Daniel-Constantin Mierla [mailto:miconda at gmail.com]
>>> Sent: Thursday, May 31, 2018 12:52
>>> To: Kamailio (SER) - Users Mailing List; Brooks Bridges
>>> Subject: Re: [SR-Users] Strange behavior with $shtinc
>>>
>>>
>>> Did you monitor the values of those statistics over the time? If yes, was there a moment when the value evolved unexpected?
>>>
>>> Cheers,
>>> Daniel
>>>
>>> On 31.05.18 19:30, Brooks Bridges wrote:
>>> Let me preface this with the statement that as best I can tell from docs and code, this function is supposed to be 100% atomic and this shouldn't be able to happen. I also have not found anything in the module's github commit logs that would indicate this behavior has changed from previous versions.
>>>
>>> That being said, I appear to have run into an oddity where intermittently I'm getting 2 slots being put in the same entry, which results in trying to parse the output for graphing and reporting not working quite right. The mechanism I'm using is a very simple counter mechanism to record statistics about calls. As an example, I am using the following mechanism:
>>>
>>> $var(z) = $shtinc(callstats=>$avp(realm),cps_exceeded);
>>> or
>>> $var(z) = $shtinc(callstats=>$avp(realm),sessions_exceeded);
>>>
>>> This typically results in something like this:
>>>
>>> {
>>> entry: 4335
>>> size: 1
>>> slot: {
>>> {
>>> name: realm1,total_requests
>>> value: 2365034
>>> type: int
>>> }
>>> }
>>> }
>>> {
>>> entry: 4532
>>> size: 1
>>> slot: {
>>> {
>>> name: realm2,cps_exceeded
>>> value: 30
>>> type: int
>>> }
>>> }
>>> }
>>> And so on... However, one or more of them sometimes end up like this:
>>>
>>> {
>>> entry: 4646
>>> size: 2
>>> slot: {
>>> {
>>> name: realm1,total_requests
>>> value: 15958026
>>> type: int
>>> }
>>> {
>>> name: realm2,cps_exceeded
>>> value: 6432103
>>> type: int
>>> }
>>> }
>>> }
>>>
>>> Thanks in advance for your help and/or suggestions!
>>>
>>> Brooks Bridges | Engineering Manager
>>> O1 Communications
>>> 4359 Town Center Boulevard, Suite 217
>>> El Dorado Hills, California 95762
>>> office: 916.235.2097 | main: 888.444.1111, Option 2
>>> email: bbridges at o1.com<mailto:bbridges at o1.com> | web: www.o1.com<http://www.o1.com/>
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>>
>>> Kamailio (SER) - Users Mailing List
>>>
>>> sr-users at lists.kamailio.org<mailto:sr-users at lists.kamailio.org>
>>>
>>> https://lists.kamailio.org/cgi-bin/mailman/listinfo/sr-users
>>>
>>>
>>>
>>> --
>>>
>>> Daniel-Constantin Mierla -- www.asipto.com<http://www.asipto.com>
>>>
>>> www.twitter.com/miconda<http://www.twitter.com/miconda> -- www.linkedin.com/in/miconda<http://www.linkedin.com/in/miconda>
>>>
>>> Kamailio World Conference -- www.kamailioworld.com<http://www.kamailioworld.com>
>>> _______________________________________________
>>> Kamailio (SER) - Users Mailing List
>>> sr-users at lists.kamailio.org
>>> https://lists.kamailio.org/cgi-bin/mailman/listinfo/sr-users
>>
>> --
>> Alex Balashov | Principal | Evariste Systems LLC
>>
>> Tel: +1-706-510-6800 / +1-800-250-5920 (toll-free)
>> Web: http://www.evaristesys.com/, http://www.csrpswitch.com/
>>
>> _______________________________________________
>> Kamailio (SER) - Users Mailing List
>> sr-users at lists.kamailio.org
>> https://lists.kamailio.org/cgi-bin/mailman/listinfo/sr-users
--
Daniel-Constantin Mierla -- www.asipto.com
www.twitter.com/miconda -- www.linkedin.com/in/miconda
Kamailio World Conference -- www.kamailioworld.com
More information about the sr-users
mailing list