Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1309607

Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct flow_keys layout

Show all headers | View raw

On Thu, Jan 14, 2016 at 11:15 AM, Haiyang Zhang <haiyangz@microsoft.com> wrote:
>
>
>> -----Original Message-----
>> From: Tom Herbert [mailto:tom@herbertland.com]
>> Sent: Thursday, January 14, 2016 1:49 PM
>> To: Haiyang Zhang <haiyangz@microsoft.com>
>> Cc: Eric Dumazet <eric.dumazet@gmail.com>; One Thousand Gnomes
>> <gnomes@lxorguk.ukuu.org.uk>; David Miller <davem@davemloft.net>;
>> vkuznets@redhat.com; netdev@vger.kernel.org; KY Srinivasan
>> <kys@microsoft.com>; devel@linuxdriverproject.org; linux-
>> kernel@vger.kernel.org
>> Subject: Re: [PATCH net-next] hv_netvsc: don't make assumptions on
>> struct flow_keys layout
>>
>> On Thu, Jan 14, 2016 at 10:35 AM, Haiyang Zhang <haiyangz@microsoft.com>
>> wrote:
>> >
>> >
>> >> -----Original Message-----
>> >> From: Eric Dumazet [mailto:eric.dumazet@gmail.com]
>> >> Sent: Thursday, January 14, 2016 1:24 PM
>> >> To: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
>> >> Cc: Tom Herbert <tom@herbertland.com>; Haiyang Zhang
>> >> <haiyangz@microsoft.com>; David Miller <davem@davemloft.net>;
>> >> vkuznets@redhat.com; netdev@vger.kernel.org; KY Srinivasan
>> >> <kys@microsoft.com>; devel@linuxdriverproject.org; linux-
>> >> kernel@vger.kernel.org
>> >> Subject: Re: [PATCH net-next] hv_netvsc: don't make assumptions on
>> >> struct flow_keys layout
>> >>
>> >> On Thu, 2016-01-14 at 17:53 +0000, One Thousand Gnomes wrote:
>> >> > > These results for Toeplitz are not plausible. Given random input
>> you
>> >> > > cannot expect any hash function to produce such uniform results.
>> I
>> >> > > suspect either your input data is biased or how your applying the
>> >> hash
>> >> > > is.
>> >> > >
>> >> > > When I run 64 random IPv4 3-tuples through Toeplitz and Jenkins I
>> >> get
>> >> > > something more reasonable:
>> >> >
>> >> > IPv4 address patterns are not random. Nothing like it. A long long
>> >> time
>> >> > ago we did do a bunch of tuning for network hashes using big porn
>> site
>> >> > data sets. Random it was not.
>> >> >
>> >>
>> >> I ran my tests with non random IPV4 addresses, as I had 2 hosts,
>> >> one server, one client. (typical benchmark stuff)
>> >>
>> >> The only 'random' part was the ports, so maybe ~20 bits of entropy,
>> >> considering how we allocate ports during connect() to a given
>> >> destination to avoid port reuse.
>> >>
>> >> > It's probably hard to repeat that exercise now with geo specific
>> >> routing,
>> >> > and all the front end caches and redirectors on big sites but I'd
>> >> > strongly suggest random input is not a good test, and also that you
>> >> need
>> >> > to worry more about hash attacks than perfect distributions.
>> >>
>> >> Anyway, the exercise is not to find a hash that exactly splits 128
>> flows
>> >> into 16 buckets, according to the number of flows per bucket.
>> >>
>> >> Maybe only 4 flows are sending at 3Gbits, and others are sending at
>> 100
>> >> kbits. There is no way the driver can predict the future.
>> >>
>> >> This is why we prefer to select a queue given the cpu sending the
>> >> packet. This permits a natural shift based on actual load, and is the
>> >> default on linux (see XPS in Documentation/networking/scaling.txt)
>> >>
>> >> Only this driver has a selection based on a flow 'hash'.
>> >
>> > Also, the port number selection may not be random either. For example,
>> > the well-known network throughput test tool, iperf, use port numbers
>> with
>> > equal increment among them. We tested these non-random cases, and
>> found
>> > the Toeplitz hash has distributed evenly, but Jenkins hash has non-
>> even
>> > distribution.
>> >
>> > I'm aware of the test from Tom Herbert <tom@herbertland.com>, which
>> > showing similar results of Toeplitz v.s. Jenkins with random inputs.
>> >
>> > In summary, the Toeplitz performs better in case of non-random inputs,
>> > and performs similar to Jenkins in random inputs (which may not be the
>> > case in real world). So we still prefer to use Toeplitz hash.
>> >
>> You are basing your conclusions on one toy benchmark. I don't believe
>> that an realistically loaded web server is going to consistently give
>> you tuples that happen to somehow fit into a nice model so that the
>> bias benefits your load distribution.
>>
>> > To minimize the computational overhead, we may consider put the hash
>> > in a per-connection cache in TCP layer, so it only needs one time
>> > computation. But, even with the computation overhead at this moment,
>> > the throughput based on Toeplitz hash is better than Jenkins:
>> > Throughput (Gbps) comparison:
>> > #conn           Toeplitz        Jenkins
>> > 32              26.6            23.2
>> > 64              32.1            23.4
>> > 128             29.1            24.1
>> >
>> You don't need to do that. We already store a random hash value in the
>> connection context. If you want to make it non-random then just
>> replace that with a simple global counter. This will have the exact
>> same effect that you see in your tests without needing any expensive
>> computation.
>
> Could you point me to the data field of connection context where this
> hash value is stored? Is it computed only one time?
>
sk_txhash in struct sock. It is set to a random number on TCP or UDP
connect call, It can be reset to a different random value when
connection is seen to be have trouble (sk_rethink_txhash).

Also when you say "Toeplitz performs better in case of non-random
inputs" please quantify exactly how your input data is not random.
What header changes with each connection in your test...

> Thanks!
>
> - Haiyang
>
>
>

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH net-next] hv_netvsc: don't make assumptions on struct flow_keys layout Vitaly Kuznetsov <vkuznets@redhat.com> - 2016-01-07 10:40 +0100
  Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Eric Dumazet <eric.dumazet@gmail.com> - 2016-01-07 14:00 +0100
    Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct flow_keys layout Vitaly Kuznetsov <vkuznets@redhat.com> - 2016-01-07 14:30 +0100
      Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout John Fastabend <john.fastabend@gmail.com> - 2016-01-08 02:10 +0100
        RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout KY Srinivasan <kys@microsoft.com> - 2016-01-08 04:50 +0100
          Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout John Fastabend <john.fastabend@gmail.com> - 2016-01-08 07:20 +0100
            RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout KY Srinivasan <kys@microsoft.com> - 2016-01-08 19:10 +0100
      RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Haiyang Zhang <haiyangz@microsoft.com> - 2016-01-08 22:10 +0100
    Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Tom Herbert <tom@herbertland.com> - 2016-01-09 01:20 +0100
  Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout David Miller <davem@davemloft.net> - 2016-01-10 23:30 +0100
    RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Haiyang Zhang <haiyangz@microsoft.com> - 2016-01-14 00:30 +0100
      Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout David Miller <davem@davemloft.net> - 2016-01-14 06:00 +0100
      Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Tom Herbert <tom@herbertland.com> - 2016-01-14 18:20 +0100
        Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk> - 2016-01-14 19:00 +0100
          Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Eric Dumazet <eric.dumazet@gmail.com> - 2016-01-14 19:30 +0100
            RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Haiyang Zhang <haiyangz@microsoft.com> - 2016-01-14 19:40 +0100
              Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Tom Herbert <tom@herbertland.com> - 2016-01-14 19:50 +0100
                RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Haiyang Zhang <haiyangz@microsoft.com> - 2016-01-14 20:20 +0100
                Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Tom Herbert <tom@herbertland.com> - 2016-01-14 20:50 +0100
                RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Haiyang Zhang <haiyangz@microsoft.com> - 2016-01-14 21:30 +0100
                Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Tom Herbert <tom@herbertland.com> - 2016-01-14 22:50 +0100
                Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout David Miller <davem@davemloft.net> - 2016-01-14 23:10 +0100
                Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Eric Dumazet <eric.dumazet@gmail.com> - 2016-01-14 23:10 +0100
                RE: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Haiyang Zhang <haiyangz@microsoft.com> - 2016-01-14 23:50 +0100
      Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct  flow_keys layout Eric Dumazet <eric.dumazet@gmail.com> - 2016-01-14 19:00 +0100

csiph-web