314 lines
11 KiB
JavaScript
314 lines
11 KiB
JavaScript
|
import assert from 'node:assert/strict';
|
||
|
|
import { describe, test } from 'node:test';
|
||
|
|
import { CondensedGraph } from '../../src/core/CondensedGraph.js';
|
||
|
|
|
||
|
|
const runPerf = process.env.RUN_PERF_TESTS === '1';
|
||
|
|
const perfTest = runPerf ? test : test.skip;
|
||
|
|
|
||
|
|
describe('CondensedGraph - Realistic Authorization Workloads', () => {
|
||
|
|
perfTest('Zanzibar-style authorization graph', () => {
|
||
|
|
// Simulate a real authorization graph with:
|
||
|
|
// - Users, documents, groups, folders
|
||
|
|
// - Multiple relation types
|
||
|
|
// - Hierarchical access patterns
|
||
|
|
|
||
|
|
const graph = new CondensedGraph();
|
||
|
|
const numUsers = 1000;
|
||
|
|
const numDocs = 5000;
|
||
|
|
const numGroups = 50;
|
||
|
|
const numFolders = 100;
|
||
|
|
|
||
|
|
// Add users to groups (many-to-many)
|
||
|
|
for (let i = 0; i < numUsers; i++) {
|
||
|
|
const numGroupsPerUser = 1 + Math.floor(Math.random() * 5);
|
||
|
|
for (let j = 0; j < numGroupsPerUser; j++) {
|
||
|
|
const groupNum = Math.floor(Math.random() * numGroups);
|
||
|
|
graph.addEdge(`user:${i}`, 'member', `group:${groupNum}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Add document ownership (one user per doc)
|
||
|
|
for (let i = 0; i < numDocs; i++) {
|
||
|
|
const ownerNum = Math.floor(Math.random() * numUsers);
|
||
|
|
graph.addEdge(`user:${ownerNum}`, 'owner', `doc:${i}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Add documents to folders
|
||
|
|
for (let i = 0; i < numDocs; i++) {
|
||
|
|
const folderNum = Math.floor(Math.random() * numFolders);
|
||
|
|
graph.addEdge(`doc:${i}`, 'parent', `folder:${folderNum}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Add folder ownership
|
||
|
|
for (let i = 0; i < numFolders; i++) {
|
||
|
|
const ownerNum = Math.floor(Math.random() * numUsers);
|
||
|
|
graph.addEdge(`user:${ownerNum}`, 'owner', `folder:${i}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Add group access to documents
|
||
|
|
for (let i = 0; i < numDocs; i++) {
|
||
|
|
const numGroupsWithAccess = Math.floor(Math.random() * 3);
|
||
|
|
for (let j = 0; j < numGroupsWithAccess; j++) {
|
||
|
|
const groupNum = Math.floor(Math.random() * numGroups);
|
||
|
|
const relations = ['viewer', 'editor', 'commenter'];
|
||
|
|
const rel = relations[Math.floor(Math.random() * relations.length)];
|
||
|
|
graph.addEdge(`group:${groupNum}`, rel, `doc:${i}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
graph.finalizePerfectHash();
|
||
|
|
graph.finalizeWaveletAdjacency({ dropAdjacencyList: true });
|
||
|
|
|
||
|
|
const stats = graph.getStats();
|
||
|
|
|
||
|
|
console.log('\nZanzibar-style graph:');
|
||
|
|
console.log(` Users: ${numUsers}, Docs: ${numDocs}, Groups: ${numGroups}, Folders: ${numFolders}`);
|
||
|
|
console.log(` Total nodes: ${stats.numNodes}`);
|
||
|
|
console.log(` Total edges: ${stats.numEdges}`);
|
||
|
|
console.log(` Avg degree: ${stats.avgDegree.toFixed(2)}`);
|
||
|
|
console.log(` Memory: ${(stats.memoryUsage.total / 1024 / 1024).toFixed(2)} MB`);
|
||
|
|
console.log(` Bytes/edge: ${stats.bytesPerEdge.toFixed(2)}`);
|
||
|
|
|
||
|
|
// Authorization checks: user -> doc
|
||
|
|
console.log('\nAuthorization checks (user -> doc):');
|
||
|
|
|
||
|
|
const checks = [
|
||
|
|
{ user: 'user:0', doc: 'doc:0' },
|
||
|
|
{ user: 'user:100', doc: 'doc:500' },
|
||
|
|
{ user: 'user:500', doc: 'doc:1000' }
|
||
|
|
];
|
||
|
|
|
||
|
|
checks.forEach(check => {
|
||
|
|
const iterations = 100000;
|
||
|
|
|
||
|
|
// Direct ownership check
|
||
|
|
const directStart = performance.now();
|
||
|
|
for (let i = 0; i < iterations; i++) {
|
||
|
|
graph.findEdge(check.user, 'owner', check.doc);
|
||
|
|
}
|
||
|
|
const directTime = (performance.now() - directStart) / iterations * 1000;
|
||
|
|
|
||
|
|
// Has edge check
|
||
|
|
const hasStart = performance.now();
|
||
|
|
for (let i = 0; i < iterations; i++) {
|
||
|
|
graph.hasEdge(check.user, 'owner', check.doc);
|
||
|
|
}
|
||
|
|
const hasTime = (performance.now() - hasStart) / iterations * 1000;
|
||
|
|
|
||
|
|
console.log(` ${check.user} -> ${check.doc}:`);
|
||
|
|
console.log(` findEdge: ${directTime.toFixed(3)} µs`);
|
||
|
|
console.log(` hasEdge: ${hasTime.toFixed(3)} µs`);
|
||
|
|
});
|
||
|
|
|
||
|
|
// Group membership traversal simulation
|
||
|
|
console.log('\nGroup membership traversal:');
|
||
|
|
const userNum = 50;
|
||
|
|
const groups = graph.getOutEdgesByRel(`user:${userNum}`, 'member');
|
||
|
|
console.log(` User ${userNum} belongs to ${groups.length} groups`);
|
||
|
|
|
||
|
|
let totalDocsThroughGroups = 0;
|
||
|
|
let totalTime = 0;
|
||
|
|
const traversalIterations = 10000;
|
||
|
|
|
||
|
|
for (let i = 0; i < traversalIterations; i++) {
|
||
|
|
const start = performance.now();
|
||
|
|
let docCount = 0;
|
||
|
|
|
||
|
|
// Simulate: get user's groups, then get docs accessible by those groups
|
||
|
|
const userGroups = graph.getOutEdgesByRel(`user:${userNum}`, 'member');
|
||
|
|
for (const groupEdgeIdx of userGroups) {
|
||
|
|
const groupEdge = graph.getEdge(groupEdgeIdx);
|
||
|
|
const groupDocsViewer = graph.getOutEdgesByRel(groupEdge.dst, 'viewer');
|
||
|
|
const groupDocsEditor = graph.getOutEdgesByRel(groupEdge.dst, 'editor');
|
||
|
|
const groupDocsCommenter = graph.getOutEdgesByRel(groupEdge.dst, 'commenter');
|
||
|
|
docCount += groupDocsViewer.length + groupDocsEditor.length + groupDocsCommenter.length;
|
||
|
|
}
|
||
|
|
|
||
|
|
totalTime += performance.now() - start;
|
||
|
|
totalDocsThroughGroups += docCount;
|
||
|
|
}
|
||
|
|
|
||
|
|
const avgTime = (totalTime / traversalIterations) * 1000;
|
||
|
|
const avgDocs = totalDocsThroughGroups / traversalIterations;
|
||
|
|
|
||
|
|
console.log(` Avg time: ${avgTime.toFixed(3)} µs`);
|
||
|
|
console.log(` Avg docs accessible: ${avgDocs.toFixed(1)}`);
|
||
|
|
|
||
|
|
// Batch operations performance
|
||
|
|
console.log('\nBatch operations:');
|
||
|
|
|
||
|
|
// Batch getOutEdges
|
||
|
|
const batchStart = performance.now();
|
||
|
|
for (let i = 0; i < 1000; i++) {
|
||
|
|
const edges = graph.getOutEdgesByRel(`user:${i % numUsers}`, 'member');
|
||
|
|
}
|
||
|
|
const batchTime = performance.now() - batchStart;
|
||
|
|
console.log(` 1000 getOutEdges: ${batchTime.toFixed(2)} ms`);
|
||
|
|
|
||
|
|
assert.ok(stats.memoryUsage.total < 100 * 1024 * 1024, 'Memory should be < 100MB');
|
||
|
|
});
|
||
|
|
|
||
|
|
perfTest('high-frequency authorization checks', () => {
|
||
|
|
const graph = new CondensedGraph();
|
||
|
|
|
||
|
|
// Build a realistic graph
|
||
|
|
for (let i = 0; i < 10000; i++) {
|
||
|
|
graph.addEdge(`user:${i % 100}`, ['owner', 'editor', 'viewer'][i % 3], `doc:${i % 1000}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
graph.finalizePerfectHash();
|
||
|
|
graph.finalizeWaveletAdjacency({ dropAdjacencyList: true });
|
||
|
|
|
||
|
|
const numChecks = 1000000;
|
||
|
|
const users = Array.from({ length: 100 }, (_, i) => `user:${i}`);
|
||
|
|
const docs = Array.from({ length: 1000 }, (_, i) => `doc:${i}`);
|
||
|
|
for (let i = 0; i < 10000; i++) {
|
||
|
|
const user = users[i % 100];
|
||
|
|
const doc = docs[i % 1000];
|
||
|
|
graph.findEdge(user, 'owner', doc);
|
||
|
|
graph.findEdge(user, 'editor', doc);
|
||
|
|
graph.findEdge(user, 'viewer', doc);
|
||
|
|
}
|
||
|
|
|
||
|
|
const start = performance.now();
|
||
|
|
let allowed = 0;
|
||
|
|
|
||
|
|
for (let i = 0; i < numChecks; i++) {
|
||
|
|
const user = users[i % 100];
|
||
|
|
const doc = docs[i % 1000];
|
||
|
|
const hasOwner = graph.findEdge(user, 'owner', doc);
|
||
|
|
const hasEditor = graph.findEdge(user, 'editor', doc);
|
||
|
|
const hasViewer = graph.findEdge(user, 'viewer', doc);
|
||
|
|
|
||
|
|
if (hasOwner !== null || hasEditor !== null || hasViewer !== null) {
|
||
|
|
allowed++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
const duration = performance.now() - start;
|
||
|
|
const avgTime = (duration / numChecks) * 1000;
|
||
|
|
const opsPerSec = numChecks / (duration / 1000);
|
||
|
|
|
||
|
|
console.log('\nHigh-frequency authorization checks (1M checks):');
|
||
|
|
console.log(` Total time: ${duration.toFixed(2)} ms`);
|
||
|
|
console.log(` Avg time/check: ${avgTime.toFixed(3)} µs`);
|
||
|
|
console.log(` Checks/sec: ${opsPerSec.toFixed(0)}`);
|
||
|
|
console.log(` Allowed: ${allowed} (${(allowed / numChecks * 100).toFixed(1)}%)`);
|
||
|
|
|
||
|
|
assert.ok(avgTime < 80, `Should be fast, got ${avgTime.toFixed(3)} µs`);
|
||
|
|
});
|
||
|
|
|
||
|
|
perfTest('reachability query simulation', () => {
|
||
|
|
// Simulate hierarchical access: user -> group -> subgroups -> docs
|
||
|
|
const graph = new CondensedGraph();
|
||
|
|
|
||
|
|
const numUsers = 100;
|
||
|
|
const numGroups = 50;
|
||
|
|
const numDocs = 1000;
|
||
|
|
|
||
|
|
// User -> group membership
|
||
|
|
for (let i = 0; i < numUsers; i++) {
|
||
|
|
for (let j = 0; j < 3; j++) {
|
||
|
|
const groupNum = (i + j) % numGroups;
|
||
|
|
graph.addEdge(`user:${i}`, 'member', `group:${groupNum}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Group hierarchy
|
||
|
|
for (let i = 0; i < numGroups; i++) {
|
||
|
|
if (i < numGroups - 1) {
|
||
|
|
graph.addEdge(`group:${i}`, 'parent', `group:${i + 1}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Group -> doc access
|
||
|
|
for (let i = 0; i < numGroups; i++) {
|
||
|
|
for (let j = 0; j < 20; j++) {
|
||
|
|
graph.addEdge(`group:${i}`, 'viewer', `doc:${(i * 20 + j) % numDocs}`);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
graph.finalizePerfectHash();
|
||
|
|
graph.finalizeWaveletAdjacency({ dropAdjacencyList: true });
|
||
|
|
|
||
|
|
const stats = graph.getStats();
|
||
|
|
console.log('\nReachability graph:');
|
||
|
|
console.log(` Nodes: ${stats.numNodes}, Edges: ${stats.numEdges}`);
|
||
|
|
console.log(` Memory: ${(stats.memoryUsage.total / 1024 / 1024).toFixed(2)} MB`);
|
||
|
|
|
||
|
|
// Simulate BFS-like queries
|
||
|
|
const queries = 10000;
|
||
|
|
const start = performance.now();
|
||
|
|
|
||
|
|
for (let i = 0; i < queries; i++) {
|
||
|
|
const user = `user:${i % numUsers}`;
|
||
|
|
|
||
|
|
// Get user's groups
|
||
|
|
const userGroups = graph.getOutEdgesByRel(user, 'member');
|
||
|
|
|
||
|
|
// For each group, get parent groups
|
||
|
|
let allGroups = new Set();
|
||
|
|
for (const edgeIdx of userGroups) {
|
||
|
|
const edge = graph.getEdge(edgeIdx);
|
||
|
|
allGroups.add(edge.dst);
|
||
|
|
|
||
|
|
// Check for parent groups
|
||
|
|
const parentEdge = graph.findEdge(edge.dst, 'parent');
|
||
|
|
if (parentEdge !== null) {
|
||
|
|
const parent = graph.getEdge(parentEdge);
|
||
|
|
allGroups.add(parent.dst);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Get docs accessible by all groups
|
||
|
|
let docCount = 0;
|
||
|
|
for (const group of allGroups) {
|
||
|
|
const docEdges = graph.getOutEdgesByRel(group, 'viewer');
|
||
|
|
docCount += docEdges.length;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
const duration = performance.now() - start;
|
||
|
|
const avgTime = (duration / queries) * 1000;
|
||
|
|
|
||
|
|
console.log(`\nReachability queries (${queries} queries):`);
|
||
|
|
console.log(` Total time: ${duration.toFixed(2)} ms`);
|
||
|
|
console.log(` Avg time/query: ${avgTime.toFixed(3)} µs`);
|
||
|
|
console.log(` Queries/sec: ${(queries / (duration / 1000)).toFixed(0)}`);
|
||
|
|
|
||
|
|
assert.ok(avgTime < 100, `Should be fast, got ${avgTime.toFixed(3)} µs`);
|
||
|
|
});
|
||
|
|
|
||
|
|
perfTest('memory scalability comparison', () => {
|
||
|
|
const sizes = [10000, 50000, 100000];
|
||
|
|
|
||
|
|
console.log('\nMemory scalability:');
|
||
|
|
console.log('Edges | Memory (MB) | Bytes/Edge | Capacity | Utilization');
|
||
|
|
console.log('-------|-------------|------------|----------|-------------');
|
||
|
|
|
||
|
|
sizes.forEach(size => {
|
||
|
|
const graph = new CondensedGraph();
|
||
|
|
|
||
|
|
for (let i = 0; i < size; i++) {
|
||
|
|
graph.addEdge(`user:${i % 100}`, ['owner', 'editor', 'viewer'][i % 3], `doc:${i % 1000}`);
|
||
|
|
}
|
||
|
|
|
||
|
|
graph.finalizePerfectHash();
|
||
|
|
graph.finalizeWaveletAdjacency({ dropAdjacencyList: true });
|
||
|
|
|
||
|
|
const stats = graph.getStats();
|
||
|
|
const memMB = stats.memoryUsage.total / 1024 / 1024;
|
||
|
|
|
||
|
|
console.log(
|
||
|
|
`${size.toString().padEnd(7)} | ` +
|
||
|
|
`${memMB.toFixed(2).padEnd(11)} | ` +
|
||
|
|
`${stats.bytesPerEdge.toFixed(2).padEnd(10)} | ` +
|
||
|
|
`${stats.capacity.toString().padEnd(8)} | ` +
|
||
|
|
`${(stats.utilization * 100).toFixed(1).padEnd(10)}%`
|
||
|
|
);
|
||
|
|
|
||
|
|
assert.ok(memMB < size / 100, `Memory should be reasonable for ${size} edges`);
|
||
|
|
});
|
||
|
|
});
|
||
|
|
});
|