Flexihash is a small PHP library which implements consistent hashing.

Related tags

Laravel flexihash
Overview

Flexihash

Build Status Coverage Status

Flexihash is a small PHP library which implements consistent hashing, which is most useful in distributed caching. It requires PHP5 and uses PHPUnit for unit testing.

Installation

Composer is the recommended installation technique. You can find flexihash on Packagist so installation is as easy as

composer require flexihash/flexihash

or in your composer.json

{
    "require": {
        "flexihash/flexihash": "^3.0.0"
    }
}

Usage

$hash = new Flexihash();

// bulk add
$hash->addTargets(['cache-1', 'cache-2', 'cache-3']);

// simple lookup
$hash->lookup('object-a'); // "cache-1"
$hash->lookup('object-b'); // "cache-2"

// add and remove
$hash
  ->addTarget('cache-4')
  ->removeTarget('cache-1');

// lookup with next-best fallback (for redundant writes)
$hash->lookupList('object', 2); // ["cache-2", "cache-4"]

// remove cache-2, expect object to hash to cache-4
$hash->removeTarget('cache-2');
$hash->lookup('object'); // "cache-4"

Tests

Unit Test

% vendor/bin/phpunit

Benchmark Test

% vendor/bin/phpunit tests/BenchmarkTest.php

Further Reading

Issues
  • Versioning, SemVer, tags, CHANGELOG

    Versioning, SemVer, tags, CHANGELOG

    • Current version, which has barely been touched for seven years, should be tagged as v1.0.0.
    • CHANGELOG.md should be created.
    • Future versioning should follow SemVer
      • Changing autoloaders, namespacing etc should be a major release e.g. v2.0.0
    opened by pda 7
  • Create a composer package

    Create a composer package

    It would be great (and appreciated) if you could create a composer package for this library. Thank you!

    opened by kornrunner 4
  • Using MD5Hasher with large server pool breaks correctness of algorithm

    Using MD5Hasher with large server pool breaks correctness of algorithm

    Here is a fun bug.

    In a simulation/test we had 10 nodes added like this:

    $hasher->addTargets(['node1:port1', ... 'node10:port10']);
    

    We also set num replicas to 100 but you can reproduce with 64.

    Then we tested that 1000 keys looked up a roughly evenly distributed (pass), and that if we remove a node (node4:port4 in our case) they remain even which works fine. We also test that each node retains all of the keys it had originally after one node is removed (as well as something close to 1/N-1 of the 1/N keys the failed host had in the original ring).

    This part fails - somehow removing a node (or strictly building same ring without node4 but they should be equivalent), makes some small percentage of keys move which node they are on even if they weren't on the failed node.

    After some debugging, I think I can explain this.

    When using MD5Hasher you chose to keep hex strings at the ring positions rather than converting back to ints. That in itself is not necessarily wrong, however it falls into a PHP dynamic typing gotcha: the internal positionToTarget lookup ends up looking like this (after sorting):

    ...
      'ff4a2aff' => 'host7:port7',
      'ff6c8fa3' => 'host5:port5',
      'ff820a72' => 'host5:port5',
      'ffc8b06f' => 'host6:port6',
      'fff31063' => 'host10:port10',
      11023620 => 'host4:port4',
      13715227 => 'host7:port7',
      13952778 => 'host4:port4',
      16385505 => 'host6:port6',
      17878142 => 'host2:port2',
    ...
    

    i.e. using an all-decimal-digit string as an array key in PHP causes PHP to convert it to an int key which then sorts after all string keys not in natural hex-digit order. Keys that are in these ring segments then move unpredictably between ring reconfigurations because the algorithm is no longer correct and comparisons are not working as expected.

    Switching to CRC32Hasher with identical params fixes the issue because those are always integer keys.

    2 possible fixes:

    1. You //could// do some magic in Flexihash to make this work correctly - it's not really MD5Hasher's fault PHP does funny things with "int-like" strings. For example you could prefix string keys in the array so they look like _ffaabb33, the leading underscore would stop PHP mangling to an int and would keep sort order correct. You'd obviously need to also prepend the hashed key with _ at lookup time etc.
    2. Alternatively, you could decide that HasherInterface requires returned values to be ints and no larger than PHP_INT_MAX and fix MD5Hasher to meet this - just need hexdec() around the return statement.

    Please let us know which you'd prefer both are simple changes.

    opened by banks 4
  • Add basic composer support

    Add basic composer support

    Makes it a bit easier to use with composer.

    opened by DavidGoodwin 3
  • BREAKING CHANGES: Support PHP >= 7.2

    BREAKING CHANGES: Support PHP >= 7.2

    Why

    PHP <= 7.1 and PHPUnit <= 7 are no longer supported.

    What to change

    • Update Roadmap.
    • Use PHPUnit 8 instead of PHPUnit 4.
    • PHP 7.2 minimum.
    • Enable strict typing mode for all PHP files.

    This change is breaking that it's better to release the major version as 3.0.0.

    Ref.

    https://www.php.net/supported-versions.php image

    https://phpunit.de/supported-versions.html image

    opened by serima 2
  • Update README.md

    Update README.md

    opened by myxobek 2
  • Fatal error:  Class 'Flexihash_Crc32Hasher' not found in .../Flexihash.php on line 57

    Fatal error: Class 'Flexihash_Crc32Hasher' not found in .../Flexihash.php on line 57

    Hi, you must include classes before initialize it, becouse users without autoloader couldn't use you great flexihash!

    opened by shumkov 2
  • Add composer support, convert unit tests to PHPUnit and add CI

    Add composer support, convert unit tests to PHPUnit and add CI

    • PSR-0 autoloading via Composer.
    • Unit tests converted to PHPUnit and benchmark test excluded in phpunit.xml.dist
    • Travis CI support.
    • Coveralls support.
    • PHP Code sniffer phpcs.xml added to ignore class naming until v2.0.0 hits.

    I will add a CHANGELOG.md before merging.

    opened by dmnc 1
  • use binary search for lookup

    use binary search for lookup

    null

    opened by ptcong 1
  • Fixed PHPDoc

    Fixed PHPDoc

    screenshot at jun 02 15-58-41 screenshot at jun 02 15-59-10

    opened by sergeyklay 1
  • Consistent hashing question

    Consistent hashing question

    This isn't an issue with the library, just a question about how consistent hashing works with weights. If I change the weight of a target by some small amount, let's say out of 10 targets each with a weight of 1, I change the weight of one target to 3. How significantly will the keys be redistributed?

    opened by dliebner 5
  • Add php 8.0 on travis

    Add php 8.0 on travis

    Ref: https://www.dereuromark.de/2019/01/04/test-composer-dependencies-with-prefer-lowest/

    opened by serima 0
  • Use with redis for sharding

    Use with redis for sharding

    Can it be used with Redis for client-side sharding? Has this library some performance impact?

    opened by akalongman 0
  • Use binary search for initial target lookup

    Use binary search for initial target lookup

    I just got a 20x speedup in my python translation of this code by doing a binary search instead of "iterate over the whole sorted targets list one at a time until we find our first valid target", I suspect that the PHP version could see benefits too :)

    https://github.com/shish/python-flexihash/commit/37f56794903c626726be421cbf2964178866ab91

    opened by shish 3
Releases(v3.0.0)
  • v3.0.0(Aug 7, 2020)

  • v2.0.2(Apr 22, 2016)

  • v2.0.1(Apr 22, 2016)

    PHP treats numeric strings as integers when used as an array key. This means they pop out of order and cause incorrect remapping when a target is removed.

    This release fixes that issue with thanks to @kojik1010 and @banks.

    Source code(tar.gz)
    Source code(zip)
  • v2.0.0(Nov 8, 2015)

    Changes

    • Namespacing.
    • PSR-4 autoloading.
    • Reorganisation of files.
    • Full PSR-2 support.
    • Drops PHP<5.4 support.

    Upgrading

    This is a breaking update. The class names have changed. To upgrade you will need to:

    • Update any references to Flexihash to Flexihash\Flexihash.
    • Update any references to the hashers from (for example) Flexihash_Crc32Hasher to Flexihash\Hasher\Crc32Hasher.
    • Catch Flexihash\Exception instead of 'Flexihash_Exception`.
    Source code(tar.gz)
    Source code(zip)
  • v1.0.0(Nov 7, 2015)

    Install with composer require flexihash/flexihash

    • Remove legacy autoloader.
    • Migrate tests to PHPUnit.
    • Get as close to PSR-2 as possible without changing class names.
    • Setup automatic testing with Travis.
    • Give code coverage information with Coveralls.
    Source code(tar.gz)
    Source code(zip)
  • v0.1.0(Nov 7, 2015)

    This is the repository in it's historical state.

    It does not support composer , PSR or PHPUnit.

    You are recommended to use v1.0.0 as a minimum unless you have a good reason.

    Source code(tar.gz)
    Source code(zip)
Owner
Paul Annesley
Paul Annesley
Simple timesheets and vacation management for small businesses.

About Daybreak Daybreak is a very simplistic timesheet and vacation planning program for small businesses. It was created because I needed something I

Erik Porsche 92 Jan 10, 2022
A small package for adding UUIDs to Eloquent models.

A small package for adding UUIDs to Eloquent models. Installation You can install the package via composer: composer require ryangjchandler/laravel-uu

Ryan Chandler 37 Oct 15, 2021
An issue tracking tool based on laravel+reactjs for small and medium-sized enterprises, open-source and free, similar to Jira.

ActionView English | 中文 An issue tracking tool based on php laravel-framework in back-end and reactjs+redux in front-end, it's similar to Jira. You co

null 1.6k Jan 18, 2022
Migrator is a GUI migration manager for Laravel which you can create, manage and delete your migration.

Migrator Migrator is a GUI migration manager for Laravel which you can create, manage and delete your migration. Installation: To install Migrator you

Reza Amini 301 Jan 11, 2022
A Laravel 8 Project Implement with GraphQL With Sanctum APIs Authentications Which utilized in Any Frontend or Any Mobile Application Programs.

A Laravel 8 Project Implement with GraphQL With Sanctum APIs Authentications Which utilized in Any Frontend or Any Mobile Application Programs.

Vikas Ukani 3 Jan 6, 2022
Stash view is a composer package for Laravel which caches views using Russian Doll Caching methodology.

Stash View Stash view is a composer package for Laravel which caches views using Russian Doll Caching methodology. What is Russian Doll Caching ? It i

Bhushan Gaikwad 13 Dec 31, 2021
Load head metadata from a manifest file which can be shared with a SPA project

Laravel Head Manifest Installation Step 1: Add Laravel Head Manifest to your laravel project composer require critiq/laravel-head-manifest Step 2: Add

Critiq 1 Nov 17, 2021
Composer package which adds support for HTML5 elements using Laravels Form interface (e.g. Form::date())

Laravel HTML 5 Inputs Composer package which adds support for HTML5 elements by extending Laravel's Form interface (e.g. Form::date()) Adds support fo

Small Dog Studios 11 Oct 13, 2020
Blacksmith is a code generation tool which automates the creation of common files that you'd typically create for each entity in your application.

Blacksmith is a code generation tool which automates the creation of common files that you'd typically create for each entity in your application.

Indatus 196 Oct 19, 2021
Github repository dedicated for my YT tutorial which shows how to use testing in Laravel

Testing in Laravel The following documentation is based on my Laravel Testing for Beginners tutorial we’re going to cover the basics of unit tests, fe

Code With Dary 8 Dec 28, 2021
Is an Extension of Laravel View Class which compiles String Template on the fly. It automatically detects changes on your string template and recompiles it if needed.

Laravel-fly-view Is an Extension of Laravel View Class which compiles String Template on the fly. It automatically detects changes on your string temp

John Turingan 17 Aug 15, 2021
Package to optimize your site automatically which results in a 35%+ optimization

Laravel Page Speed Simple package to minify HTML output on demand which results in a 35%+ optimization. Laravel Page Speed was created by Renato Marin

Renato Marinho 2.1k Jan 11, 2022
GeoLocation-Package - This package helps you to know the current language of the user, the country from which he is browsing, the currency of his country, and also whether he is using it vpn

GeoLocation in PHP (API) ?? ?? ?? This package helps you to know a lot of information about the current user by his ip address ?? ?? ?? This package h

Abdullah Karam 3 Dec 27, 2021
A site which you can apply jobs or search for employees with cool functionalities..

About App An App which you can apply jobs or search for employees with cool functionalities. Some Pics of App Click Image to Zoom in Sign In & Up Empl

Fatih Canbolat 1 Jan 6, 2022
Lavacharts is a graphing / charting library for PHP 5.4+ that wraps Google's Javascript Chart API.

Lavacharts 3.1.12 Lavacharts is a graphing / chart library for PHP5.4+ that wraps the Google Chart API. Stable: Dev: Developer Note Please don't be di

Kevin Hill 608 Jan 9, 2022
A laravel service provider for the netsuite-php library service

netsuite-laravel A PHP supplemental package to the ryanwinchester/netsuite-php package to add the NetSuite service client to the service container of

NetsuitePHP 3 Apr 23, 2021
PHP client library for reCAPTCHA, a free service to protect your website from spam and abuse.

reCAPTCHA PHP client library reCAPTCHA is a free CAPTCHA service that protects websites from spam and abuse. This is a PHP library that wraps up the s

Google 3.2k Jan 14, 2022
Menu Library for PHP

KnpMenu The KnpMenu library provides object oriented menus for PHP. It is used by the KnpMenuBundle for Symfony but can now be used stand-alone. Insta

KNP Labs 1.3k Jan 14, 2022
PHP 5.3 Object Oriented image manipulation library

Imagine Tweet about it using the #php_imagine hashtag. Image manipulation library for PHP 5.3 inspired by Python's PIL and other image libraries. Requ

null 4.2k Jan 14, 2022