[erlang-questions] Packets deduplication

[Jesper Louis Andersen]

Keep a map, M :: #{ integer() => bool() } and ask if there is_key/2 on the
ID's. Once in a while, you GC the map through maps:with(lists:seq(ID1,
ID2), M)  and make it small again.

You would have to measure if this is actually faster/slower and by how much
it is a slower solution. It isn't a priori given it would be either.
jlouis/eministat will help determine if it is the case.


On Thu, Feb 18, 2016 at 2:43 PM, Alexander Petrovsky <askjuise@REDACTED>
wrote:

> Yep, right now I try to do something similar with bitmap and sliding
> window, that will shift. Could you explain about maps?
>
> Thanks!
>
> 2016-02-18 16:37 GMT+03:00 Jesper Louis Andersen <
> jesper.louis.andersen@REDACTED>:
>
>> A simple solution that may work in the end is to keep track of a window
>> of bits:
>>
>> * shift the window as the ID increases
>> * check older packets against the window
>>
>> This gives you "SACK" support, is fast to check against and fast to
>> expire old data due to the shifting.
>>
>> Simply using an ordered list or a map could also work if you clean it up
>> eventually. It depends on how fast your CPU core is.
>>
>>
>> On Thu, Feb 18, 2016 at 2:24 PM, Alexander Petrovsky <askjuise@REDACTED>
>> wrote:
>>
>>> Ouch, I forgot to say, the IDs can be sparse, so they not really
>>> monotonically, they just grow, and can be reordered.
>>>
>>> 2016-02-18 16:20 GMT+03:00 Danil Zagoskin <z@REDACTED>:
>>>
>>>> Hi!
>>>>
>>>> If ID grows monotinically and you have no plans of recovering after
>>>> packet reordering, then you can just keep the previous ID.
>>>>   - If CurID > PrevID, CurID is unique;
>>>>   - If CurID == PrevID, it is not unique;
>>>>   - If CurID < PrevID, it is a bug or reordering, let it crash.
>>>>
>>>>
>>>> On Thu, Feb 18, 2016 at 3:01 PM, Alexander Petrovsky <
>>>> askjuise@REDACTED> wrote:
>>>>
>>>>> Hi!
>>>>>
>>>>> I have the stream of packets with ID (int), and I need to check is the
>>>>> packet is uniq (by ID) or not?
>>>>>
>>>>> Incoming rate is about 20k pps and ID is monotonically grows. What's
>>>>> the best way and data structure fit for this problem?
>>>>>
>>>>> --
>>>>> Петровский Александр / Alexander Petrovsky,
>>>>>
>>>>> Skype: askjuise
>>>>> Phone: +7 914 8 820 815
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> erlang-questions mailing list
>>>>> erlang-questions@REDACTED
>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Danil Zagoskin | z@REDACTED
>>>>
>>>
>>>
>>>
>>> --
>>> Петровский Александр / Alexander Petrovsky,
>>>
>>> Skype: askjuise
>>> Phone: +7 914 8 820 815
>>>
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>
>>>
>>
>>
>> --
>> J.
>>
>
>
>
> --
> Петровский Александр / Alexander Petrovsky,
>
> Skype: askjuise
> Phone: +7 914 8 820 815
>
>


-- 
J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20160218/0bce8ae8/attachment.htm>