| 1 | package ShardedKV::Continuum::StaticMapping; | ||
| 2 | $ShardedKV::Continuum::StaticMapping::VERSION = '0.20'; | ||
| 3 | use Moose; | ||
| 4 | # ABSTRACT: A continuum strategy based on a simple "significant bits" static mapping | ||
| 5 | use JSON::XS qw(encode_json decode_json); | ||
| 6 | use Array::IntSpan; | ||
| 7 | use POSIX (); | ||
| 8 | |||
| 9 | with 'ShardedKV::Continuum'; | ||
| 10 | |||
| 11 | has 'num_significant_bits' => ( | ||
| 12 | is => 'ro', | ||
| 13 | isa => 'Int', | ||
| 14 | ); | ||
| 15 | |||
| 16 | # 2**num_significant_bits | ||
| 17 | has '_modulo' => ( | ||
| 18 | is => 'ro', | ||
| 19 | isa => 'Int', | ||
| 20 | ); | ||
| 21 | |||
| 22 | has '_min_key_length' => ( | ||
| 23 | is => 'ro', | ||
| 24 | isa => 'Int', | ||
| 25 | ); | ||
| 26 | |||
| 27 | has '_original_range_mapping' => ( | ||
| 28 | is => 'ro', | ||
| 29 | isa => 'ArrayRef[ArrayRef]', | ||
| 30 | ); | ||
| 31 | |||
| 32 | has '_intspan' => ( | ||
| 33 | is => 'ro', | ||
| 34 | isa => 'Array::IntSpan', | ||
| 35 | ); | ||
| 36 | |||
| 37 | # bypassing accessors, hot path | ||
| 38 | sub choose { | ||
| 39 | my ($self, $key) = @_; | ||
| 40 | |||
| 41 | die "Invalid key length: Need at least $self->{_min_key_length} bytes" | ||
| 42 | if length($key) < $self->{_min_key_length}; | ||
| 43 | |||
| 44 | my ($location) = unpack("V", $key); | ||
| 45 | return $self->{_intspan}->lookup($location % $self->{_modulo}); | ||
| 46 | } | ||
| 47 | |||
| 48 | sub serialize { | ||
| 49 | encode_json( { | ||
| 50 | num_significant_bits => $_[0]->num_significant_bits, | ||
| 51 | from => $_[0]->_original_range_mapping | ||
| 52 | } ) | ||
| 53 | } | ||
| 54 | |||
| 55 | sub deserialize { | ||
| 56 | my $class = shift; | ||
| 57 | return $class->new(decode_json( $_[1] )); | ||
| 58 | } | ||
| 59 | |||
| 60 | sub clone { | ||
| 61 | my $self = shift; | ||
| 62 | return ref($self)->new( | ||
| 63 | num_significant_bits => $self->num_significant_bits, | ||
| 64 | from => $self->_original_range_mapping | ||
| 65 | ); | ||
| 66 | } | ||
| 67 | |||
| 68 | sub extend { | ||
| 69 | my $self = shift; | ||
| 70 | my $spec = shift; | ||
| 71 | |||
| 72 | die "Extension not supported for StaticMapping at this time!"; | ||
| 73 | |||
| 74 | # TODO: To be figure out | ||
| 75 | # - How do you extend? In theory, we'd have to add a new range that takes over a part of a | ||
| 76 | # range from one or more others. This doesn't naturally allow for "take a bit of data from | ||
| 77 | # all other shards" which would be desireable for many key migration situations. | ||
| 78 | # - Should we support increasing the no. of significant bits? Ie. go from 10 to 11 (1024 to 2048 | ||
| 79 | # partitions) and thus simply double all ints in the ranges? How does this work with assigning | ||
| 80 | # actual semantics to the range numbers -- eg. for splitting into many tables in mysql? | ||
| 81 | # - Does this allow for natural distribution of data into $n tables on $m hosts? IOW, the | ||
| 82 | # value returned by choose() would identify the host and the table, but the table would be | ||
| 83 | # identified directly by the integer in the host range. This is a natural fit if we want | ||
| 84 | # to shard by promoting a database slave to a master for a subset of the data and then simply | ||
| 85 | # drop partitions or tables that are not required respectively on old or new machine. | ||
| 86 | # GAAH. | ||
| 87 | |||
| 88 | Carp::croak("StaticMapping spec must be an Array of Arrays, each inner record holding range start, end, and weight! This is not an array") | ||
| 89 | if not ref($spec) eq 'ARRAY'; | ||
| 90 | my @ranges = [sort {$a->[0] <=> $b->[0]} @$spec]; | ||
| 91 | my $orig_mapping = $self->_original_range_mapping; | ||
| 92 | my $prev = $orig_mapping->[-1][1]; | ||
| 93 | my $intspan = $self->_intspan; | ||
| 94 | foreach my $range (@ranges) { | ||
| 95 | Carp::croak("StaticMapping spec must be an Array of Arrays, each inner record " | ||
| 96 | . "holding range start, end, and weight! This particular record is not an array or does not hold three elements") | ||
| 97 | if not ref($range) eq 'ARRAY' and @$range == 3; | ||
| 98 | if ($range->[0] != $prev+1) { | ||
| 99 | Carp::croak("The lower boundary of any StaticMapping range needs to be one above the end of the previous" | ||
| 100 | ." range or 0 for the first range"); | ||
| 101 | } | ||
| 102 | my $overlapping = $intspan->set_range(@$range); | ||
| 103 | die("Assertion fail: range overlap!") | ||
| 104 | if $overlapping; | ||
| 105 | |||
| 106 | push @$orig_mapping, [@$range]; | ||
| 107 | $prev = $range->[1]; | ||
| 108 | } | ||
| 109 | } | ||
| 110 | |||
| 111 | sub get_bucket_names { | ||
| 112 | my $self = shift; | ||
| 113 | my $orig_mapping = $self->_original_range_mapping; | ||
| 114 | return map $_->[2], @$orig_mapping; | ||
| 115 | } | ||
| 116 | |||
| 117 | sub BUILD { | ||
| 118 | my $self = shift; | ||
| 119 | my $args = shift; | ||
| 120 | my $from = delete $args->{from}; | ||
| 121 | if (ref($from) eq 'ARRAY') { | ||
| 122 | my $mapping = [sort {$a->[0] <=> $b->[0]} @$from]; | ||
| 123 | $self->{_intspan} = $self->_make_intspan($mapping); | ||
| 124 | $self->{_original_range_mapping} = $mapping; | ||
| 125 | } | ||
| 126 | else { | ||
| 127 | die "Invalid 'from' specification for " . __PACKAGE__; | ||
| 128 | } | ||
| 129 | my $bits = $self->num_significant_bits; | ||
| 130 | $self->{_min_key_length} = POSIX::ceil($bits/8); | ||
| 131 | $self->{_modulo} = 2 ** $bits; | ||
| 132 | } | ||
| 133 | |||
| 134 | sub _make_intspan { | ||
| 135 | my $self = shift; | ||
| 136 | my $spec = shift; | ||
| 137 | |||
| 138 | Carp::croak("StaticMapping spec must be an Array of Arrays, each inner record holding range start, end, and weight! This is not an array") | ||
| 139 | if not ref($spec) eq 'ARRAY'; | ||
| 140 | my $prev = -1; | ||
| 141 | my $intspan = Array::IntSpan->new; | ||
| 142 | foreach my $range (@$spec) { | ||
| 143 | Carp::croak("StaticMapping spec must be an Array of Arrays, each inner record " | ||
| 144 | . "holding range start, end, and weight! This particular record is not an array or does not hold three elements") | ||
| 145 | if not ref($range) eq 'ARRAY' and @$range == 3; | ||
| 146 | if ($range->[0] != $prev+1) { | ||
| 147 | Carp::croak("The lower boundary of any StaticMapping range needs to be one above the end of the previous" | ||
| 148 | ." range or 0 for the first range"); | ||
| 149 | } | ||
| 150 | my $overlapping = $intspan->set_range(@$range); | ||
| 151 | die("Assertion fail: range overlap!") | ||
| 152 | if $overlapping; | ||
| 153 | $prev = $range->[1]; | ||
| 154 | } | ||
| 155 | |||
| 156 | return $intspan; | ||
| 157 | } | ||
| 158 | |||
| 159 | no Moose; | ||
| 160 | __PACKAGE__->meta->make_immutable; | ||
| 161 | |||
| 162 | __END__ |