GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  SET::CONSISTENTHASH (3)

.ds Aq ’

NAME

Set::ConsistentHash - library for doing consistent hashing

CONTENTS

SYNOPSIS



  my $set = Set::ConsistentHash->new;



OVERVIEW

Description, shamelessly stolen from Wikipedia:



  Consistent hashing is a scheme that provides hash table
  functionality in a way that the addition or removal of one slot does
  not significantly change the mapping of keys to slots. In contrast,
  in most traditional hash tables, a change in the number of array
  slots causes nearly all keys to be remapped.

  Consistent hashing was introduced in 1997 as a way of distributing
  requests among a changing population of web servers. More recently,
  it and similar techniques have been employed in distributed hash
  tables.



You’re encouraged to read the original paper, linked below.

TERMINOLOGY

Terminology about this stuff seems to vary. For clarity, this module uses the following:

<B>Consistent HashB> — The object you work with. Contains 0 or more targets, each with a weight.

<B>TargetB> — A member of the set. The weight (an arbitrary number), specifies how often it occurs relative to other targets.

CLASS METHODS

    new



  $set = Set::ConsistentHash->new;



Takes no options. Creates a new consistent hashing set with no targets. You’ll need to add them.

INSTANCE METHODS

    targets

Returns (alphabetically sorted) array of all targets in set.

    reset_targets

Remove all targets.

    set_targets



    $set->set_targets(%target_to_weight);
    $set->set_targets("foo" => 5, "bar" => 10);



Removes all targets, then sets the provided ones with the weightings provided.

    modify_targets



    $set->modify_targets(%target_to_weight);



Without removing existing targets, modifies the weighting of provided targets. A weight of undef or 0 removes an item from the set.

    set_target



    $set->set_target($target => $weight);



A wrapper around modify_targets that sounds better for modifying a single item.

    total_weight

Returns sum of all current targets’ weights.

    percent_weight



   $weight = $set->percent_weight($target);
   $weight = $set->percent_weight("10.0.0.2");



Returns number in range [0,100] representing percentage of weight that provided $target has.

    set_hash_func



    $set->set_hash_func(\&your_hash_func);



Sets the function with which keys will be hashed before looking up which target they will be mapped onto.

    get_target



    $selected_target = $set->get_target(your_hash_func($your_key));

    - or -

    $set->set_hash_func(\&your_hash_func);
    $selected_target = $set->get_target($your_key);



Given a key, select the target in the set to which that key is mapped.

If you find the target (say, a server) to be dead or otherwise unavailable, remove it from the set, and get the target again.

    buckets



    $selected_target = $set->buckets->[your_hash_func($your_key) % 1024];



Returns an arrayref of 1024 selected items from the set, in a consistent order.

This is what you want to use to actually select items quickly in your application.

If you find the target (say, a server) to be dead, or otherwise unavailable, remove it from the set, and look at that index in the bucket arrayref again.

INTERNALS

    _compute_buckets

Computes and returns an array of 1024 selected items from the set, in a consistent order.

    target_of_point



   $target = $set->target_of_point($point)



Given a $point, an integer in the range [0,2**32), returns (somewhat slowly), the next target found, clockwise from that point on the circle.

This is mostly an internal method, used to generated the 1024-element cached bucket arrayref when needed. You probably don’t want to use this. Instead, use the <B>bucketsB> method, and run your hash function on your key, generating an integer, modulous 1024, and looking up that bucket index’s target.

REFERENCES

<http://en.wikipedia.org/wiki/Consistent_hashing>

<http://www8.org/w8-papers/2a-webserver/caching/paper2.html>

AUTHOR

Brad Fitzpatrick — brad@danga.com

CONTRIBUTING

Bug, performance, doc, feature patch? See <http://contributing.appspot.com/set-consistenthash-perl>

COPYRIGHT & LICENSE

Copyright 2007, Six Apart, Ltd.

You’re granted permission to use this code under the same terms as Perl itself.

WARRANTY

This is free software. It comes with no warranty of any kind.
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 SET::CONSISTENTHASH (3) 2010-07-12

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.