blib/lib/IPC/LeaderBoard.pm

filter: Statementstmt 99.0% 108 / 109 Branchbran 88.1% 37 / 42 Conditioncond 82.3% 14 / 17 MC/DCmcdc 63.6% 7 / 11 Subroutinesub 100% 16 / 16 Podpod 16.6% 1 / 6 totaltotal 91.0% 183 / 201 CC 29 SCAR 21.8
CC
29
Cov
95%
update
16.0
BUILD
10.3
DEMOLISH
3.0
CRAP 8.8
↑ Summary
1 package IPC::LeaderBoard;
2  
3 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 2 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 2 ▶use Fcntl ':flock'; # import LOCK_* constants
Subroutine BEGIN: called CC=1 SCAR=0.0
7 2 ▶use Guard;
Subroutine BEGIN: called CC=1 SCAR=0.0
8 2 ▶use IPC::ScoreBoard;
Subroutine BEGIN: called CC=1 SCAR=0.0
9 2 ▶use Moo;
Subroutine BEGIN: called CC=1 SCAR=0.0
10 2 ▶use Path::Tiny;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 2 ▶use namespace::clean;
Subroutine BEGIN: called CC=1 SCAR=0.0
12  
13 2 our $VERSION = '0.04';
14  
15 2 ▶my $max_lock_attempts = $ENV{IPC_LEADERBOARD_MAX_SPINLOCK_ATTEMPTS} // 10000;
Condition50%1/2
$ENV{"IPC_LEADERBOARD_MAX_SPINLOCK_ATTEMPTS"} // 10000
l!l
02
MC/DC0%0/1
$ENV{"IPC_LEADERBOARD_MAX_SPINLOCK_ATTEMPTS"} // 10000
$ENV{"IPC_LEADERBOARD_MAX_SPINLOCK_ATTEMPTS"}
Truth table50%1/2
A
A= $ENV{"IPC_LEADERBOARD_MAX_SPINLOCK_ATTEMPTS"}
Aresult
11
00
16  
17 =head1 NAME
18  
19 IPC::LeaderBoard - fast per-symbol online get/update information
20  
21 =head1 VERSION
22  
23 0.02
24  
25 =head1 STATUS
26  
27 =begin HTML
28  
29 <p>
30 <a href="https://travis-ci.org/binary-com/perl-IPC-LeaderBoard"><img src="https://travis-ci.org/binary-com/perl-IPC-LeaderBoard.svg" /></a>
31 </p>
32  
33 =end HTML
34  
35  
36 =head1 SYNOPSIS
37  
38 use IPC::LeaderBoard;
39  
40 # in master-process
41 my $master = IPC::LeaderBoard::create(
42 n_slots => 2, # number of symbols
43 slot_shared_size => 4, # number integers per slot, concurrent access
44 slot_private_size => 2, # number integers per slot, non-concurrent access
45 mmaped_file => "/var/run/data/my.scores", # mmaped file
46 );
47 # ... initialize data here
48  
49 # in slave processes
50 my $slave = IPC::LeaderBoard::attach(
51 # exactly the same parameters as for master
52 );
53  
54 my $leader_board = $slave; # or $master, does not matter
55  
56 # get shared and private arrays of integers for the 0-th slot
57 my ($shared, $private) = $leader_board->read_slot(0);
58  
59 # update shared integers with values 1,2,3,4 and 0-th private integer
60 # with value 6
61 my $success = $leader_board->update(0, [1, 2, 3, 4], 0 => 6, 1 => 8);
62  
63 # $shared = [1, 2, 3, 4], $private = [6, 8]
64 ($shared, $private) = $leader_board->read_slot(0);
65  
66 # update just private integer with index 1 with value 2
67 $leader_board->update(0, 1 => 2);
68  
69 # update just shared values of 0-th slot
70 $success = $leader_board->update(0, [1, 2, 3, 4]);
71  
72 =head1 DESCRIPTION
73  
74 LeaderBoard uses shared memory IPC to fast set/get integers on arbitrary row,
75 (slot) defined by it's index.
76  
77 There are the following assumptions:
78  
79 =over 2
80  
81 =item * only one master is present
82  
83 C<create> method dies, if it founds that some other master ownes shared
84 memory (file lock is used for that).
85  
86 =item * master is launched before slaves
87  
88 C<attach> dies, if slave finds, that master-owner isn't present, or,
89 if it presents, the masters provider/symbol information isn't actual.
90 In the last case master should be restarted first.
91  
92 =item * there is no hot-deploy mechanism
93  
94 Just restart master/slaves
95  
96 =item * read slot before update it
97  
98 The vesion/generation pattern is used do detect, whether update
99 has been successfull or not. Update failure means, some other
100 C<LeaderBoard> instance updated the slot; you should re-read it
101 and try uptate it again (if the update will be still actual after
102 data refresh)
103  
104 =item * no semantical difference between slave and master
105  
106 Master was introduced to lock leadear board to prevent other masters
107 connect to it and re-initialize (corrupt) data. After attach slave validates,
108 that LeaderBoard is valid (i.e. number of slots, as well as the sizes
109 of private and shared areas match to the declared).
110  
111 Hence, master can be presented only by one instance, while slaves
112 can be presented by multiple instances.
113  
114 =item * slot data organization and consistency
115  
116 A leaderboard is an array of slots of the same size:
117  
118 +------------------------------------------------------------------------+
119 | slot 1 |
120 +------------------------------------------------------------------------+
121 | slot 2 |
122 +------------------------------------------------------------------------+
123 | ... |
124 +------------------------------------------------------------------------+
125 | slot N |
126 +------------------------------------------------------------------------+
127  
128 A slot is addressed by its index.
129  
130 Each slot contains a spin-lock, a shared part, a generation field and a private part like
131  
132 It is supposed, that only leader (independent for each slot) will update the shared part,
133 while other competitors will update only own private parts, i.e.:
134  
135 | | shared part | | private part |
136 | spin | | gene- | process1 | process2 | process3 |
137 | lock | shr1 | shr2 | ... | shrN | ration | p1 | p2 | ... | pN | p1 | p2 | ... | pN | p1 | p2 | ... | pN |
138  
139 All values (shrX and pX) in the leaderboard are integer numbers. Only the current leader updates
140 the shared part, and does that in safe manner (i.e. protected by spin-lock and generation). Each process can
141 update its own private part of a slot.
142  
143 Read or write for integer values (shr1, p1, ..) read/write B<atomicity> is guaranteed
144 by L<IPC::ScoreBoard>, which in the final, uses special CPU-instructions for that.
145  
146 The SpinLock pattern guarantees the safety of shared part update, i.e. in
147 the case of two or more concurrent write request, they will be done in
148 sequential manner.
149  
150 The Generation pattern guarantees that you update the most recent values
151 in the shared part of the slot, i.e. if some process updated shared
152 part of the slot, between slot read and update operations of the
153 current process, than, the update request of the current process
154 would fail. You have re-read the slot, and try to update it again, but
155 after re-read the update might be not required.
156  
157 Both SpinLock and Generation patterns guarantee, that you'll never
158 can made inconsistent C<update>, or updating non-actual data.
159  
160 In the same time, you might end up with the inconsistent C<read_slot>
161 of the shared data: the individual values (integer) are consistent (atomic),
162 but you they might belong to the different generations. There is an assumption
163 in the C<LeaderBoard> design, that it is B<fine>: would you try to update
164 the shared data, the C<update> will fail, hence, no any harm will occur. If
165 you need to handle that, just check return value C<update>.
166  
167 There are no any guarantees for slot private data; but it isn't needed.
168 The shared data should store information about leader, hence when a
169 new leader arrives, it updates the information; or the current leader update
170 it's information on the LeaderBoard in the appropriate slot. No data loss might
171 occur.
172  
173 When competitor (i.e. some process) updates private data, nobody else
174 can update it (i.e. you shouldn't write progam such a way, that one
175 process-competitor updates data of the other process-competitor), hence,
176 private data cannot be corrupted if used properly.
177  
178 The private data might be inconsistent on read (e.g. competitor1 reads
179 private data of competitor2, while it is half-updated by competitor2);
180 but that shoudl be B<insignificant for the sake of speed>. If it is
181 significant, use shared memory for that, re-design your approach (e.g
182 use additional slots) or use some other module.
183  
184 =back
185  
186 The update process should be rather simple: C<killall $slave_1, $slave_2, ... $master>
187 and then start all together. C<create> / C<attach> should be wrappend into
188 C<eval> (or C<Try::Tiny> & friends), to repeat seveal attempts with some delay.
189  
190 The C<update> method might fail, (i.e. it does not returns true), when it detects,
191 that somebody else already has changed an row. It is assumed that no any harm
192 in it. If needed the row can be refreshed (re-read), and the next update
193 might be successfull.
194  
195 It is assumed, that if C<read> returs outdated data and the C<update> decision
196 has been taken, than update will silently fail (return false), without any
197 loud exceptions; so, the next read-update cycle might be successful, but
198 probably, the updated values are already correct, so, no immediate update
199 would occur.
200  
201 =for Pod::Coverage BUILD DEMOLISH attach create mmaped_file n_slots read_slot slot_private_size slot_shared_size
202  
203 =cut
204  
205 2 has mmaped_file => (
206 is => 'ro',
207 required => 1
208 );
209  
210 2 has n_slots => (
211 is => 'ro',
212 required => 1
213 );
214  
215 2 has slot_shared_size => (
216 is => 'ro',
217 required => 1
218 );
219  
220 2 has slot_private_size => (
221 is => 'ro',
222 required => 1
223 );
224  
225 2 has _mode => (
226 is => 'ro',
227 required => 1
228 );
229  
230 2 has _score_board => (is => 'rw');
231 2 has _fd => (is => 'rw');
232 2 has _generation_idx => (is => 'rw');
233 2 has _last_generation => (is => 'rw');
234 has _last_idx => (
235 is => 'rw',
236 12 ▶ default => sub { -1 });
Subroutine __ANON__: called CC=1 SCAR=0.0
237  
238 12 ▶sub BUILD {
Subroutine BUILD: called CC=10 SCAR=23.3
Pod undocumented
239 12 my $self = shift;
240 12 my $mode = $self->_mode;
241 12 ▶ die("unknown mode '$mode'") unless $mode =~ /(slave)|(master)/;
Branch: 1 branch
BranchTrueFalseTotal
unless $mode =~ /(slave)|(master)/ 0 12 12
242  
243 # construct ids (number, actually the order) for all symbols
244 # and providers. Should be sorted to guaranttee the same
245 # ids in different proccess
246 # There is an assumption, that processes, using LeaderBoard, should
247 # restarte in case of symbols/providers change.
248  
249 12 my $filename = $self->mmaped_file;
250 12 ▶ if (!(-e $filename) && ($mode eq 'slave')) {
Branch: 1 branch
BranchTrueFalseTotal
if (not -e $filename and $mode eq "slave") 0 12 12
Condition66%2/3
not -e $filename and $mode eq "slave"
!ll&&!rl&&r
1110
MC/DC0%0/2
not -e $filename and $mode eq "slave"
not -e $filename $mode eq "slave"
Truth table66%2/3
not(A) and B
A= not -e $filenameB= $mode eq "slave"
ABresult
0X0
100
111
251 0 die("LeaderBoard ($filename) is abandoned, cannot attach to it (file not exists)");
252 }
253  
254 12 my $scoreboard_path = path($filename);
255 12 ▶ $scoreboard_path->touch if !-e $filename;
Branch: 1 branch
BranchTrueFalseTotal
unless -e $filename 1 11 12
256 12 my $fd = $scoreboard_path->filehandle('<');
257  
258 12 my $score_board;
259 12 ▶ if ($mode eq 'slave') {
Branch: 1 branch
BranchTrueFalseTotal
if ($mode eq 'slave') { } 7 5 12
260 # die, if slave was able to lock it, that means, that master
261 # didn't accquired the exclusive lock, i.e. no master
262 7 ▶ flock($fd, LOCK_SH | LOCK_NB)
Branch: 1 branch
BranchTrueFalseTotal
flock $fd, 5 and die "LeaderBoard ($filename) is abandoned, cannot attach to it (shared lock obtained)" 1 6 7
263 && die("LeaderBoard ($filename) is abandoned, cannot attach to it (shared lock obtained)");
264 6 my ($sb, $nslots, $slotsize) = IPC::ScoreBoard->open($filename);
265 # just additional check, that providers/symbols information is actual
266 6 my $declared_size = $self->slot_shared_size + $self->slot_private_size + 2;
267 6 ▶ die("number of slots mismatch") unless $nslots == $self->n_slots;
Branch: 1 branch
BranchTrueFalseTotal
unless $nslots == $self->n_slots 0 6 6
268 6 ▶ die("slot size mismatch") unless $slotsize == $declared_size;
Branch: 1 branch
BranchTrueFalseTotal
unless $slotsize == $declared_size 0 6 6
269 6 $score_board = $sb;
270 } else {
271 # die if we can't lock it, that means, another master-process
272 # already acquired it
273 5 ▶ flock($fd, LOCK_EX | LOCK_NB)
Branch: 1 branch
BranchTrueFalseTotal
flock $fd, 6 or die "LeaderBoard ($filename) is owned by some other process, cannot lock it exclusively" 4 1 5
274 || die("LeaderBoard ($filename) is owned by some other process, cannot lock it exclusively");
275 # we use the addtitional fields: for spinlock and generation
276 4 my $declared_size = $self->slot_shared_size + $self->slot_private_size + 2;
277 4 $score_board = IPC::ScoreBoard->named($filename, $self->n_slots, $declared_size, 0);
278 4 $self->_fd($fd);
279 }
280 10 $self->_generation_idx($self->slot_shared_size + 1); # [spin_lock | shared_data | generation | private_data ]
281 10 $self->_score_board($score_board);
282 10 return;
283 }
284  
285 12 ▶sub DEMOLISH {
Subroutine DEMOLISH: called CC=3 SCAR=11.0
Pod undocumented
286 12 my $self = shift;
287 # actually we need that only for tests
288 12 ▶ if ($self->_mode eq 'master') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_mode eq "master") 5 7 12
289 5 ▶ flock($self->_fd, LOCK_UN) if ($self->_fd);
Branch: 1 branch
BranchTrueFalseTotal
if $self->_fd 4 1 5
290 }
291 12 return;
292 }
293  
294 7 ▶sub attach {
Subroutine attach: called CC=1 SCAR=0.0
Pod undocumented
295 7 return IPC::LeaderBoard->new({
296 _mode => 'slave',
297 @_,
298 });
299 }
300  
301 5 ▶sub create {
Subroutine create: called CC=1 SCAR=0.0
Pod undocumented
302 5 return IPC::LeaderBoard->new({
303 _mode => 'master',
304 @_,
305 });
306 }
307  
308 # our use-case implies, that if we read a bit outdated data, this is OK, because
309 # the generation field will be outdated, hence, no update would occur
310 12 ▶sub read_slot {
Subroutine read_slot: called CC=3 SCAR=11.0
Pod undocumented
311 12 my ($self, $idx) = @_;
312 12 ▶ die("wrong index") if ($idx >= $self->n_slots) || $idx < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $idx >= $self->n_slots or $idx < 0 2 10 12
Condition100%3/3
$idx >= $self->n_slots or $idx < 0
l!l&&r!l&&!r
1110
MC/DC100%2/2
$idx >= $self->n_slots or $idx < 0
$idx >= $self->n_slots $idx < 0
Truth table100%3/3
A or B
A= $idx >= $self->n_slotsB= $idx < 0
ABresult
1X1
011
000
313  
314 10 my @all_values = $self->_score_board->get_all($idx);
315 # drop spinlock and generation
316 10 my $generation = splice @all_values, $self->_generation_idx, 1;
317 10 splice @all_values, 0, 1;
318  
319 # record generation + index for further possible update
320 10 $self->_last_idx($idx);
321 10 $self->_last_generation($generation);
322  
323 # separate shared and private data
324 10 my $shared_size = $self->slot_shared_size;
325 10 my @shared_values = @all_values[0 .. $shared_size - 1];
326 10 my @private_values = @all_values[$shared_size .. $shared_size + $self->slot_private_size - 1];
327  
328 10 return \@shared_values, \@private_values;
329 }
330  
331 12 ▶sub update {
Subroutine update: called CC=16 SCAR=27.7
Pod documented
332 12 my ($self, $idx, @rest) = @_;
333 12 ▶ my $values = (@rest && ref($rest[0]) eq 'ARRAY') ? shift(@rest) : undef;
Branch: 1 branch
BranchTrueFalseTotal
@rest && ref $rest[0] eq 'ARRAY' ? : 9 3 12
Condition66%2/3
@rest and ref $rest[0] eq "ARRAY"
!ll&&!rl&&r
039
MC/DC50%1/2
@rest and ref $rest[0] eq "ARRAY"
@rest ref $rest[0] eq "ARRAY"
Truth table66%2/3
A and B
A= @restB= ref $rest[0] eq "ARRAY"
ABresult
0X0
100
111
334 12 my %private_values = @rest;
335 12 my $operation_result = 0;
336 12 ▶ die("wrong index") if ($idx >= $self->n_slots) || $idx < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $idx >= $self->n_slots or $idx < 0 2 10 12
Condition100%3/3
$idx >= $self->n_slots or $idx < 0
l!l&&r!l&&!r
1110
MC/DC100%2/2
$idx >= $self->n_slots or $idx < 0
$idx >= $self->n_slots $idx < 0
Truth table100%3/3
A or B
A= $idx >= $self->n_slotsB= $idx < 0
ABresult
1X1
011
000
337 10 ▶ die("update for only last read index is allowed") if $idx != $self->_last_idx;
Branch: 1 branch
BranchTrueFalseTotal
if $idx != $self->_last_idx 0 10 10
338  
339 10 my $sb = $self->_score_board;
340  
341 # updating shared values
342 10 ▶ if ($values) {
Branch: 1 branch
BranchTrueFalseTotal
if ($values) 7 3 10
343 7 ▶ die("values size mismatch slot size") if @$values != $self->slot_shared_size;
Branch: 1 branch
BranchTrueFalseTotal
if @$values != $self->slot_shared_size 2 5 7
344  
345 # obtain spin-lock
346 5 my $attempts = 0;
347 5 ▶ while ($sb->incr($idx, 0) != 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($sb->incr($idx, 0) != 1) 10001 4 10005
348 10001 $sb->decr($idx, 0);
349 10001 ▶ if (++$attempts > $max_lock_attempts) {
Branch: 1 branch
BranchTrueFalseTotal
if (++$attempts > $max_lock_attempts) 1 10000 10001
350 1 warn("failed to acquire spin lock for row $idx after $attempts attempts");
351 1 return 0;
352 }
353 }
354 # release the lock at the end of the scope
355 4 ▶ scope_guard { $sb->decr($idx, 0) };
Subroutine __ANON__: called CC=1 SCAR=0.0
356  
357 # now we hold the record, nobody else can update it.
358 # Atomically read generation value via increment it to zero.
359 # The simple $sb->get(...) cannot be used, because it does not guarantees
360 # atomicity, i.e. slot re-write is possible due to L1/L2 caches in CPU
361 4 my $actual_generation = $sb->incr($idx, $self->_generation_idx, 0);
362 4 ▶ if ($actual_generation == $self->_last_generation) {
Branch: 1 branch
BranchTrueFalseTotal
if ($actual_generation == $self->_last_generation) 2 2 4
363 # now we are sure, that nobody else updated the record since our last read
364 # so we can safely update it
365  
366 # +1 because the 1st field is spinlock
367 2 $sb->set($idx, $_ + 1, $values->[$_]) for (0 .. @$values - 1);
368 # increment the generation field
369 2 $sb->incr($idx, $self->_generation_idx);
370 # success
371 2 $operation_result = 1;
372 }
373 }
374  
375 # updating private values
376 7 ▶ if (%private_values) {
Branch: 1 branch
BranchTrueFalseTotal
if (%private_values) 6 1 7
377 6 my $idx_delta = $self->_generation_idx + 1;
378 6 for my $private_idx (keys %private_values) {
379 7 my $value = $private_values{$private_idx};
380 7 ▶ if (($private_idx >= $self->slot_private_size) || ($private_idx < 0)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($private_idx >= $self->slot_private_size or $private_idx < 0) 2 5 7
Condition100%3/3
$private_idx >= $self->slot_private_size or $private_idx < 0
l!l&&r!l&&!r
115
MC/DC100%2/2
$private_idx >= $self->slot_private_size or $private_idx < 0
$private_idx >= $self->slot_private_size $private_idx < 0
Truth table100%3/3
A or B
A= $private_idx >= $self->slot_private_sizeB= $private_idx < 0
ABresult
1X1
011
000
381 2 die("wrong private index");
382 }
383 5 $sb->set($idx, $private_idx + $idx_delta, $value);
384 }
385 }
386  
387 5 return $operation_result;
388 }
389  
390 =head1 AUTHOR
391  
392 binary.com, C<< <perl at binary.com> >>
393  
394 =head1 BUGS
395  
396 Please report any bugs or feature requests to
397 L<https://github.com/binary-com/perl-IPC-LeaderBoard/issues>.
398  
399 =cut
400  
401 2 1;
↑ Summary