From owner-freebsd-fs@freebsd.org Wed May 8 15:50:57 2019 Return-Path: Delivered-To: freebsd-fs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id DDF4A158B101 for ; Wed, 8 May 2019 15:50:56 +0000 (UTC) (envelope-from cse.cem@gmail.com) Received: from mail-io1-f51.google.com (mail-io1-f51.google.com [209.85.166.51]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1O1" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 95EB881771 for ; Wed, 8 May 2019 15:50:55 +0000 (UTC) (envelope-from cse.cem@gmail.com) Received: by mail-io1-f51.google.com with SMTP id s20so7806795ioj.7 for ; Wed, 08 May 2019 08:50:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:reply-to :from:date:message-id:subject:to:cc; bh=qcppmgf09g5IjWS1+15J3iHE6Oj4U/SuTMg9T9vuGlI=; b=FttBb6GoyyKy08kv5zAmoooa3psdsINLjsPOfWW0IPp7rMfyRGK34cdgaGW96YtS8Q MrkMF9tOTJ9J/SaSMhPqLUa/VXG8wBUnn4VwtgzIYpy15D3f4skor3Oq+slGlcFG9j1k wQO4PUqYPx/K6T3qYY2kcUQrLb7lzGilA+F9EMfAOe3Kj5rd+/P0yTxwHZgMPnkQj0d3 yYU9NlMn41MJuE8vWC1ko0H24gIJSGqsYjWx+CHZgJNggeIwUoGCCpEl9noBkf4awF2v mrmX9+89LXOnDhaSBVOocvzT8/0el0LroJXhJhpsgXxfdSFbxmN2vv0BJ2vUYbUkohss vRhw== X-Gm-Message-State: APjAAAWD/pEw2/33aaHbS4p1LdK2x3awO6qaq9COyNs0YghV/DM0Ap7r J1lVqiQy5osAStOru0rMUtcZf3a2 X-Google-Smtp-Source: APXvYqzWbLt8iPtoIMvPKimIG/HrwgC0aKd6ip4m58LPFZ6/37l4thtwnp3cNffWpJNj3ryHPevGRA== X-Received: by 2002:a5e:9313:: with SMTP id k19mr21798603iom.239.1557330649045; Wed, 08 May 2019 08:50:49 -0700 (PDT) Received: from mail-it1-f175.google.com (mail-it1-f175.google.com. [209.85.166.175]) by smtp.gmail.com with ESMTPSA id m20sm3646709ioh.13.2019.05.08.08.50.48 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 08 May 2019 08:50:48 -0700 (PDT) Received: by mail-it1-f175.google.com with SMTP id o190so4725891itc.1 for ; Wed, 08 May 2019 08:50:48 -0700 (PDT) X-Received: by 2002:a24:65cf:: with SMTP id u198mr4058440itb.32.1557330648433; Wed, 08 May 2019 08:50:48 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: Reply-To: cem@freebsd.org From: Conrad Meyer Date: Wed, 8 May 2019 08:50:37 -0700 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: test hash functions for fsid To: Rick Macklem Cc: "freebsd-fs@freebsd.org" Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: 95EB881771 X-Spamd-Bar: ----- Authentication-Results: mx1.freebsd.org; spf=pass (mx1.freebsd.org: domain of csecem@gmail.com designates 209.85.166.51 as permitted sender) smtp.mailfrom=csecem@gmail.com X-Spamd-Result: default: False [-5.97 / 15.00]; TO_DN_EQ_ADDR_SOME(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; HAS_REPLYTO(0.00)[cem@freebsd.org]; TO_DN_SOME(0.00)[]; R_SPF_ALLOW(-0.20)[+ip4:209.85.128.0/17]; REPLYTO_ADDR_EQ_FROM(0.00)[]; RCVD_COUNT_THREE(0.00)[4]; MX_GOOD(-0.01)[cached: alt3.gmail-smtp-in.l.google.com]; RCPT_COUNT_TWO(0.00)[2]; NEURAL_HAM_SHORT(-0.99)[-0.987,0]; FORGED_SENDER(0.30)[cem@freebsd.org,csecem@gmail.com]; IP_SCORE(-2.97)[ip: (-8.83), ipnet: 209.85.128.0/17(-3.73), asn: 15169(-2.25), country: US(-0.06)]; R_DKIM_NA(0.00)[]; FREEMAIL_ENVFROM(0.00)[gmail.com]; ASN(0.00)[asn:15169, ipnet:209.85.128.0/17, country:US]; FROM_NEQ_ENVFROM(0.00)[cem@freebsd.org,csecem@gmail.com]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; TAGGED_FROM(0.00)[]; FROM_HAS_DN(0.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; MIME_GOOD(-0.10)[text/plain]; PREVIOUSLY_DELIVERED(0.00)[freebsd-fs@freebsd.org]; DMARC_NA(0.00)[freebsd.org]; MIME_TRACE(0.00)[0:+]; TO_MATCH_ENVRCPT_SOME(0.00)[]; RCVD_IN_DNSWL_NONE(0.00)[51.166.85.209.list.dnswl.org : 127.0.5.0]; RCVD_TLS_LAST(0.00)[] X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 08 May 2019 15:50:57 -0000 Hi Rick, On Wed, May 8, 2019 at 7:39 AM Rick Macklem wrote: > If you have a FreeBSD system with lots of local file systems (1000s), maybe you could > run the attached program on it and email me the stats. > I'm just trying to see how well these hash functions work on fsids. Below I'll get to some comments on hash functions and hash tables, but first: have you considered a non-hash data structure, such as PCTRIE? PCTRIE_DEFINE() creates a datastructure with similar properties to a hash table for this use, but does not require a hash function step at all because all fsids are already unique, fixed-size, 64-bit values. It may be especially space-efficient for non-ZFS FSIDs, when the 64-bit key is composed with '(fsid.val[1] << 32 | fsid.val[0])'. (Elaborated on more below.(A)) Usually it makes sense to size hash tables for the size of the data; for direct insert tables you want to keep the load factor below 0.8 or something like that. So the hardcoded 256 doesn't make a ton of sense, IMO. As far as hash functions, both (hash32_buf == djb2, FNV32) are really weak, but importantly for hash tables, fast. https://github.com/Cyan4973/smhasher#summary provides some broader context, but keep in mind most of those algorithms are targeting much longer keys than 8 bytes. I would guess that h1/h3 will be noticably worse than h2/h4 without performing any better, but I don't have data to back that up. (If you were to test calculate_crc32c() or XXH32/XXH64, included in sys/contrib/zstd, you might observe fewer collisions and better distribution. But that isn't necessarily the most important factor for hash table performance in this use.) (A) FSIDs themselves have poor initial distribution and *very* few unique bits (i.e., for filesystems that use vfs_getnewfsid, the int32 fsid val[1] will be identical across all filesystems of the same type, such as NFS mounts). The remaining val[0] is unique due to an incrementing global counter. You could pretty easily extract the vfs_getnewfsid() code out to userspace to simulate creating a bunch of fsid_t's and run some tests on that list. It isn't a real world distribution but it would probably be pretty close, outside of ZFS. ZFS FSIDs have 8 bits of shared vfs type, but the remaining 56 bits appears to be generated by arc4rand(9), so ZFS FSIDs will have good distribution even without hashing. Anyway, maybe this is helpful, maybe not. Thanks for working on scaling exports, and NFS in general! It is appreciated. Take care, Conrad