ShardedKV/Continuum/StaticMapping.pm untested

filter: Statementstmt 0.0% 0 / 81 Branchbran 0.0% 0 / 20 Conditioncond 0.0% 0 / 6 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 0.0% 0 / 13 Podpod 0.0% 0 / 8 totaltotal 0.0% 0 / 132 CC 11 SCAR 27.0
CC
11
Cov
0%
extend
30.0
_make_intspan
30.0
choose
6.0
CRAP 14.9
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__