Vitaliy Filippov
a2278be84d
This greatly speeds up PG placement and makes it more uniform both because the LP task becomes simpler and because the distribution of individual OSDs is optimised manually
558 lines
17 KiB
JavaScript
558 lines
17 KiB
JavaScript
// Copyright (c) Vitaliy Filippov, 2019+
|
|
// License: VNPL-1.1 (see README.md for details)
|
|
|
|
// Data distribution optimizer using linear programming (lp_solve)
|
|
|
|
const child_process = require('child_process');
|
|
|
|
const NO_OSD = 'Z';
|
|
|
|
async function lp_solve(text)
|
|
{
|
|
const cp = child_process.spawn('lp_solve');
|
|
let stdout = '', stderr = '', finish_cb;
|
|
cp.stdout.on('data', buf => stdout += buf.toString());
|
|
cp.stderr.on('data', buf => stderr += buf.toString());
|
|
cp.on('exit', () => finish_cb && finish_cb());
|
|
cp.stdin.write(text);
|
|
cp.stdin.end();
|
|
if (cp.exitCode == null)
|
|
{
|
|
await new Promise(ok => finish_cb = ok);
|
|
}
|
|
if (!stdout.trim())
|
|
{
|
|
return null;
|
|
}
|
|
let score = 0;
|
|
let vars = {};
|
|
for (const line of stdout.split(/\n/))
|
|
{
|
|
let m = /^(^Value of objective function: (-?[\d\.]+)|Actual values of the variables:)\s*$/.exec(line);
|
|
if (m)
|
|
{
|
|
if (m[2])
|
|
{
|
|
score = m[2];
|
|
}
|
|
continue;
|
|
}
|
|
else if (/This problem is (infeasible|unbounded)/.exec(line))
|
|
{
|
|
return null;
|
|
}
|
|
let [ k, v ] = line.trim().split(/\s+/, 2);
|
|
if (v)
|
|
{
|
|
vars[k] = v;
|
|
}
|
|
}
|
|
return { score, vars };
|
|
}
|
|
|
|
// osd_weights = { [id]: weight }
|
|
async function optimize_initial({ osd_weights, combinator, pg_count, pg_size = 3, pg_minsize = 2, parity_space = 1, ordered = false })
|
|
{
|
|
if (!pg_count || !osd_weights)
|
|
{
|
|
return null;
|
|
}
|
|
const total_weight = Object.values(osd_weights).reduce((a, c) => Number(a) + Number(c), 0);
|
|
const all_pgs = Object.values(make_cyclic(combinator.random_combinations(), parity_space));
|
|
const pg_per_osd = {};
|
|
for (const pg of all_pgs)
|
|
{
|
|
for (let i = 0; i < pg.length; i++)
|
|
{
|
|
const osd = pg[i];
|
|
pg_per_osd[osd] = pg_per_osd[osd] || [];
|
|
pg_per_osd[osd].push((i >= pg_minsize ? parity_space+'*' : '')+"pg_"+pg.join("_"));
|
|
}
|
|
}
|
|
let pg_effsize = all_pgs.reduce((a, c) => Math.max(a, c.filter(e => e != NO_OSD).length), 0);
|
|
pg_effsize = Math.min(pg_minsize, pg_effsize) + Math.max(0, Math.min(pg_size, pg_effsize) - pg_minsize) * parity_space;
|
|
let lp = '';
|
|
lp += "max: "+all_pgs.map(pg => 'pg_'+pg.join('_')).join(' + ')+";\n";
|
|
for (const osd in pg_per_osd)
|
|
{
|
|
if (osd !== NO_OSD)
|
|
{
|
|
let osd_pg_count = osd_weights[osd]/total_weight*pg_effsize*pg_count;
|
|
lp += pg_per_osd[osd].join(' + ')+' <= '+osd_pg_count+';\n';
|
|
}
|
|
}
|
|
for (const pg of all_pgs)
|
|
{
|
|
lp += 'pg_'+pg.join('_')+" >= 0;\n";
|
|
}
|
|
lp += "sec "+all_pgs.map(pg => 'pg_'+pg.join('_')).join(', ')+";\n";
|
|
const lp_result = await lp_solve(lp);
|
|
if (!lp_result)
|
|
{
|
|
console.log(lp);
|
|
throw new Error('Problem is infeasible or unbounded - is it a bug?');
|
|
}
|
|
const int_pgs = make_int_pgs(lp_result.vars, pg_count, ordered);
|
|
const eff = pg_list_space_efficiency(int_pgs, osd_weights, pg_minsize, parity_space);
|
|
const res = {
|
|
score: lp_result.score,
|
|
weights: lp_result.vars,
|
|
int_pgs,
|
|
pg_effsize,
|
|
space: eff * pg_effsize,
|
|
total_space: total_weight,
|
|
};
|
|
return res;
|
|
}
|
|
|
|
function make_cyclic(pgs, parity_space)
|
|
{
|
|
if (parity_space > 1)
|
|
{
|
|
for (const pg in pgs)
|
|
{
|
|
for (let i = 1; i < pg.size; i++)
|
|
{
|
|
const cyclic = [ ...pg.slice(i), ...pg.slice(0, i) ];
|
|
pgs['pg_'+cyclic.join('_')] = cyclic;
|
|
}
|
|
}
|
|
}
|
|
return pgs;
|
|
}
|
|
|
|
function shuffle(array)
|
|
{
|
|
for (let i = array.length - 1, j, x; i > 0; i--)
|
|
{
|
|
j = Math.floor(Math.random() * (i + 1));
|
|
x = array[i];
|
|
array[i] = array[j];
|
|
array[j] = x;
|
|
}
|
|
}
|
|
|
|
function make_int_pgs(weights, pg_count, round_robin)
|
|
{
|
|
const total_weight = Object.values(weights).reduce((a, c) => Number(a) + Number(c), 0);
|
|
let int_pgs = [];
|
|
let pg_left = pg_count;
|
|
let weight_left = total_weight;
|
|
for (const pg_name in weights)
|
|
{
|
|
let cur_pg = pg_name.substr(3).split('_');
|
|
let n = Math.round(weights[pg_name] / weight_left * pg_left);
|
|
for (let i = 0; i < n; i++)
|
|
{
|
|
int_pgs.push([ ...cur_pg ]);
|
|
if (round_robin)
|
|
{
|
|
cur_pg.push(cur_pg.shift());
|
|
}
|
|
}
|
|
weight_left -= weights[pg_name];
|
|
pg_left -= n;
|
|
}
|
|
shuffle(int_pgs);
|
|
return int_pgs;
|
|
}
|
|
|
|
function calc_intersect_weights(old_pg_size, pg_size, pg_count, prev_weights, all_pgs, ordered)
|
|
{
|
|
const move_weights = {};
|
|
if ((1 << old_pg_size) < pg_count)
|
|
{
|
|
const intersect = {};
|
|
for (const pg_name in prev_weights)
|
|
{
|
|
const pg = pg_name.substr(3).split(/_/);
|
|
for (let omit = 1; omit < (1 << old_pg_size); omit++)
|
|
{
|
|
let pg_omit = [ ...pg ];
|
|
let intersect_count = old_pg_size;
|
|
for (let i = 0; i < old_pg_size; i++)
|
|
{
|
|
if (omit & (1 << i))
|
|
{
|
|
pg_omit[i] = '';
|
|
intersect_count--;
|
|
}
|
|
}
|
|
if (!ordered)
|
|
pg_omit = pg_omit.filter(n => n).sort();
|
|
pg_omit = pg_omit.join(':');
|
|
intersect[pg_omit] = Math.max(intersect[pg_omit] || 0, intersect_count);
|
|
}
|
|
}
|
|
for (const pg of all_pgs)
|
|
{
|
|
let max_int = 0;
|
|
for (let omit = 1; omit < (1 << pg_size); omit++)
|
|
{
|
|
let pg_omit = [ ...pg ];
|
|
for (let i = 0; i < pg_size; i++)
|
|
{
|
|
if (omit & (1 << i))
|
|
pg_omit[i] = '';
|
|
}
|
|
if (!ordered)
|
|
pg_omit = pg_omit.filter(n => n).sort();
|
|
pg_omit = pg_omit.join(':');
|
|
max_int = Math.max(max_int, intersect[pg_omit] || 0);
|
|
}
|
|
move_weights['pg_'+pg.join('_')] = pg_size-max_int;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
const prev_pg_hashed = Object.keys(prev_weights).map(pg_name => pg_name
|
|
.substr(3).split(/_/).reduce((a, c, i) => { a[c] = i+1; return a; }, {}));
|
|
for (const pg of all_pgs)
|
|
{
|
|
if (!prev_weights['pg_'+pg.join('_')])
|
|
{
|
|
let max_int = 0;
|
|
for (const prev_hash of prev_pg_hashed)
|
|
{
|
|
const intersect_count = ordered
|
|
? pg.reduce((a, osd, i) => a + (prev_hash[osd] == 1+i ? 1 : 0), 0)
|
|
: pg.reduce((a, osd) => a + (prev_hash[osd] ? 1 : 0), 0);
|
|
if (max_int < intersect_count)
|
|
{
|
|
max_int = intersect_count;
|
|
if (max_int >= pg_size)
|
|
{
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
move_weights['pg_'+pg.join('_')] = pg_size-max_int;
|
|
}
|
|
}
|
|
}
|
|
return move_weights;
|
|
}
|
|
|
|
// Try to minimize data movement
|
|
async function optimize_change({ prev_pgs: prev_int_pgs, osd_weights, combinator, pg_size = 3, pg_minsize = 2, parity_space = 1, ordered = false })
|
|
{
|
|
if (!osd_weights)
|
|
{
|
|
return null;
|
|
}
|
|
// FIXME: use parity_chunks with parity_space instead of pg_minsize
|
|
let all_pgs = make_cyclic(combinator.random_combinations(), parity_space);
|
|
let pg_effsize = Object.values(all_pgs).reduce((a, c) => Math.max(a, c.filter(e => e != NO_OSD).length), 0);
|
|
pg_effsize = Math.min(pg_minsize, pg_effsize) + Math.max(0, Math.min(pg_size, pg_effsize) - pg_minsize) * parity_space;
|
|
const pg_count = prev_int_pgs.length;
|
|
const prev_weights = {};
|
|
const prev_pg_per_osd = {};
|
|
for (const pg of prev_int_pgs)
|
|
{
|
|
const pg_name = 'pg_'+pg.join('_');
|
|
prev_weights[pg_name] = (prev_weights[pg_name]||0) + 1;
|
|
for (let i = 0; i < pg.length; i++)
|
|
{
|
|
const osd = pg[i];
|
|
prev_pg_per_osd[osd] = prev_pg_per_osd[osd] || [];
|
|
prev_pg_per_osd[osd].push([ pg_name, (i >= pg_minsize ? parity_space : 1) ]);
|
|
}
|
|
}
|
|
const old_pg_size = prev_int_pgs[0].length;
|
|
// Get all combinations
|
|
if (old_pg_size == pg_size)
|
|
{
|
|
const still_valid = combinator.check_combinations(Object.keys(prev_weights).map(pg_name => pg_name.substr(3).split('_')));
|
|
for (const pg of still_valid)
|
|
{
|
|
all_pgs['pg_'+pg.join('_')] = pg;
|
|
}
|
|
}
|
|
all_pgs = Object.values(all_pgs);
|
|
const pg_per_osd = {};
|
|
for (const pg of all_pgs)
|
|
{
|
|
const pg_name = 'pg_'+pg.join('_');
|
|
for (let i = 0; i < pg.length; i++)
|
|
{
|
|
const osd = pg[i];
|
|
pg_per_osd[osd] = pg_per_osd[osd] || [];
|
|
pg_per_osd[osd].push([ pg_name, (i >= pg_minsize ? parity_space : 1) ]);
|
|
}
|
|
}
|
|
// Penalize PGs based on their similarity to old PGs
|
|
const move_weights = calc_intersect_weights(old_pg_size, pg_size, pg_count, prev_weights, all_pgs, ordered);
|
|
// Calculate total weight - old PG weights
|
|
const all_pg_names = all_pgs.map(pg => 'pg_'+pg.join('_'));
|
|
const all_pgs_hash = all_pg_names.reduce((a, c) => { a[c] = true; return a; }, {});
|
|
const total_weight = Object.values(osd_weights).reduce((a, c) => Number(a) + Number(c), 0);
|
|
// Generate the LP problem
|
|
let lp = '';
|
|
lp += 'max: '+all_pg_names.map(pg_name => (
|
|
prev_weights[pg_name] ? `${pg_size+1}*add_${pg_name} - ${pg_size+1}*del_${pg_name}` : `${pg_size+1-move_weights[pg_name]}*${pg_name}`
|
|
)).join(' + ')+';\n';
|
|
for (const osd in pg_per_osd)
|
|
{
|
|
if (osd !== NO_OSD)
|
|
{
|
|
const osd_sum = (pg_per_osd[osd]||[]).map(([ pg_name, space ]) => (
|
|
prev_weights[pg_name] ? `${space} * add_${pg_name} - ${space} * del_${pg_name}` : `${space} * ${pg_name}`
|
|
)).join(' + ');
|
|
const rm_osd_pg_count = (prev_pg_per_osd[osd]||[])
|
|
.reduce((a, [ old_pg_name, space ]) => (a + (all_pgs_hash[old_pg_name] ? space : 0)), 0);
|
|
const osd_pg_count = osd_weights[osd]*pg_effsize/total_weight*pg_count - rm_osd_pg_count;
|
|
lp += osd_sum + ' <= ' + osd_pg_count + ';\n';
|
|
}
|
|
}
|
|
let pg_vars = [];
|
|
for (const pg_name of all_pg_names)
|
|
{
|
|
if (prev_weights[pg_name])
|
|
{
|
|
pg_vars.push(`add_${pg_name}`, `del_${pg_name}`);
|
|
// Can't add or remove less than zero
|
|
lp += `add_${pg_name} >= 0;\n`;
|
|
lp += `del_${pg_name} >= 0;\n`;
|
|
// Can't remove more than the PG already has
|
|
lp += `add_${pg_name} - del_${pg_name} >= -${prev_weights[pg_name]};\n`;
|
|
}
|
|
else
|
|
{
|
|
pg_vars.push(pg_name);
|
|
lp += `${pg_name} >= 0;\n`;
|
|
}
|
|
}
|
|
lp += 'sec '+pg_vars.join(', ')+';\n';
|
|
// Solve it
|
|
const lp_result = await lp_solve(lp);
|
|
if (!lp_result)
|
|
{
|
|
console.log(lp);
|
|
throw new Error('Problem is infeasible or unbounded - is it a bug?');
|
|
}
|
|
// Generate the new distribution
|
|
const weights = { ...prev_weights };
|
|
for (const k in prev_weights)
|
|
{
|
|
if (!all_pgs_hash[k])
|
|
{
|
|
delete weights[k];
|
|
}
|
|
}
|
|
for (const k in lp_result.vars)
|
|
{
|
|
if (k.substr(0, 4) === 'add_')
|
|
{
|
|
weights[k.substr(4)] = (weights[k.substr(4)] || 0) + Number(lp_result.vars[k]);
|
|
}
|
|
else if (k.substr(0, 4) === 'del_')
|
|
{
|
|
weights[k.substr(4)] = (weights[k.substr(4)] || 0) - Number(lp_result.vars[k]);
|
|
}
|
|
else if (k.substr(0, 3) === 'pg_')
|
|
{
|
|
weights[k] = Number(lp_result.vars[k]);
|
|
}
|
|
}
|
|
for (const k in weights)
|
|
{
|
|
if (!weights[k])
|
|
{
|
|
delete weights[k];
|
|
}
|
|
}
|
|
const int_pgs = make_int_pgs(weights, pg_count);
|
|
// Align them with most similar previous PGs
|
|
const new_pgs = align_pgs(prev_int_pgs, int_pgs);
|
|
let differs = 0, osd_differs = 0;
|
|
for (let i = 0; i < pg_count; i++)
|
|
{
|
|
if (new_pgs[i].join('_') != prev_int_pgs[i].join('_'))
|
|
{
|
|
differs++;
|
|
}
|
|
}
|
|
if (ordered)
|
|
{
|
|
for (let i = 0; i < pg_count; i++)
|
|
{
|
|
for (let j = 0; j < pg_size; j++)
|
|
{
|
|
if (new_pgs[i][j] != prev_int_pgs[i][j])
|
|
{
|
|
osd_differs++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
for (let i = 0; i < pg_count; i++)
|
|
{
|
|
const old_map = prev_int_pgs[i].reduce((a, c) => { a[c] = (a[c]|0) + 1; return a; }, {});
|
|
for (let j = 0; j < pg_size; j++)
|
|
{
|
|
if ((0|old_map[new_pgs[i][j]]) > 0)
|
|
{
|
|
old_map[new_pgs[i][j]]--;
|
|
}
|
|
else
|
|
{
|
|
osd_differs++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return {
|
|
prev_pgs: prev_int_pgs,
|
|
score: lp_result.score,
|
|
weights,
|
|
int_pgs: new_pgs,
|
|
differs,
|
|
osd_differs,
|
|
pg_effsize,
|
|
space: pg_effsize * pg_list_space_efficiency(new_pgs, osd_weights, pg_minsize, parity_space),
|
|
total_space: total_weight,
|
|
};
|
|
}
|
|
|
|
function print_change_stats(retval, detailed)
|
|
{
|
|
const new_pgs = retval.int_pgs;
|
|
const prev_int_pgs = retval.prev_pgs;
|
|
if (prev_int_pgs)
|
|
{
|
|
if (detailed)
|
|
{
|
|
for (let i = 0; i < new_pgs.length; i++)
|
|
{
|
|
if (new_pgs[i].join('_') != prev_int_pgs[i].join('_'))
|
|
{
|
|
console.log("pg "+i+": "+prev_int_pgs[i].join(' ')+" -> "+new_pgs[i].join(' '));
|
|
}
|
|
}
|
|
}
|
|
console.log(
|
|
"Data movement: "+retval.differs+" pgs, "+
|
|
retval.osd_differs+" pg*osds = "+Math.round(retval.osd_differs / prev_int_pgs.length / 3 * 10000)/100+" %"
|
|
);
|
|
}
|
|
console.log(
|
|
"Total space (raw): "+Math.round(retval.space*100)/100+" TB, space efficiency: "+
|
|
Math.round(retval.space/(retval.total_space||1)*10000)/100+" %"
|
|
);
|
|
}
|
|
|
|
function align_pgs(prev_int_pgs, int_pgs)
|
|
{
|
|
const aligned_pgs = [];
|
|
put_aligned_pgs(aligned_pgs, int_pgs, prev_int_pgs, (pg) => [ pg.join(':') ]);
|
|
put_aligned_pgs(aligned_pgs, int_pgs, prev_int_pgs, (pg) => [ pg[0]+'::'+pg[2], ':'+pg[1]+':'+pg[2], pg[0]+':'+pg[1]+':' ]);
|
|
put_aligned_pgs(aligned_pgs, int_pgs, prev_int_pgs, (pg) => [ pg[0]+'::', ':'+pg[1]+':', '::'+pg[2] ]);
|
|
const free_slots = prev_int_pgs.map((pg, i) => !aligned_pgs[i] ? i : null).filter(i => i != null);
|
|
for (const pg of int_pgs)
|
|
{
|
|
if (!free_slots.length)
|
|
{
|
|
throw new Error("Can't place unaligned PG");
|
|
}
|
|
aligned_pgs[free_slots.shift()] = pg;
|
|
}
|
|
return aligned_pgs;
|
|
}
|
|
|
|
function put_aligned_pgs(aligned_pgs, int_pgs, prev_int_pgs, keygen)
|
|
{
|
|
let prev_indexes = {};
|
|
for (let i = 0; i < prev_int_pgs.length; i++)
|
|
{
|
|
for (let k of keygen(prev_int_pgs[i]))
|
|
{
|
|
prev_indexes[k] = prev_indexes[k] || [];
|
|
prev_indexes[k].push(i);
|
|
}
|
|
}
|
|
PG: for (let i = int_pgs.length-1; i >= 0; i--)
|
|
{
|
|
let pg = int_pgs[i];
|
|
let keys = keygen(int_pgs[i]);
|
|
for (let k of keys)
|
|
{
|
|
while (prev_indexes[k] && prev_indexes[k].length)
|
|
{
|
|
let idx = prev_indexes[k].shift();
|
|
if (!aligned_pgs[idx])
|
|
{
|
|
aligned_pgs[idx] = pg;
|
|
int_pgs.splice(i, 1);
|
|
continue PG;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
function pg_weights_space_efficiency(weights, pg_count, osd_sizes)
|
|
{
|
|
const per_osd = {};
|
|
for (const pg_name in weights)
|
|
{
|
|
for (const osd of pg_name.substr(3).split(/_/))
|
|
{
|
|
per_osd[osd] = (per_osd[osd]||0) + weights[pg_name];
|
|
}
|
|
}
|
|
return pg_per_osd_space_efficiency(per_osd, pg_count, osd_sizes);
|
|
}
|
|
|
|
function pg_list_space_efficiency(pgs, osd_sizes, pg_minsize, parity_space)
|
|
{
|
|
const per_osd = {};
|
|
for (const pg of pgs)
|
|
{
|
|
for (let i = 0; i < pg.length; i++)
|
|
{
|
|
const osd = pg[i];
|
|
per_osd[osd] = (per_osd[osd]||0) + (i >= pg_minsize ? (parity_space||1) : 1);
|
|
}
|
|
}
|
|
return pg_per_osd_space_efficiency(per_osd, pgs.length, osd_sizes);
|
|
}
|
|
|
|
function pg_per_osd_space_efficiency(per_osd, pg_count, osd_sizes)
|
|
{
|
|
// each PG gets randomly selected in 1/N cases
|
|
// & there are x PGs per OSD
|
|
// => an OSD is selected in x/N cases
|
|
// => total space * x/N <= OSD size
|
|
// => total space <= OSD size * N/x
|
|
let space;
|
|
for (let osd in per_osd)
|
|
{
|
|
if (osd in osd_sizes)
|
|
{
|
|
const space_estimate = osd_sizes[osd] * pg_count / per_osd[osd];
|
|
if (space == null || space > space_estimate)
|
|
{
|
|
space = space_estimate;
|
|
}
|
|
}
|
|
}
|
|
return space == null ? 0 : space;
|
|
}
|
|
|
|
module.exports = {
|
|
NO_OSD,
|
|
|
|
optimize_initial,
|
|
optimize_change,
|
|
print_change_stats,
|
|
pg_weights_space_efficiency,
|
|
pg_list_space_efficiency,
|
|
pg_per_osd_space_efficiency,
|
|
|
|
lp_solve,
|
|
make_int_pgs,
|
|
align_pgs,
|
|
};
|