[dpdk-users] DPDK hash table dynamic growth

[dpdk-users] DPDK hash table dynamic growth

[Fu, Qiaobin]

Hello,

Currently, I am using the hash library to handle network flows defined as source and destination IP addresses. I need to find a way to alleviate memory pressure when the table is full. However, after some research, I didn’t find any hints on the dynamic growth in the hash library. Could anyone point me some hints on this? Thanks.

Best,
Qiaobin

Re: [dpdk-users] DPDK hash table dynamic growth

[Stephen Hemminger]

On Mon, 17 Apr 2017 15:47:59 +0000
"Fu, Qiaobin" <qiaobinf@bu.edu> wrote:

> Hello,
> 
> Currently, I am using the hash library to handle network flows defined as source and destination IP addresses. I need to find a way to alleviate memory pressure when the table is full. However, after some research, I didn’t find any hints on the dynamic growth in the hash library. Could anyone point me some hints on this? Thanks.
> 
> Best,
> Qiaobin

If you need growing hash table, I recommend the lock-free hash table in the Linux userspace RCU library;
rather than the more limited DPDK one.

Re: [dpdk-users] DPDK hash table dynamic growth

[Alex Kiselev]

I would take a look at:

1) http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/
2) https://github.com/efficient/libcuckoo
3)
http://high-scale-lib.cvs.sourceforge.net/viewvc/high-scale-lib/high-scale-lib/org/cliffc/high_scale_lib/NonBlockingHashMap.java?view=markup
https://www.youtube.com/watch?v=HJ-719EGIts
https://www.youtube.com/watch?v=WYXgtXWejRM

But there is a catch, none of them is written in C.

2017-04-17 19:54 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org>:
> On Mon, 17 Apr 2017 15:47:59 +0000
> "Fu, Qiaobin" <qiaobinf@bu.edu> wrote:
>
>> Hello,
>>
>> Currently, I am using the hash library to handle network flows defined as source and destination IP addresses. I need to find a way to alleviate memory pressure when the table is full. However, after some research, I didn’t find any hints on the dynamic growth in the hash library. Could anyone point me some hints on this? Thanks.
>>
>> Best,
>> Qiaobin
>
> If you need growing hash table, I recommend the lock-free hash table in the Linux userspace RCU library;
> rather than the more limited DPDK one.



-- 
--
Kiselev Alexander

Re: [dpdk-users] DPDK hash table dynamic growth

[Fu, Qiaobin]

Thanks @Alex and @Stephen for pointing these valuable materials to me!

Maybe it’s better that I can clarify my scenarios more. Actually, we are using RSS (source + destination IP) to distribute packets, so we are maintaining one hash table per lcore (thread), and there is no need for synchronization issue in our case. If there are more solutions, please let me know. I will compare the solutions, and pick up the best suitable one.

Best,
Qiaobin

On Apr 17, 2017, at 1:30 PM, Alex Kiselev <kiselev99@gmail.com<mailto:kiselev99@gmail.com>> wrote:

I would take a look at:

1) http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/
2) https://github.com/efficient/libcuckoo
3)
http://high-scale-lib.cvs.sourceforge.net/viewvc/high-scale-lib/high-scale-lib/org/cliffc/high_scale_lib/NonBlockingHashMap.java?view=markup
https://www.youtube.com/watch?v=HJ-719EGIts
https://www.youtube.com/watch?v=WYXgtXWejRM

But there is a catch, none of them is written in C.

2017-04-17 19:54 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org>:
On Mon, 17 Apr 2017 15:47:59 +0000
"Fu, Qiaobin" <qiaobinf@bu.edu> wrote:

Hello,

Currently, I am using the hash library to handle network flows defined as source and destination IP addresses. I need to find a way to alleviate memory pressure when the table is full. However, after some research, I didn’t find any hints on the dynamic growth in the hash library. Could anyone point me some hints on this? Thanks.

Best,
Qiaobin

If you need growing hash table, I recommend the lock-free hash table in the Linux userspace RCU library;
rather than the more limited DPDK one.



--
--
Kiselev Alexander

Re: [dpdk-users] DPDK hash table dynamic growth

[Alex Kiselev]

If you need only a single reader and a single writer solution you can use
any existing hash table implementation and build on top of it your own
resizable version. You can try a straightforward approach. Create a new
bigger hash table when the old is full and just copy key/values into it. A
new reader/lookup function should take into account that during resizing
there can be more then one hash table and check all of them. And I wouldn't
copy all keys at once, but instead I'd copy N keys at one iteration of the
lcore main loop so the resizing process don't block other operations.

пн, 17 апр. 2017 г. в 20:44, Fu, Qiaobin <qiaobinf@bu.edu>:

> Thanks @Alex and @Stephen for pointing these valuable materials to me!
>
> Maybe it’s better that I can clarify my scenarios more. Actually, we are
> using RSS (source + destination IP) to distribute packets, so we are
> maintaining one hash table per lcore (thread), and there is no need for
> synchronization issue in our case. If there are more solutions, please let
> me know. I will compare the solutions, and pick up the best suitable one.
>
> Best,
> Qiaobin
>
> On Apr 17, 2017, at 1:30 PM, Alex Kiselev <kiselev99@gmail.com> wrote:
>
> I would take a look at:
>
> 1) http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/
> 2) https://github.com/efficient/libcuckoo
> 3)
>
> http://high-scale-lib.cvs.sourceforge.net/viewvc/high-scale-lib/high-scale-lib/org/cliffc/high_scale_lib/NonBlockingHashMap.java?view=markup
> https://www.youtube.com/watch?v=HJ-719EGIts
> https://www.youtube.com/watch?v=WYXgtXWejRM
>
> But there is a catch, none of them is written in C.
>
> 2017-04-17 19:54 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org>:
>
> On Mon, 17 Apr 2017 15:47:59 +0000
> "Fu, Qiaobin" <qiaobinf@bu.edu> wrote:
>
> Hello,
>
> Currently, I am using the hash library to handle network flows defined as
> source and destination IP addresses. I need to find a way to alleviate
> memory pressure when the table is full. However, after some research, I
> didn’t find any hints on the dynamic growth in the hash library. Could
> anyone point me some hints on this? Thanks.
>
> Best,
> Qiaobin
>
>
> If you need growing hash table, I recommend the lock-free hash table in
> the Linux userspace RCU library;
> rather than the more limited DPDK one.
>
>
>
>
> --
> --
> Kiselev Alexander
>
>
> --
--
Kiselev Alexander

Re: [dpdk-users] DPDK hash table dynamic growth

[Shyam Shrivastav]

For theory on growing/shrinking hash tables useful MIT class

https://www.youtube.com/watch?v=BRO7mVIFt08

On Tue, Apr 18, 2017 at 1:36 AM, Alex Kiselev <kiselev99@gmail.com> wrote:

> If you need only a single reader and a single writer solution you can use
> any existing hash table implementation and build on top of it your own
> resizable version. You can try a straightforward approach. Create a new
> bigger hash table when the old is full and just copy key/values into it. A
> new reader/lookup function should take into account that during resizing
> there can be more then one hash table and check all of them. And I wouldn't
> copy all keys at once, but instead I'd copy N keys at one iteration of the
> lcore main loop so the resizing process don't block other operations.
>
> пн, 17 апр. 2017 г. в 20:44, Fu, Qiaobin <qiaobinf@bu.edu>:
>
> > Thanks @Alex and @Stephen for pointing these valuable materials to me!
> >
> > Maybe it’s better that I can clarify my scenarios more. Actually, we are
> > using RSS (source + destination IP) to distribute packets, so we are
> > maintaining one hash table per lcore (thread), and there is no need for
> > synchronization issue in our case. If there are more solutions, please
> let
> > me know. I will compare the solutions, and pick up the best suitable one.
> >
> > Best,
> > Qiaobin
> >
> > On Apr 17, 2017, at 1:30 PM, Alex Kiselev <kiselev99@gmail.com> wrote:
> >
> > I would take a look at:
> >
> > 1) http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/
> > 2) https://github.com/efficient/libcuckoo
> > 3)
> >
> > http://high-scale-lib.cvs.sourceforge.net/viewvc/high-
> scale-lib/high-scale-lib/org/cliffc/high_scale_lib/
> NonBlockingHashMap.java?view=markup
> > https://www.youtube.com/watch?v=HJ-719EGIts
> > https://www.youtube.com/watch?v=WYXgtXWejRM
> >
> > But there is a catch, none of them is written in C.
> >
> > 2017-04-17 19:54 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org
> >:
> >
> > On Mon, 17 Apr 2017 15:47:59 +0000
> > "Fu, Qiaobin" <qiaobinf@bu.edu> wrote:
> >
> > Hello,
> >
> > Currently, I am using the hash library to handle network flows defined as
> > source and destination IP addresses. I need to find a way to alleviate
> > memory pressure when the table is full. However, after some research, I
> > didn’t find any hints on the dynamic growth in the hash library. Could
> > anyone point me some hints on this? Thanks.
> >
> > Best,
> > Qiaobin
> >
> >
> > If you need growing hash table, I recommend the lock-free hash table in
> > the Linux userspace RCU library;
> > rather than the more limited DPDK one.
> >
> >
> >
> >
> > --
> > --
> > Kiselev Alexander
> >
> >
> > --
> --
> Kiselev Alexander
>