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.
449 lines
17 KiB
JavaScript
449 lines
17 KiB
JavaScript
import { performance } from 'perf_hooks';
|
|
import { Arbiter } from '../src/index.js';
|
|
|
|
console.log('🔬 Batch Size Performance Analysis\n');
|
|
|
|
// Quick graph setup for testing
|
|
function setupTestGraph() {
|
|
const arbiter = new Arbiter({
|
|
enableInference: true,
|
|
useOptimizedInference: true,
|
|
fastConstructionMode: true,
|
|
inferenceParams: {
|
|
minCaseThreshold: 3,
|
|
minJaccard: 0.15,
|
|
maxSimilarCases: 100
|
|
}
|
|
});
|
|
|
|
// Create test data
|
|
const users = [];
|
|
const docs = [];
|
|
const groups = [];
|
|
|
|
// 1000 users, 5000 documents, 50 groups for realistic scale
|
|
for (let i = 0; i < 1000; i++) {
|
|
const userKey = `user:${i}`;
|
|
users.push(userKey);
|
|
arbiter.addNode(userKey, 'user', { id: i, department: `dept_${i % 10}` });
|
|
}
|
|
|
|
for (let i = 0; i < 5000; i++) {
|
|
const docKey = `doc:${i}`;
|
|
docs.push(docKey);
|
|
arbiter.addNode(docKey, 'document', { id: i, classification: `level_${i % 5}` });
|
|
}
|
|
|
|
for (let i = 0; i < 50; i++) {
|
|
const groupKey = `group:${i}`;
|
|
groups.push(groupKey);
|
|
arbiter.addNode(groupKey, 'group', { id: i, type: `type_${i % 5}` });
|
|
}
|
|
|
|
// Add direct relations (20% of users have direct access to 10% of docs)
|
|
for (let i = 0; i < users.length * 0.2; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
for (let j = 0; j < docs.length * 0.1; j++) {
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
if (Math.random() < 0.3) { // 30% chance of access
|
|
arbiter.addRelation(user, 'can_read', doc, { possibility: 1.0 });
|
|
}
|
|
}
|
|
}
|
|
|
|
// Add group memberships (each user in 2-3 groups)
|
|
for (const user of users) {
|
|
const numGroups = 2 + Math.floor(Math.random() * 2); // 2-3 groups
|
|
for (let i = 0; i < numGroups; i++) {
|
|
const group = groups[Math.floor(Math.random() * groups.length)];
|
|
arbiter.addRelation(user, 'member_of', group, { possibility: 1.0 });
|
|
}
|
|
}
|
|
|
|
// Add group permissions (groups can access documents)
|
|
for (const group of groups) {
|
|
for (let i = 0; i < docs.length * 0.05; i++) { // 5% of docs per group
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
if (Math.random() < 0.4) { // 40% chance
|
|
arbiter.addRelation(group, 'can_read', doc, { possibility: 1.0 });
|
|
if (Math.random() < 0.3) { // 30% chance for write
|
|
arbiter.addRelation(group, 'can_write', doc, { possibility: 1.0 });
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// Configure relation types
|
|
arbiter.setRelationConfig('can_read', {
|
|
union: [
|
|
{ type: 'direct' },
|
|
{
|
|
type: 'tuple_to_userset',
|
|
tuplesetRelation: 'can_read',
|
|
computedRelation: 'member_of'
|
|
}
|
|
]
|
|
});
|
|
|
|
arbiter.setRelationConfig('can_write', {
|
|
intersection: [
|
|
{
|
|
union: [
|
|
{ type: 'direct' },
|
|
{
|
|
type: 'tuple_to_userset',
|
|
tuplesetRelation: 'can_write',
|
|
computedRelation: 'member_of'
|
|
}
|
|
]
|
|
},
|
|
{
|
|
type: 'direct',
|
|
relation: 'is_active'
|
|
}
|
|
]
|
|
});
|
|
|
|
arbiter.setRelationConfig('member_of', { type: 'direct' });
|
|
arbiter.setRelationConfig('is_active', { type: 'direct' });
|
|
|
|
// Add some active user flags
|
|
for (let i = 0; i < users.length * 0.8; i++) { // 80% active
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
arbiter.addRelation(user, 'is_active', 'system:active', { possibility: 1.0 });
|
|
}
|
|
|
|
console.log(`📊 Test graph: ${users.length} users, ${docs.length} documents, ${groups.length} groups`);
|
|
return { arbiter, users, docs, groups };
|
|
}
|
|
|
|
// Benchmark individual queries
|
|
async function benchmarkIndividual(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_read', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
for (const query of queries) {
|
|
arbiter.check(query.userKey, query.relation, query.objectKey, { noInfer: true });
|
|
}
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'individual' };
|
|
}
|
|
|
|
// Benchmark batch queries
|
|
async function benchmarkBatch(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_read', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
arbiter.checkBatch(queries);
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'batch' };
|
|
}
|
|
|
|
// Benchmark user batch (1 user, N documents)
|
|
async function benchmarkUserBatch(arbiter, users, docs, numQueries) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const docKeys = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
docKeys.push(doc);
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
arbiter.checkUserBatch(user, 'can_read', docKeys);
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'userBatch' };
|
|
}
|
|
|
|
// Benchmark binary mode individual
|
|
async function benchmarkBinaryIndividual(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_read', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
for (const query of queries) {
|
|
arbiter.check(query.userKey, query.relation, query.objectKey, {
|
|
binary: true,
|
|
noInfer: true,
|
|
minAllowPossibility: 0.8,
|
|
maxDenyPossibility: 0.8
|
|
});
|
|
}
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'binary' };
|
|
}
|
|
|
|
// Benchmark with inference (individual queries)
|
|
async function benchmarkWithInference(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_read', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
for (const query of queries) {
|
|
arbiter.check(query.userKey, query.relation, query.objectKey); // Inference enabled
|
|
}
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'inference' };
|
|
}
|
|
|
|
// Benchmark complex write queries (intersection rules)
|
|
async function benchmarkComplexWrite(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_write', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
for (const query of queries) {
|
|
arbiter.check(query.userKey, query.relation, query.objectKey, { noInfer: true });
|
|
}
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'complexWrite' };
|
|
}
|
|
|
|
// Benchmark batch with inference
|
|
async function benchmarkBatchWithInference(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_read', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
// Note: Current batch processor doesn't support inference options per query
|
|
// This will use individual checks with inference for each query in the batch
|
|
const results = [];
|
|
for (const query of queries) {
|
|
results.push(arbiter.check(query.userKey, query.relation, query.objectKey));
|
|
}
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'batchInference' };
|
|
}
|
|
|
|
// Benchmark binary + batch combination
|
|
async function benchmarkBinaryBatch(arbiter, users, docs, numQueries) {
|
|
const queries = [];
|
|
for (let i = 0; i < numQueries; i++) {
|
|
const user = users[Math.floor(Math.random() * users.length)];
|
|
const doc = docs[Math.floor(Math.random() * docs.length)];
|
|
queries.push({ userKey: user, relation: 'can_read', objectKey: doc });
|
|
}
|
|
|
|
const start = performance.now();
|
|
|
|
// Simulate binary batch by doing individual binary checks
|
|
// (since batch processor doesn't support binary mode yet)
|
|
for (const query of queries) {
|
|
arbiter.check(query.userKey, query.relation, query.objectKey, {
|
|
binary: true,
|
|
noInfer: true,
|
|
minAllowPossibility: 0.8,
|
|
maxDenyPossibility: 0.8
|
|
});
|
|
}
|
|
|
|
const totalTime = performance.now() - start;
|
|
const qps = numQueries / (totalTime / 1000);
|
|
const avgLatency = totalTime / numQueries;
|
|
|
|
return { totalTime, qps, avgLatency, method: 'binaryBatch' };
|
|
}
|
|
|
|
// Main analysis
|
|
async function analyzeBatchSizes() {
|
|
const { arbiter, users, docs, groups } = setupTestGraph();
|
|
|
|
// Test different batch sizes
|
|
const batchSizes = [1, 5, 10, 25, 50, 100, 250, 500, 1000, 2000, 5000];
|
|
const results = [];
|
|
|
|
console.log('\n🧪 Testing batch sizes vs individual queries...\n');
|
|
console.log('Batch Size | Individual | Batch | UserBatch | Binary | Inference | ComplexWrite | BinaryBatch | Best Method');
|
|
console.log('-----------|------------|-------|-----------|--------|-----------|--------------|-------------|-------------');
|
|
|
|
for (const batchSize of batchSizes) {
|
|
// Run each test 3 times and take the best result
|
|
const individualResults = [];
|
|
const batchResults = [];
|
|
const userBatchResults = [];
|
|
const binaryResults = [];
|
|
const inferenceResults = [];
|
|
const complexWriteResults = [];
|
|
const binaryBatchResults = [];
|
|
|
|
for (let run = 0; run < 3; run++) {
|
|
individualResults.push(await benchmarkIndividual(arbiter, users, docs, batchSize));
|
|
batchResults.push(await benchmarkBatch(arbiter, users, docs, batchSize));
|
|
userBatchResults.push(await benchmarkUserBatch(arbiter, users, docs, batchSize));
|
|
binaryResults.push(await benchmarkBinaryIndividual(arbiter, users, docs, batchSize));
|
|
inferenceResults.push(await benchmarkWithInference(arbiter, users, docs, batchSize));
|
|
complexWriteResults.push(await benchmarkComplexWrite(arbiter, users, docs, batchSize));
|
|
binaryBatchResults.push(await benchmarkBinaryBatch(arbiter, users, docs, batchSize));
|
|
}
|
|
|
|
// Take the best QPS from each method
|
|
const individualQPS = Math.max(...individualResults.map(r => r.qps));
|
|
const batchQPS = Math.max(...batchResults.map(r => r.qps));
|
|
const userBatchQPS = Math.max(...userBatchResults.map(r => r.qps));
|
|
const binaryQPS = Math.max(...binaryResults.map(r => r.qps));
|
|
const inferenceQPS = Math.max(...inferenceResults.map(r => r.qps));
|
|
const complexWriteQPS = Math.max(...complexWriteResults.map(r => r.qps));
|
|
const binaryBatchQPS = Math.max(...binaryBatchResults.map(r => r.qps));
|
|
|
|
// Determine best method
|
|
const methods = [
|
|
{ name: 'Individual', qps: individualQPS },
|
|
{ name: 'Batch', qps: batchQPS },
|
|
{ name: 'UserBatch', qps: userBatchQPS },
|
|
{ name: 'Binary', qps: binaryQPS },
|
|
{ name: 'Inference', qps: inferenceQPS },
|
|
{ name: 'ComplexWrite', qps: complexWriteQPS },
|
|
{ name: 'BinaryBatch', qps: binaryBatchQPS }
|
|
];
|
|
|
|
const bestMethod = methods.reduce((best, current) =>
|
|
current.qps > best.qps ? current : best
|
|
);
|
|
|
|
console.log(`${batchSize.toString().padStart(10)} | ${Math.round(individualQPS).toString().padStart(10)} | ${Math.round(batchQPS).toString().padStart(5)} | ${Math.round(userBatchQPS).toString().padStart(9)} | ${Math.round(binaryQPS).toString().padStart(6)} | ${Math.round(inferenceQPS).toString().padStart(9)} | ${Math.round(complexWriteQPS).toString().padStart(12)} | ${Math.round(binaryBatchQPS).toString().padStart(11)} | ${bestMethod.name}`);
|
|
|
|
results.push({
|
|
batchSize,
|
|
individualQPS,
|
|
batchQPS,
|
|
userBatchQPS,
|
|
binaryQPS,
|
|
inferenceQPS,
|
|
complexWriteQPS,
|
|
binaryBatchQPS,
|
|
bestMethod: bestMethod.name,
|
|
bestQPS: bestMethod.qps
|
|
});
|
|
}
|
|
|
|
// Find crossover points
|
|
console.log('\n📊 Analysis Results:\n');
|
|
|
|
// Find where batch beats individual
|
|
const batchCrossover = results.find(r => r.batchQPS > r.individualQPS);
|
|
if (batchCrossover) {
|
|
console.log(`🎯 Batch beats Individual at size: ${batchCrossover.batchSize}`);
|
|
console.log(` Individual: ${Math.round(batchCrossover.individualQPS)} QPS`);
|
|
console.log(` Batch: ${Math.round(batchCrossover.batchQPS)} QPS`);
|
|
console.log(` Improvement: ${((batchCrossover.batchQPS / batchCrossover.individualQPS - 1) * 100).toFixed(1)}%\n`);
|
|
}
|
|
|
|
// Find where userBatch beats batch
|
|
const userBatchCrossover = results.find(r => r.userBatchQPS > r.batchQPS);
|
|
if (userBatchCrossover) {
|
|
console.log(`🎯 UserBatch beats Batch at size: ${userBatchCrossover.batchSize}`);
|
|
console.log(` Batch: ${Math.round(userBatchCrossover.batchQPS)} QPS`);
|
|
console.log(` UserBatch: ${Math.round(userBatchCrossover.userBatchQPS)} QPS`);
|
|
console.log(` Improvement: ${((userBatchCrossover.userBatchQPS / userBatchCrossover.batchQPS - 1) * 100).toFixed(1)}%\n`);
|
|
}
|
|
|
|
// Find where binary beats inference
|
|
const binaryVsInference = results.find(r => r.binaryQPS > r.inferenceQPS);
|
|
if (binaryVsInference) {
|
|
console.log(`🎯 Binary beats Inference at size: ${binaryVsInference.batchSize}`);
|
|
console.log(` Inference: ${Math.round(binaryVsInference.inferenceQPS)} QPS`);
|
|
console.log(` Binary: ${Math.round(binaryVsInference.binaryQPS)} QPS`);
|
|
console.log(` Improvement: ${((binaryVsInference.binaryQPS / binaryVsInference.inferenceQPS - 1) * 100).toFixed(1)}%\n`);
|
|
}
|
|
|
|
// Find optimal batch size
|
|
const optimalResult = results.reduce((best, current) =>
|
|
current.bestQPS > best.bestQPS ? current : best
|
|
);
|
|
|
|
console.log(`🏆 Optimal Configuration:`);
|
|
console.log(` Batch Size: ${optimalResult.batchSize}`);
|
|
console.log(` Method: ${optimalResult.bestMethod}`);
|
|
console.log(` QPS: ${Math.round(optimalResult.bestQPS)}`);
|
|
|
|
// Show efficiency gains
|
|
const baseline = results[0]; // Size 1 individual
|
|
console.log(`\n💪 Performance Gains vs Individual (size 1):`);
|
|
console.log(` Best Method: ${((optimalResult.bestQPS / baseline.individualQPS - 1) * 100).toFixed(1)}% faster`);
|
|
console.log(` Binary Mode: ${((optimalResult.binaryQPS / baseline.individualQPS - 1) * 100).toFixed(1)}% faster`);
|
|
console.log(` Inference: ${((optimalResult.inferenceQPS / baseline.individualQPS - 1) * 100).toFixed(1)}% faster`);
|
|
console.log(` Complex Write: ${((optimalResult.complexWriteQPS / baseline.individualQPS - 1) * 100).toFixed(1)}% faster`);
|
|
|
|
// Performance comparison at optimal size
|
|
console.log(`\n🔬 Performance Breakdown at Optimal Size (${optimalResult.batchSize}):`);
|
|
console.log(` UserBatch: ${Math.round(optimalResult.userBatchQPS).toLocaleString()} QPS`);
|
|
console.log(` Batch: ${Math.round(optimalResult.batchQPS).toLocaleString()} QPS`);
|
|
console.log(` Binary: ${Math.round(optimalResult.binaryQPS).toLocaleString()} QPS`);
|
|
console.log(` Individual: ${Math.round(optimalResult.individualQPS).toLocaleString()} QPS`);
|
|
console.log(` Inference: ${Math.round(optimalResult.inferenceQPS).toLocaleString()} QPS`);
|
|
console.log(` ComplexWrite: ${Math.round(optimalResult.complexWriteQPS).toLocaleString()} QPS`);
|
|
|
|
// Inference impact analysis
|
|
const inferenceImpact = results.map(r => ({
|
|
batchSize: r.batchSize,
|
|
slowdown: ((r.individualQPS - r.inferenceQPS) / r.individualQPS * 100).toFixed(1)
|
|
}));
|
|
|
|
console.log(`\n🧠 Inference Performance Impact:`);
|
|
console.log(` Average slowdown: ${(inferenceImpact.reduce((sum, r) => sum + parseFloat(r.slowdown), 0) / inferenceImpact.length).toFixed(1)}%`);
|
|
console.log(` Best inference QPS: ${Math.round(Math.max(...results.map(r => r.inferenceQPS))).toLocaleString()}`);
|
|
console.log(` Inference still viable for: ${results.filter(r => r.inferenceQPS > 10000).length}/${results.length} batch sizes tested`);
|
|
}
|
|
|
|
// Run the analysis
|
|
analyzeBatchSizes().catch(console.error);
|