[ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement policy.
O Mahony, Billy
billy.o.mahony at intel.com
Tue Sep 12 14:49:45 UTC 2017
Hi Darrell,
> The effect here is highly data dependent and in fact dominated by the packet
> distribution which will not be random or rather pseudo-random. I had done
> my own testing with pseudo random flows, fwiw.
> I did not see any thrashing with even at 4000 flows and saw one alive/alive
> choice at 8000.
An agreed standard packet distribution would be useful (essential really) for EMC performance characterization. What is the packet distribution you are using?
Thanks,
Billy.
> -----Original Message-----
> From: ovs-dev-bounces at openvswitch.org [mailto:ovs-dev-
> bounces at openvswitch.org] On Behalf Of Darrell Ball
> Sent: Friday, August 4, 2017 8:38 PM
> To: Ilya Maximets <i.maximets at samsung.com>; Wang, Yipeng1
> <yipeng1.wang at intel.com>; ovs-dev at openvswitch.org
> Cc: Heetae Ahn <heetae82.ahn at samsung.com>
> Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement
> policy.
>
>
>
> -----Original Message-----
> From: Ilya Maximets <i.maximets at samsung.com>
> Date: Monday, July 31, 2017 at 7:25 AM
> To: Darrell Ball <dball at vmware.com>, "Wang, Yipeng1"
> <yipeng1.wang at intel.com>, "ovs-dev at openvswitch.org" <ovs-
> dev at openvswitch.org>
> Cc: Heetae Ahn <heetae82.ahn at samsung.com>
> Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement
> policy.
>
> On 31.07.2017 04:41, Darrell Ball wrote:
> >
> >
> > -----Original Message-----
> > From: <ovs-dev-bounces at openvswitch.org> on behalf of "Wang,
> Yipeng1" <yipeng1.wang at intel.com>
> > Date: Friday, July 28, 2017 at 11:04 AM
> > To: Ilya Maximets <i.maximets at samsung.com>, "ovs-
> dev at openvswitch.org" <ovs-dev at openvswitch.org>
> > Cc: Heetae Ahn <heetae82.ahn at samsung.com>
> > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement
> policy.
> >
> > Good catch. But I think the hash comparison is to "randomly" choose
> one of the two entries to replace when both entries are live.
> > Your change would always replace the first one in such case. It might
> cause some thrashing issue for certain traffic. Meanwhile, to my experience,
> the original "hash comparison" is also not a good way to choose random
> entry, I encountered some thrashing issue before.
> >
> > I think we want some condition like below, but a way to fast choose a
> random entry.
> >
> > if (!to_be_replaced || (emc_entry_alive(to_be_replaced) &&
> !emc_entry_alive(current_entry) )
> > to_be_replaced = current_entry;
> > else if((emc_entry_alive(to_be_replaced) &&
> (emc_entry_alive(current_entry))
> > to_be_replaced = random_entry;
>
> I agree that we need to have something like random choosing of active
> entry to replace.
> I though about this a little and came up with idea to reuse the random
> value generated
> for insertion probability. This should give a good distribution for
> replacement.
> I'll send v2 soon with that approach.
>
> The effect here is highly data dependent and in fact dominated by the packet
> distribution which will not be random or rather pseudo-random. I had done
> my own testing with pseudo random flows, fwiw.
> I did not see any thrashing with even at 4000 flows and saw one alive/alive
> choice at 8000.
[[BO'M]] What is the packet distribution you are using?
>
> We can also see the data dependency with this patch in this first version.
> This patch removed all randomness when choosing an entry to replace when
> both candidates are alive and instead always choose the first entry.
>
> However, you observed that this fixed your problem of thrashing with your
> dataset – if so, the dataset used in your testing may not be very random.
> This change would have been worse in the general case, but seemed perfect
> for your dataset.
>
>
> > //////////////////
> >
> > I agree – we are trying to randomly select one of two live entries with the
> last condition.
> > Something like this maybe makes it more clear what we are trying to do ?
>
> Your code solves the issue with replacement of alive entries while dead
> ones exists,
> but you're still uses hashes as random values which is not right. Hashes are
> not random
> and there is no any difference in choosing the first entry or the entry with a
> bit
> set in a particular place. There always will be some bad case where you will
> replace
> same entries all the time and performance of EMC will be low.
>
> > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
> > index 47a9fa0..75cc039 100644
> > --- a/lib/dpif-netdev.c
> > +++ b/lib/dpif-netdev.c
> > @@ -2051,12 +2051,15 @@ emc_insert(struct emc_cache *cache, const
> struct netdev_flow_key *key,
> > }
> >
> > /* Replacement policy: put the flow in an empty (not alive) entry, or
> > - * in the first entry where it can be */
> > - if (!to_be_replaced
> > - || (emc_entry_alive(to_be_replaced)
> > - && !emc_entry_alive(current_entry))
> > - || current_entry->key.hash < to_be_replaced->key.hash) {
> > + * randomly choose one of the two alive entries to be replaced. */
> > + if (!to_be_replaced) {
> > to_be_replaced = current_entry;
> > + } else if (emc_entry_alive(to_be_replaced) &&
> !emc_entry_alive(current_entry)) {
> > + to_be_replaced = current_entry;
> > + } else if (emc_entry_alive(to_be_replaced) &&
> emc_entry_alive(current_entry)) {
> > + if (current_entry->key.hash & 0x1) {
> > + to_be_replaced = current_entry;
> > + }
> > }
> > }
> > /* We didn't find the miniflow in the cache.
> >
> > //////////////////
> >
> > Thanks
> > Yipeng
> >
> > > -----Original Message-----
> > > From: ovs-dev-bounces at openvswitch.org [mailto:ovs-dev-
> > > bounces at openvswitch.org] On Behalf Of Ilya Maximets
> > > Sent: Friday, July 28, 2017 5:41 AM
> > > To: ovs-dev at openvswitch.org
> > > Cc: Ilya Maximets <i.maximets at samsung.com>; Heetae Ahn
> > > <heetae82.ahn at samsung.com>
> > > Subject: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement
> policy.
> > >
> > > Current EMC replacement policy allows to replace active EMC entry
> > > even if there are dead (empty) entries available. This leads to
> > > EMC trashing even on few hundreds of flows. In some cases PMD
> > > threads starts to execute classifier lookups even in tests with
> > > 50 - 100 active flows.
> > >
> > > Fix this by removing of srtange hash comparison rule from the
> > > replacement checking. New behavior also matches the comment that
> > > describes replacement policy. This comment wasn't correct before.
> > >
> > > Testing shows stable work of exact match cache without misses
> > > with up to 3072 active flows and only 0.05% of EMC misses with
> > > 4096 flows. With higher number of flows there is no significant
> > > difference with current implementation.
> > >
> > > For the reference, number of EMC misses in current master is
> > > around 20% for the case with 2048 active flows.
> > >
> > > Testing performed with 100% EMC insert probability.
> > >
> > > Signed-off-by: Ilya Maximets <i.maximets at samsung.com>
> > > ---
> > > lib/dpif-netdev.c | 3 +--
> > > 1 file changed, 1 insertion(+), 2 deletions(-)
> > >
> > > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
> > > index 47a9fa0..4a8dd80 100644
> > > --- a/lib/dpif-netdev.c
> > > +++ b/lib/dpif-netdev.c
> > > @@ -2054,8 +2054,7 @@ emc_insert(struct emc_cache *cache, const
> struct
> > > netdev_flow_key *key,
> > > * in the first entry where it can be */
> > > if (!to_be_replaced
> > > || (emc_entry_alive(to_be_replaced)
> > > - && !emc_entry_alive(current_entry))
> > > - || current_entry->key.hash < to_be_replaced->key.hash) {
> > > + && !emc_entry_alive(current_entry))) {
> > > to_be_replaced = current_entry;
> > > }
> > > }
> > > --
> > > 2.7.4
> > >
> > > _______________________________________________
> > > dev mailing list
> > > dev at openvswitch.org
> > > https://urldefense.proofpoint.com/v2/url?u=https-
> 3A__mail.openvswitch.org_mailman_listinfo_ovs-
> 2Ddev&d=DwICAg&c=uilaK90D4TOVoH58JNXRgQ&r=BVhFA09CGX7JQ5Ih-
> uZnsw&m=HFvjSxTsGMYHRXD3eRZLc3k_Bp2JfICYTyAbSu8BVWY&s=TNifYfm
> VzvLBYl_mTbSPOlNnLousX2rUvGA8khGcOcw&e=
> > _______________________________________________
> > dev mailing list
> > dev at openvswitch.org
> > https://urldefense.proofpoint.com/v2/url?u=https-
> 3A__mail.openvswitch.org_mailman_listinfo_ovs-
> 2Ddev&d=DwICAg&c=uilaK90D4TOVoH58JNXRgQ&r=BVhFA09CGX7JQ5Ih-
> uZnsw&m=HFvjSxTsGMYHRXD3eRZLc3k_Bp2JfICYTyAbSu8BVWY&s=TNifYfm
> VzvLBYl_mTbSPOlNnLousX2rUvGA8khGcOcw&e=
> >
> >
> >
> >
>
>
>
>
>
>
>
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
More information about the dev
mailing list