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

Comments
  • 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
  • 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
  • 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
  • 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
  • switched simple test to relase 1.1.0, changed addTargets function to acc...

    switched simple test to relase 1.1.0, changed addTargets function to acc...

    switched simple test to relase 1.1.0, changed addTargets function to accept key value array so that now define weight of each individual server, fixed the tests

    opened by damijanc 1
  • Updated simpletest repo location

    Updated simpletest repo location

    1 commit in this pull request. I simply updated the repo location for simpletest from /cbosuna/ to /lox/, where there is actually a public repo.

    The prevents git from choking on a submodule update, etc.

    opened by tapvt 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
  • 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 4
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
Renders consistent HTTP JSON responses for API-based projects

Laravel API Response is a package that helps to provide and render a consistent HTTP JSON responses to API calls as well as converting and formatting

Kennedy Osaze 43 Nov 20, 2022
A small PHP library for validating VAT identification numbers (VATINs).

VATIN A small PHP library for validating VAT identification numbers (VATINs). Installation This library is available on Packagist: $ composer require

David de Boer 128 Oct 27, 2022
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 110 Dec 27, 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 40 Jun 5, 2022
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.7k Dec 23, 2022
Datenstrom Yellow is for people who make small websites.

Datenstrom Yellow is for people who make small websites.

Datenstrom 389 Jan 7, 2023
A package to handle the SEO in any Laravel application, big or small.

Never worry about SEO in Laravel again! Currently there aren't that many SEO-packages for Laravel and the available ones are quite complex to set up a

Ralph J. Smit 267 Jan 2, 2023
Package with small support traits and classes for the Laravel Eloquent models

Contains a set of traits for the eloquent model. In future can contain more set of classes/traits for the eloquent database.

Martin Kluska 3 Feb 10, 2022
A program which shows the match days and results of a sport league developed with HTML, PHP and BladeOne technology

league-table Escribe un programa PHP que permita al usuario introducir los nombres de los equipos que participan un una liga de fútbol. Con dichos nom

ManuMT 1 Jan 21, 2022
🐍 Web application made in PHP with Laravel where you can interact via API with my Snake game which is made in Python

Snake web application Project of the web application where you can interact via API with Snake game which is available to download on it. Application

Maciek Iwaniuk 1 Nov 26, 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 457 Jan 8, 2023
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 18 Nov 20, 2022
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 197 Dec 30, 2022
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 17 Oct 24, 2022
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 16 Jul 17, 2022
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.2k Dec 28, 2022