1# ==== Purpose ==== 2# 3# Setup $rpl_sync_chain, which is used by rpl_sync.inc. You normally 4# don't need to source this file, it should only be sourced by 5# rpl_sync.inc. 6# 7# $rpl_sync_chain is set to a string that specifies in what order 8# servers should be synchronized in include/rpl_sync.inc. This has the 9# form of a sequence of "chains" (with no separator between two 10# chains). Each chain begins with $rpl_server_count_length space 11# characters, followed by a sequence of numbers, each number 12# whitespace-padded to $rpl_server_count_length characters. Each 13# number in the sequence denotes a server, and the N'th server is a 14# master of the (N+1)'th server. For example, if $rpl_topology is 15# '1->2,2->3,3->1,2->4,5->6', then $rpl_sync_chain is ' 56 123124'. 16# 17# 18# ==== Usage ==== 19# 20# [--let $rpl_debug= 1] 21# --source include/rpl_generate_sync_chain.inc 22# 23# Parameters: 24# $rpl_debug 25# See include/rpl_init.inc 26 27 28--let $include_filename= rpl_generate_sync_chain.inc 29--source include/begin_include_file.inc 30 31 32# Algorithm: 33# 0. Mark all servers as unseen and unsynced. 34# 1. Let S be a server that is marked unseen. 35# 2. Append S to the list of seen servers. 36# 3. Check how S is marked: 37# 3.1. If S has no master: append the list of seen servers (in 38# order from grand-master to grand-slave) to the end of 39# $rpl_sync_chain. Go to 3. 40# 3.2. Elseif S is marked as synced: append the list of seen 41# servers (in order from grand-master to grand-slave) to the 42# end of $rpl_sync_chain. Go to 3. 43# 3.3. Elseif S is marked as unsynced but seen: This means that the 44# graph of visited servers has a "6-shape": it is a loop with 45# a tail, such as 1->2->3->1->4->5. We should first sync the 46# loop, and then the tail. To ensure all servers in the loop 47# are synced, we must sync the loop two turns minus two 48# servers. For example, the loop 1->2->3->4->5->1 is fully 49# synced by this sequence of 1-step synchronizations: 50# 1->2->3->4->5->1->2->3->4. Hence we do this: in the list of 51# traversed servers (in order from grand-master to 52# grand-slave), find the first occurrence of S. Take the 53# sub-list starting at the 3rd server and ending at the first 54# occurrence of S. Append this sub-list it to the end of 55# $rpl_sync_chain. Then append the entire list of traversed 56# servers (in order from grand-master to grand-slave) to 57# $rpl_sync_chain. Go to 3. 58# 3.4. Else (i.e., S has a master and is not marked as seen or 59# synced): Mark S as seen. Set S=master(S) and go back to 2. 60# 4. For each server that is marked as seen, mark it as synced. 61# 5. If there are unseen servers, go back to 1. 62 63# $_rpl_server_marks holds the marks of all servers. The i'th character 64# corresponds to the mark of server i: 65# '0' = unseen & unmarked, '1' = seen & unsynced, '2' = seen & synced. 66--let $_rpl_server_marks= `SELECT REPEAT('0', $rpl_server_count)` 67--let $_rpl_start_server= $rpl_server_count 68--let $rpl_sync_chain= 69while ($_rpl_start_server) 70{ 71 --let $_rpl_server= `SELECT RPAD('$_rpl_start_server', $rpl_server_count_length, ' ')` 72 --let $_rpl_seen_list= 73 --let $_rpl_continue_loop= 1 74 while ($_rpl_continue_loop) 75 { 76 --let $_rpl_master= `SELECT SUBSTRING('$rpl_master_list', 1 + ($_rpl_server - 1) * $rpl_server_count_length, $rpl_server_count_length)` 77 # We need to delimit elements of $_rpl_seen_list with commas, so 78 # that LOCATE() below will not find spurious matches that begin in 79 # the middle of one element and end in the middle of next element. 80 --let $_rpl_seen_list= $_rpl_server,$_rpl_seen_list 81 # If server is marked seen or synced, or has no master 82 if (`SELECT SUBSTRING('$_rpl_server_marks', $_rpl_server, 1) != 0 OR '$_rpl_master' = ''`) 83 { 84 # If server is marked seen but not synced. 85 if (`SELECT SUBSTRING('$_rpl_server_marks', $_rpl_server, 1) = 1`) 86 { 87 # Get sub-list of servers to prepend to server list. 88 # E.g., if topology is 1->2->3->4->1->5, then at this point 89 # $_rpl_seen_list='1,2,3,4,1,5,' and we have to prepend '4,3,' 90 # to it. Hence, the sub-list starts at position 91 # 1+2*($rpl_server_count_length+1) and ends at the first 92 # occurrence of ',1,' in the list. 93 --let $_rpl_extra_list= `SELECT SUBSTRING('$_rpl_seen_list', 1 + 2 * ($rpl_server_count_length + 1), LOCATE(',$_rpl_server,', '$_rpl_seen_list') - 2 * ($rpl_server_count_length + 1))` 94 --let $_rpl_seen_list= $_rpl_extra_list$_rpl_seen_list 95 } 96 # Append the seen servers. Only need to append if the list 97 # contains at least two elements. 98 if (`SELECT LENGTH('$_rpl_seen_list') > $rpl_server_count_length + 1`) 99 { 100 --let $rpl_sync_chain= $rpl_sync_chain$_rpl_no_server$_rpl_seen_list 101 } 102 --let $_rpl_continue_loop= 0 103 } 104 --let $_rpl_server_marks= `SELECT INSERT('$_rpl_server_marks', $_rpl_server, 1, '1')` 105 --let $_rpl_server= $_rpl_master 106 } 107 # Mark seen servers as synced 108 --let $_rpl_server_marks= `SELECT REPLACE('$_rpl_server_marks', '1', '2')` 109 # Get highest-numbered unmarked server. 110 --let $_rpl_start_server= `SELECT IFNULL(NULLIF($rpl_server_count + 1 - LOCATE('0', REVERSE('$_rpl_server_marks')), $rpl_server_count + 1), 0)` 111} 112# Strip commas: they were only needed temporarily. 113--let $rpl_sync_chain= `SELECT REPLACE('$rpl_sync_chain', ',', '')` 114 115if ($rpl_debug) 116{ 117 --echo Generated \$rpl_sync_chain = '$rpl_sync_chain' 118} 119 120 121--let $include_filename= rpl_generate_sync_chain.inc 122--source include/end_include_file.inc 123