John Dvorak
717ae1031e
Zanzibar-style authorization graph engine (direct/chain/TTU/defeasible/ binary modes, condensed snapshots, value relations) with 39 rigor test campaigns. Includes fixes for snapshot binary writer/reader format mismatch (snapshot-of-snapshot corruption), possibility write-boundary validation, empty-graph snapshot serialization, relation lookup cache direction collision, config-redefinition cache invalidation, binary threshold semantics, defeasible compiled routing, and comparator reason whitelisting.
254 lines
10 KiB
JavaScript
254 lines
10 KiB
JavaScript
import { performance } from 'perf_hooks';
|
|
import { Arbiter } from '../src/index.js';
|
|
|
|
class Benchmark {
|
|
constructor(name) {
|
|
this.name = name;
|
|
this.results = [];
|
|
this.labels = [];
|
|
}
|
|
async run(fn, iterations = 1000, label = '') {
|
|
for (let i = 0; i < 10; i++) await fn();
|
|
const times = [];
|
|
for (let i = 0; i < iterations; i++) {
|
|
const start = performance.now();
|
|
await fn();
|
|
const end = performance.now();
|
|
times.push(end - start);
|
|
}
|
|
const avg = times.reduce((a, b) => a + b, 0) / times.length;
|
|
const min = Math.min(...times);
|
|
const max = Math.max(...times);
|
|
const p95 = times.sort((a, b) => a - b)[Math.floor(times.length * 0.95)];
|
|
this.results.push({
|
|
avg: avg.toFixed(3),
|
|
min: min.toFixed(3),
|
|
max: max.toFixed(3),
|
|
p95: p95.toFixed(3)
|
|
});
|
|
this.labels.push(label);
|
|
return { avg, min, max, p95 };
|
|
}
|
|
report() {
|
|
console.log('Configuration | Avg (ms) | Min (ms) | Max (ms) | P95 (ms) | Speedup');
|
|
console.log('---------------------------------|----------|----------|----------|----------|--------');
|
|
const baselineTime = parseFloat(this.results[0].avg);
|
|
this.results.forEach((result, i) => {
|
|
const label = this.labels[i] || `Test ${i + 1}`;
|
|
const speedup = i === 0 ? '1.00x' : `${(baselineTime / parseFloat(result.avg)).toFixed(2)}x`;
|
|
console.log(`${label.padEnd(32)} | ${result.avg.padStart(8)} | ${result.min.padStart(8)} | ${result.max.padStart(8)} | ${result.p95.padStart(8)} | ${speedup.padStart(6)}`);
|
|
});
|
|
}
|
|
}
|
|
|
|
function setupGraph(scale = 'medium') {
|
|
const scales = {
|
|
medium: { users: 2000, resources: 1000 },
|
|
xlarge: { users: 20000, resources: 5000 }
|
|
};
|
|
const config = scales[scale];
|
|
const arbiter = new Arbiter({ fastConstructionMode: true });
|
|
const users = [], resources = [];
|
|
for (let i = 0; i < config.users; i++) {
|
|
const userKey = `user:user${i}`;
|
|
arbiter.addNode(userKey, 'user');
|
|
// Assign a random balance between 100 and 10000
|
|
arbiter.addRelation(userKey, 'has_balance', 'balance', { value: Math.floor(Math.random() * 9900) + 100 });
|
|
users.push(userKey);
|
|
}
|
|
for (let i = 0; i < config.resources; i++) {
|
|
const resKey = `resource:res${i}`;
|
|
arbiter.addNode(resKey, 'resource');
|
|
// Assign a random price between 50 and 5000
|
|
arbiter.addRelation(resKey, 'has_price', 'price', { value: Math.floor(Math.random() * 4950) + 50 });
|
|
resources.push(resKey);
|
|
}
|
|
// Direct access for a subset
|
|
for (let i = 0; i < Math.floor(config.users * 0.1); i++) {
|
|
const user = users[i];
|
|
const res = resources[i % resources.length];
|
|
arbiter.addRelation(user, 'can_access', res);
|
|
}
|
|
// ChainRule: user->can_access->resource
|
|
arbiter.setRelationConfig('can_access', { type: 'direct' });
|
|
arbiter.setRelationConfig('chain_access', {
|
|
type: 'chain',
|
|
steps: [ { relation: 'can_access', direction: 'out' } ]
|
|
});
|
|
// RelationalComparatorRule: user.balance >= resource.price
|
|
arbiter.setRelationConfig('balance_check', {
|
|
type: 'relational_comparator',
|
|
leftOperand: {
|
|
rule: { type: 'direct', relation: 'has_balance' },
|
|
extractValue: true,
|
|
valueRelation: 'has_balance',
|
|
aggregator: 'max'
|
|
},
|
|
rightOperand: {
|
|
rule: { type: 'direct', relation: 'has_price' },
|
|
extractValue: true,
|
|
valueRelation: 'has_price',
|
|
aggregator: 'max'
|
|
},
|
|
comparator: '>=',
|
|
fallbackBehavior: 'deny'
|
|
});
|
|
return { arbiter, users, resources };
|
|
}
|
|
|
|
async function runRelationalComparatorBenchmarks() {
|
|
for (const scale of ['medium', 'xlarge']) {
|
|
console.log(`\n🔬 RelationalComparatorRule Benchmark (${scale.toUpperCase()})`);
|
|
const { arbiter, users, resources } = setupGraph(scale);
|
|
const benchmark = new Benchmark(`RelationalComparatorRule (${scale})`);
|
|
// Direct access baseline
|
|
await benchmark.run(() => {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const res = resources[Math.floor(Math.random() * resources.length)];
|
|
arbiter.check(user, 'can_access', res);
|
|
}, scale === 'medium' ? 500 : 100, 'Direct Access (baseline)');
|
|
// ChainRule existence
|
|
await benchmark.run(() => {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const res = resources[Math.floor(Math.random() * resources.length)];
|
|
arbiter.check(user, 'chain_access', res);
|
|
}, scale === 'medium' ? 500 : 100, 'ChainRule Existence');
|
|
// RelationalComparatorRule (value-based)
|
|
await benchmark.run(() => {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const res = resources[Math.floor(Math.random() * resources.length)];
|
|
arbiter.check(user, 'balance_check', res);
|
|
}, scale === 'medium' ? 500 : 100, 'RelationalComparatorRule (balance >= price)');
|
|
// --- Complex, realistic scenario: sum of all balances user can debit vs. min plan/feature price ---
|
|
// Setup: users, accounts, features, plans, prices, debit rights
|
|
const accounts = [], plans = [], features = [];
|
|
for (let i = 0; i < (scale === 'medium' ? 1000 : 5000); i++) {
|
|
const accKey = `account:acc${i}`;
|
|
accounts.push(accKey);
|
|
arbiter.addNode(accKey, 'account');
|
|
// Each account has a balance (with timestamp for decay)
|
|
arbiter.addRelation(accKey, 'has_balance', 'unit:usd', {
|
|
value: Math.floor(Math.random() * 9900) + 100,
|
|
updated_last_at: Date.now() - Math.floor(Math.random() * 48 * 60 * 60 * 1000) // up to 48h old
|
|
});
|
|
}
|
|
for (let i = 0; i < (scale === 'medium' ? 100 : 500); i++) {
|
|
const planKey = `plan:plan${i}`;
|
|
plans.push(planKey);
|
|
arbiter.addNode(planKey, 'plan');
|
|
arbiter.addRelation(planKey, 'has_price', 'unit:usd', { value: Math.floor(Math.random() * 4950) + 50 });
|
|
}
|
|
for (let i = 0; i < (scale === 'medium' ? 500 : 2000); i++) {
|
|
const featKey = `feature:feat${i}`;
|
|
features.push(featKey);
|
|
arbiter.addNode(featKey, 'feature');
|
|
// Each feature has a price
|
|
arbiter.addRelation(featKey, 'has_price', 'unit:usd', { value: Math.floor(Math.random() * 4950) + 50 });
|
|
// Some features belong to a plan
|
|
if (Math.random() < 0.5) {
|
|
const plan = plans[Math.floor(Math.random() * plans.length)];
|
|
arbiter.addRelation(featKey, 'belongs_to_plan', plan);
|
|
}
|
|
}
|
|
// Each user can debit a random subset of accounts
|
|
for (const user of users) {
|
|
for (let j = 0; j < (scale === 'medium' ? 3 : 5); j++) {
|
|
const acc = accounts[Math.floor(Math.random() * accounts.length)];
|
|
arbiter.addRelation(user, 'can_debit', acc);
|
|
}
|
|
}
|
|
arbiter.setRelationConfig('can_debit', { type: 'direct' });
|
|
arbiter.setRelationConfig('belongs_to_plan', { type: 'direct' });
|
|
arbiter.setRelationConfig('has_balance', { type: 'direct' });
|
|
arbiter.setRelationConfig('has_price', { type: 'direct' });
|
|
// Simplified RelationalComparatorRule: user balance vs feature price
|
|
arbiter.setRelationConfig('can_afford_feature', {
|
|
type: 'relational_comparator',
|
|
leftOperand: {
|
|
rule: { type: 'direct', relation: 'has_balance' },
|
|
extractValue: true,
|
|
valueRelation: 'has_balance',
|
|
aggregator: 'max'
|
|
},
|
|
rightOperand: {
|
|
rule: { type: 'direct', relation: 'has_price' },
|
|
extractValue: true,
|
|
valueRelation: 'has_price',
|
|
aggregator: 'max'
|
|
},
|
|
comparator: '>=',
|
|
fallbackBehavior: 'deny'
|
|
});
|
|
// Benchmark: can user afford feature (complex, multi-hop, aggregated, decayed)
|
|
await benchmark.run(() => {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const feature = features[Math.floor(Math.random() * features.length)];
|
|
arbiter.check(user, 'can_afford_feature', feature);
|
|
}, scale === 'medium' ? 200 : 30, 'Complex: can_debit sum >= min(plan/feature price)');
|
|
// Optionally: Nested logical operator (e.g., require both can afford AND recent 2FA)
|
|
// For brevity, just add a dummy 2FA relation and a logical AND
|
|
for (const user of users) {
|
|
arbiter.addRelation(user, 'last_2fa', '2fa:recent', { value: Date.now() - Math.floor(Math.random() * 60 * 60 * 1000) });
|
|
}
|
|
arbiter.addNode('2fa:recent', '2fa');
|
|
arbiter.setRelationConfig('last_2fa', { type: 'direct' });
|
|
arbiter.setRelationConfig('recent_2fa_check', {
|
|
type: 'relational_comparator',
|
|
leftOperand: {
|
|
rule: { type: 'direct', relation: 'last_2fa' },
|
|
extractValue: true
|
|
},
|
|
rightOperand: {
|
|
rule: { type: 'computed', value: Date.now() - 10 * 60 * 1000 }, // 10 minutes ago
|
|
extractValue: true
|
|
},
|
|
comparator: '>=', // last_2fa >= threshold (i.e., more recent)
|
|
fallbackBehavior: 'deny'
|
|
});
|
|
arbiter.setRelationConfig('can_afford_and_recent_2fa', {
|
|
type: 'intersection',
|
|
rules: [
|
|
{ type: 'relational_comparator',
|
|
leftOperand: {
|
|
rule: { type: 'direct', relation: 'has_balance' },
|
|
extractValue: true,
|
|
valueRelation: 'has_balance',
|
|
aggregator: 'max'
|
|
},
|
|
rightOperand: {
|
|
rule: { type: 'direct', relation: 'has_price' },
|
|
extractValue: true,
|
|
valueRelation: 'has_price',
|
|
aggregator: 'max'
|
|
},
|
|
comparator: '>=',
|
|
fallbackBehavior: 'deny'
|
|
},
|
|
{ type: 'relational_comparator',
|
|
leftOperand: {
|
|
rule: { type: 'direct', relation: 'last_2fa' },
|
|
extractValue: true
|
|
},
|
|
rightOperand: {
|
|
rule: { type: 'computed', value: Date.now() - 10 * 60 * 1000 },
|
|
extractValue: true
|
|
},
|
|
comparator: '>=',
|
|
fallbackBehavior: 'deny'
|
|
}
|
|
]
|
|
});
|
|
await benchmark.run(() => {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const feature = features[Math.floor(Math.random() * features.length)];
|
|
arbiter.check(user, 'can_afford_and_recent_2fa', feature);
|
|
}, scale === 'medium' ? 200 : 30, 'Complex: can_afford AND recent_2FA');
|
|
benchmark.report();
|
|
}
|
|
}
|
|
|
|
if (import.meta.url === `file://${process.argv[1]}`) {
|
|
runRelationalComparatorBenchmarks();
|
|
}
|
|
|
|
export { runRelationalComparatorBenchmarks };
|