[sheepdog] [PATCH 0/7] modify hash calculation

[MORITA Kazutaka]

From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>

The current hash algorithm is fast but shows poor dispersion.  This
series introduces a new hash function based on the current fnv1a
algorithm.

I compared performance and dispersion when generating 64 bit integer
values with:

 - hash_64 (a simple hash function used in Linux kernel)
 - fnv1a   (the current hash function)
 - sd_hash (the one this patchset introduces)
 - sha1

and sd_hash showed a good result.

                   hash_64    fnv1a   sd_hash     sha1
Performance (*1)     43 ms    96 ms    182 ms   2387 ms
Dispersion (*2)     9216.0   2927.7      11.4      6.57

(*1) The time to generate 10,000,000 hash values.
(*2) The result of chi-squared test.  It should be less than 16.9.

Please note that this series breaks backward compatibility, and
shouldn't be merged into the stable trees.

MORITA Kazutaka (7):
  optimize fnv hash
  add sd_hash to generate more dispersed hash values
  sheep: use sd_hash instead of fnv_64a_buf
  increase the default number of virtual nodes
  sheep: update store version
  tests/functional: update tests for new hash function
  test/unit: add test to check hash function

 include/internal_proto.h      |    4 +-
 include/sheep.h               |   54 ++---
 include/sheepdog_proto.h      |   83 ++++++-
 sheep/cluster/zookeeper.c     |   13 +-
 sheep/config.c                |    2 +-
 sheep/md.c                    |   37 +--
 sheep/migrate.c               |    8 +
 sheep/ops.c                   |    3 +-
 sheep/recovery.c              |    4 +-
 sheep/vdi.c                   |   26 +-
 tests/functional/010.out      |  142 ++++++-----
 tests/functional/011.out      |   18 +-
 tests/functional/012.out      |    6 +-
 tests/functional/027          |    2 +-
 tests/functional/027.out      |    2 +-
 tests/functional/029.out      |   20 +-
 tests/functional/032.out      |  102 ++++----
 tests/functional/033.out      |  102 ++++----
 tests/functional/036.out      |  128 +++++-----
 tests/functional/037.out      |  128 +++++-----
 tests/functional/038.out      |  128 +++++-----
 tests/functional/042.out      |   38 +--
 tests/functional/048.out      |   20 +-
 tests/functional/057.out      |  130 +++++-----
 tests/functional/063          |   12 +-
 tests/functional/063.out      |   30 +--
 tests/functional/064.out      |   48 ++--
 tests/functional/067.out      |   14 +-
 tests/functional/072          |    2 +-
 tests/unit/sheep/Makefile.am  |    5 +-
 tests/unit/sheep/mock_group.c |    6 +
 tests/unit/sheep/test_hash.c  |  537 +++++++++++++++++++++++++++++++++++++++++
 32 files changed, 1240 insertions(+), 614 deletions(-)
 create mode 100644 tests/unit/sheep/test_hash.c

-- 
1.7.9.5