1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

// Connection Graph: Undirected, unweighted
interface ConnectionGraph {
  nodes: Map<string, MemberNode>;
  edges: Map<string, ConnectionEdge>;  // Key: canonical edge ID
  
  // Core operations
  addConnection(member1: string, member2: string): void;
  removeConnection(member1: string, member2: string): void;
  areConnected(member1: string, member2: string): boolean;
  getConnections(member: string): string[];
  getConnectionCount(member: string): number;
}
 
// Follow Graph: Directed, for content/influence
interface FollowGraph {
  // Adjacency lists for both directions
  following: Map<string, Set<string>>;  // Who does this user follow?
  followers: Map<string, Set<string>>;  // Who follows this user?
  
  follow(follower: string, followed: string): void;
  unfollow(follower: string, followed: string): void;
  getFollowing(member: string): string[];
  getFollowers(member: string): string[];
  getFollowerCount(member: string): number;  // Critical for influencers
}
 
// Interaction Graph: Directed, weighted by recency and frequency
interface InteractionGraph {
  edges: Map<string, InteractionEdge>;
  
  recordInteraction(from: string, to: string, type: InteractionType): void;
  getInteractionScore(from: string, to: string): number;
  getTopInteractions(member: string, limit: number): InteractionEdge[];
}
 
interface InteractionEdge {
  source: string;
  target: string;
  weight: number;           // Computed score
  lastInteraction: Date;
  interactionCounts: {
    profileViews: number;
    messages: number;
    contentEngagements: number;
    mentions: number;
  };
}
 
type InteractionType = 'profile_view' | 'message' | 'like' | 
                       'comment' | 'share' | 'mention';
 
// Professional Context: Multi-relational with temporal attributes
interface ProfessionalContextGraph {
  // Members connected through shared contexts
  colleagueEdges: TemporalEdge[];      // Worked at same company
  classmateEdges: TemporalEdge[];      // Attended same school
  teammateEdges: TemporalEdge[];       // Same team at same company
  
  getSharedCompanies(member1: string, member2: string): Company[];
  getSharedSchools(member1: string, member2: string): School[];
  getOverlapPeriod(member1: string, member2: string, company: string): DateRange;
}
 
interface TemporalEdge {
  source: string;
  target: string;
  context: string;         // Company or school ID
  startDate: Date;
  endDate: Date | null;   // null = ongoing
  overlapDays: number;    // Pre-computed overlap duration
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

-- Core connections table
-- Canonical ordering: member_id_1 < member_id_2 to prevent duplicates
CREATE TABLE connections (
    id BIGINT PRIMARY KEY,
    member_id_1 BIGINT NOT NULL,
    member_id_2 BIGINT NOT NULL,
    connected_at TIMESTAMP NOT NULL,
    connection_source VARCHAR(50),
    CONSTRAINT uq_connection UNIQUE (member_id_1, member_id_2),
    CONSTRAINT chk_ordering CHECK (member_id_1 < member_id_2),
    INDEX idx_member1 (member_id_1),
    INDEX idx_member2 (member_id_2),
    INDEX idx_connected_at (connected_at)
);
 
-- Denormalized adjacency list for fast reads
-- One row per (member, connection) pair - bidirectional storage
CREATE TABLE member_connections (
    member_id BIGINT NOT NULL,
    connection_id BIGINT NOT NULL,
    connected_at TIMESTAMP NOT NULL,
    connection_source VARCHAR(50),
    -- Denormalized connection metadata for display
    connection_name VARCHAR(200),
    connection_headline VARCHAR(500),
    connection_photo_url VARCHAR(500),
    PRIMARY KEY (member_id, connection_id),
    INDEX idx_member_recent (member_id, connected_at DESC)
);
 
-- Query: Get my connections (fast - single partition read)
SELECT connection_id, connection_name, connection_headline
FROM member_connections
WHERE member_id = ?
ORDER BY connected_at DESC
LIMIT 20;
 
-- Query: Check if connected (fast - primary key lookup)
SELECT 1 FROM connections 
WHERE member_id_1 = LEAST(?, ?) 
  AND member_id_2 = GREATEST(?, ?);
 
-- Query: Mutual connections (expensive - requires JOIN)
SELECT mc2.connection_id
FROM member_connections mc1
JOIN member_connections mc2 ON mc1.connection_id = mc2.member_id
WHERE mc1.member_id = ?           -- My connections
  AND mc2.connection_id = ?       -- Who are also connected to target
  AND mc1.connection_id != ?;     -- Exclude target themselves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// Create connection relationship
MATCH (m1:Member {id: $memberId1}), (m2:Member {id: $memberId2})
CREATE (m1)-[c:CONNECTED_TO {
  connectedAt: datetime(),
  source: $source
}]->(m2)
RETURN c
 
// Get all connections for a member
MATCH (m:Member {id: $memberId})-[:CONNECTED_TO]-(connection:Member)
RETURN connection.id, connection.name, connection.headline
ORDER BY connection.name
LIMIT 20
 
// Get mutual connections (elegant in graph DB)
MATCH (me:Member {id: $myId})-[:CONNECTED_TO]-(mutual:Member)-[:CONNECTED_TO]-(target:Member {id: $targetId})
WHERE mutual.id <> $targetId AND mutual.id <> $myId
RETURN mutual.id, mutual.name, mutual.headline
LIMIT 20
 
// Find shortest path between two members
MATCH path = shortestPath(
  (start:Member {id: $startId})-[:CONNECTED_TO*..4]-(end:Member {id: $endId})
)
RETURN [n IN nodes(path) | n.id] AS pathIds,
       length(path) AS degrees
 
// 2nd degree connections (friends of friends)
MATCH (me:Member {id: $myId})-[:CONNECTED_TO]-(:Member)-[:CONNECTED_TO]-(fof:Member)
WHERE NOT (me)-[:CONNECTED_TO]-(fof) AND fof.id <> $myId
WITH fof, count(*) AS mutualCount
RETURN fof.id, fof.name, mutualCount
ORDER BY mutualCount DESC
LIMIT 20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

// Redis-based adjacency list storage
class RedisGraphStore {
  private redis: RedisClient;
 
  // Key patterns
  private connectionsKey(memberId: string): string {
    return `member:${memberId}:connections`;
  }
 
  private connectionDataKey(memberId: string, connectionId: string): string {
    return `member:${memberId}:connection:${connectionId}`;
  }
 
  // Add connection (bidirectional)
  async addConnection(member1: string, member2: string): Promise<void> {
    const timestamp = Date.now();
    
    // Use pipeline for atomicity
    const pipeline = this.redis.pipeline();
    
    // Add to both members' sorted sets (score = timestamp for ordering)
    pipeline.zadd(this.connectionsKey(member1), timestamp, member2);
    pipeline.zadd(this.connectionsKey(member2), timestamp, member1);
    
    // Increment connection count
    pipeline.hincrby(`member:${member1}`, 'connectionCount', 1);
    pipeline.hincrby(`member:${member2}`, 'connectionCount', 1);
    
    await pipeline.exec();
  }
 
  // Get connections with pagination
  async getConnections(
    memberId: string,
    offset: number = 0,
    limit: number = 20
  ): Promise<{ connectionIds: string[]; total: number }> {
    const key = this.connectionsKey(memberId);
    
    const [connectionIds, total] = await Promise.all([
      // Get page of connections (most recent first)
      this.redis.zrevrange(key, offset, offset + limit - 1),
      // Get total count
      this.redis.zcard(key),
    ]);
    
    return { connectionIds, total };
  }
 
  // Check if two members are connected
  async areConnected(member1: string, member2: string): Promise<boolean> {
    // Check if member2 is in member1's connection set
    const score = await this.redis.zscore(
      this.connectionsKey(member1), 
      member2
    );
    return score !== null;
  }
 
  // Get mutual connections (requires two lookups + intersection)
  async getMutualConnections(
    member1: string,
    member2: string,
    limit: number = 20
  ): Promise<string[]> {
    const tempKey = `temp:mutual:${member1}:${member2}:${Date.now()}`;
    
    try {
      // Compute intersection and store temporarily
      await this.redis.zinterstore(
        tempKey,
        2,
        this.connectionsKey(member1),
        this.connectionsKey(member2)
      );
      
      // Get the intersected members
      const mutuals = await this.redis.zrevrange(tempKey, 0, limit - 1);
      return mutuals;
    } finally {
      // Clean up temp key
      await this.redis.del(tempKey);
    }
  }
 
  // Get connection count efficiently
  async getConnectionCount(memberId: string): Promise<number> {
    return this.redis.zcard(this.connectionsKey(memberId));
  }
}
 
// For supernodes, we need sharded storage
class ShardedAdjacencyStore {
  private shardCount = 100;
 
  private getShardKey(memberId: string, shardIndex: number): string {
    return `member:${memberId}:connections:shard:${shardIndex}`;
  }
 
  private getShardIndex(connectionId: string): number {
    // Consistent hash to determine shard
    return hashCode(connectionId) % this.shardCount;
  }
 
  async addConnection(member1: string, member2: string): Promise<void> {
    const shard1 = this.getShardIndex(member2);
    const shard2 = this.getShardIndex(member1);
    
    await Promise.all([
      this.redis.sadd(this.getShardKey(member1, shard1), member2),
      this.redis.sadd(this.getShardKey(member2, shard2), member1),
    ]);
  }
 
  async getConnectionCount(memberId: string): Promise<number> {
    // Sum across all shards
    const counts = await Promise.all(
      Array.from({ length: this.shardCount }, (_, i) =>
        this.redis.scard(this.getShardKey(memberId, i))
      )
    );
    return counts.reduce((sum, count) => sum + count, 0);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

class ConnectionQueryRouter {
  constructor(
    private mysql: MySQLPool,
    private redis: RedisCluster,
    private graphStore: GraphStore,
    private elasticsearch: ElasticsearchClient,
  ) {}
 
  // Route query to optimal storage
  async getConnections(
    memberId: string,
    params: GetConnectionsParams
  ): Promise<ConnectionList> {
    const { sortBy, filters, pagination } = params;
    
    // Simple case: recent connections without filters
    if (!filters && sortBy === 'recent' && pagination.offset < 100) {
      return this.getFromCache(memberId, pagination);
    }
    
    // Complex case: filtering requires search
    if (filters?.industry || filters?.company || filters?.skills) {
      return this.getFromSearch(memberId, params);
    }
    
    // Large offsets or specific sorts: go to MySQL
    return this.getFromDatabase(memberId, params);
  }
 
  async getMutualConnections(
    viewerId: string,
    targetId: string,
    limit: number = 20
  ): Promise<MemberSummary[]> {
    // Check cache for precomputed mutuals (common pair)
    const cached = await this.getCachedMutuals(viewerId, targetId);
    if (cached) return cached.slice(0, limit);
    
    // Use graph store for intersection computation
    return this.graphStore.getMutualConnections(viewerId, targetId, limit);
  }
 
  async getDegreesOfSeparation(
    startId: string,
    endId: string
  ): Promise<ConnectionPath | null> {
    // Always use graph store for path queries
    return this.graphStore.findShortestPath(startId, endId, {
      maxDegrees: 4,
      maxPaths: 5,
    });
  }
 
  async getSecondDegreeConnections(
    memberId: string,
    pagination: PaginationParams
  ): Promise<SecondDegreeResult> {
    // Graph store handles 2nd-degree efficiently
    return this.graphStore.getSecondDegree(memberId, {
      excludeConnected: true,  // Don't show 1st-degree
      sortBy: 'mutual_count',
      ...pagination,
    });
  }
 
  // Cache layer methods
  private async getFromCache(
    memberId: string,
    pagination: PaginationParams
  ): Promise<ConnectionList> {
    const key = `connections:${memberId}`;
    
    const connectionIds = await this.redis.zrevrange(
      key,
      pagination.offset,
      pagination.offset + pagination.limit - 1
    );
    
    if (connectionIds.length === 0) {
      // Cache miss - populate from database
      return this.populateCacheAndReturn(memberId, pagination);
    }
    
    // Fetch member details for connection IDs
    const members = await this.getMemberDetails(connectionIds);
    const total = await this.redis.zcard(key);
    
    return { connections: members, total };
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

// Standard BFS - works for small graphs
function bfsShortestPath(
  graph: Map<string, string[]>,
  start: string,
  end: string
): string[] | null {
  if (start === end) return [start];
  
  const visited = new Set<string>([start]);
  const queue: Array<{ node: string; path: string[] }> = [
    { node: start, path: [start] }
  ];
  
  while (queue.length > 0) {
    const { node, path } = queue.shift()!;
    
    for (const neighbor of graph.get(node) || []) {
      if (neighbor === end) {
        return [...path, neighbor];
      }
      
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push({ node: neighbor, path: [...path, neighbor] });
      }
    }
  }
  
  return null;
}
 
// Problems with naive BFS at scale:
// 1. Path array copying is O(path length) per node
// 2. Queue can grow to millions of entries
// 3. No early termination for unreachable nodes
 
// Optimized: Bidirectional BFS
// Search from both ends simultaneously - meets in the middle
// Time complexity: O(b^(d/2)) instead of O(b^d) where b=branching, d=depth
function bidirectionalBFS(
  graph: GraphStore,
  start: string,
  end: string,
  maxDegrees: number = 4
): ConnectionPath | null {
  if (start === end) return { path: [start], degrees: 0 };
  
  // Check if directly connected first
  if (graph.areConnected(start, end)) {
    return { path: [start, end], degrees: 1 };
  }
  
  // Forward search from start
  const forwardVisited = new Map<string, string>(); // node -> parent
  const forwardQueue: string[] = [start];
  forwardVisited.set(start, '');
  
  // Backward search from end
  const backwardVisited = new Map<string, string>(); // node -> child
  const backwardQueue: string[] = [end];
  backwardVisited.set(end, '');
  
  let degrees = 0;
  
  while (
    forwardQueue.length > 0 && 
    backwardQueue.length > 0 && 
    degrees < maxDegrees
  ) {
    degrees++;
    
    // Expand the smaller frontier first (optimization)
    if (forwardQueue.length <= backwardQueue.length) {
      const meeting = expandFrontier(
        graph, forwardQueue, forwardVisited, backwardVisited
      );
      if (meeting) {
        return reconstructPath(meeting, forwardVisited, backwardVisited);
      }
    } else {
      const meeting = expandFrontier(
        graph, backwardQueue, backwardVisited, forwardVisited
      );
      if (meeting) {
        return reconstructPath(meeting, forwardVisited, backwardVisited);
      }
    }
  }
  
  return null;
}
 
function expandFrontier(
  graph: GraphStore,
  queue: string[],
  myVisited: Map<string, string>,
  otherVisited: Map<string, string>
): string | null {
  const currentLevel = queue.length;
  
  for (let i = 0; i < currentLevel; i++) {
    const node = queue.shift()!;
    
    // Limit neighbors for supernodes
    const neighbors = graph.getConnections(node, { limit: 1000 });
    
    for (const neighbor of neighbors) {
      // Check if we've met the other search
      if (otherVisited.has(neighbor)) {
        myVisited.set(neighbor, node);
        return neighbor;
      }
      
      if (!myVisited.has(neighbor)) {
        myVisited.set(neighbor, node);
        queue.push(neighbor);
      }
    }
  }
  
  return null;
}
 
function reconstructPath(
  meeting: string,
  forwardVisited: Map<string, string>,
  backwardVisited: Map<string, string>
): ConnectionPath {
  // Build path from start to meeting point
  const forwardPath: string[] = [];
  let node = meeting;
  while (node) {
    forwardPath.unshift(node);
    node = forwardVisited.get(node)!;
  }
  
  // Build path from meeting point to end
  const backwardPath: string[] = [];
  node = backwardVisited.get(meeting)!;
  while (node) {
    backwardPath.push(node);
    node = backwardVisited.get(node)!;
  }
  
  const fullPath = [...forwardPath, ...backwardPath];
  return { 
    path: fullPath, 
    degrees: fullPath.length - 1 
  };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

// Approach 1: Set Intersection (in-memory)
// Best when both users have small connection sets
function getMutualsSetIntersection(
  connections1: Set<string>,
  connections2: Set<string>
): string[] {
  const smaller = connections1.size < connections2.size 
    ? connections1 : connections2;
  const larger = connections1.size >= connections2.size 
    ? connections1 : connections2;
  
  const mutuals: string[] = [];
  for (const id of smaller) {
    if (larger.has(id)) {
      mutuals.push(id);
    }
  }
  return mutuals;
}
// Time: O(min(|A|, |B|))
 
// Approach 2: Sorted List Merge
// Better when lists are already sorted and we can stream
function getMutualsSortedMerge(
  sorted1: string[],
  sorted2: string[]
): string[] {
  const mutuals: string[] = [];
  let i = 0, j = 0;
  
  while (i < sorted1.length && j < sorted2.length) {
    if (sorted1[i] === sorted2[j]) {
      mutuals.push(sorted1[i]);
      i++; j++;
    } else if (sorted1[i] < sorted2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return mutuals;
}
// Time: O(|A| + |B|)
 
// Approach 3: Redis ZINTERSTORE (server-side intersection)
async function getMutualsRedis(
  redis: RedisClient,
  member1: string,
  member2: string,
  limit: number = 20
): Promise<string[]> {
  const key1 = `connections:${member1}`;
  const key2 = `connections:${member2}`;
  const tempKey = `temp:mutuals:${member1}:${member2}:${Date.now()}`;
  
  try {
    // Intersect and store (with recency scores)
    await redis.zinterstore(tempKey, 2, key1, key2, 'AGGREGATE', 'MAX');
    
    // Get top by recency
    const mutuals = await redis.zrevrange(tempKey, 0, limit - 1);
    return mutuals;
  } finally {
    await redis.del(tempKey);
  }
}
 
// Approach 4: Bloom Filter Pre-check
// For supernodes, use Bloom filter to skip definite non-mutuals
class MutualConnectionFinder {
  private bloomFilters: Map<string, BloomFilter> = new Map();
 
  async getMutualsWithBloom(
    member1: string,
    member2: string,
    limit: number
  ): Promise<string[]> {
    const [connections1, bloom2] = await Promise.all([
      this.getConnections(member1),
      this.getOrCreateBloom(member2),
    ]);
    
    const candidates: string[] = [];
    
    // Use Bloom filter to quickly eliminate non-mutuals
    for (const conn of connections1) {
      if (bloom2.mightContain(conn)) {
        candidates.push(conn);
      }
    }
    
    // Verify candidates (Bloom has false positives)
    const verified = await this.verifyConnections(member2, candidates);
    
    return verified.slice(0, limit);
  }
 
  private async getOrCreateBloom(memberId: string): Promise<BloomFilter> {
    if (this.bloomFilters.has(memberId)) {
      return this.bloomFilters.get(memberId)!;
    }
    
    const connections = await this.getConnections(memberId);
    const bloom = new BloomFilter(connections.length * 10, 7);
    
    for (const conn of connections) {
      bloom.add(conn);
    }
    
    this.bloomFilters.set(memberId, bloom);
    return bloom;
  }
}
 
// Approach 5: Precomputed Mutual Counts
// For frequent pairs, precompute and cache mutual connection info
interface MutualCache {
  key: string;        // "smallerId:largerId"
  mutualIds: string[];
  mutualCount: number;
  computedAt: Date;
  ttl: number;
}
 
async function getMutualsWithCache(
  cache: CacheStore,
  graph: GraphStore,
  member1: string,
  member2: string
): Promise<string[]> {
  const cacheKey = [member1, member2].sort().join(':');
  
  const cached = await cache.get<MutualCache>(`mutuals:${cacheKey}`);
  if (cached && !isExpired(cached)) {
    return cached.mutualIds;
  }
  
  // Compute and cache
  const mutuals = await graph.computeMutuals(member1, member2);
  
  await cache.set(`mutuals:${cacheKey}`, {
    key: cacheKey,
    mutualIds: mutuals,
    mutualCount: mutuals.length,
    computedAt: new Date(),
    ttl: 3600, // 1 hour
  });
  
  return mutuals;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

// Hash-based partitioning with consistent hashing
class GraphPartitioner {
  private ring: ConsistentHashRing;
  private partitionCount: number;
  private nodeConnections: Map<string, PartitionConnection[]>;
 
  constructor(partitionCount: number) {
    this.partitionCount = partitionCount;
    this.ring = new ConsistentHashRing(partitionCount);
    this.nodeConnections = new Map();
  }
 
  // Determine which partition owns a member's data
  getPartition(memberId: string): number {
    return this.ring.getPartition(memberId);
  }
 
  // For 2-hop queries, we need to know affected partitions
  getPartitionsForSecondDegree(memberId: string): Set<number> {
    const myPartition = this.getPartition(memberId);
    const partitions = new Set<number>([myPartition]);
    
    // Would need to query my partition to get 1st-degree,
    // then fan out to their partitions
    // This is expensive - hence the need for replication/caching
    return partitions;
  }
 
  // Execute a query that may span partitions
  async executeTraversalQuery<T>(
    query: GraphQuery,
    startMemberId: string
  ): Promise<T> {
    const startPartition = this.getPartition(startMemberId);
    
    // First, get local data
    const localResult = await this.queryPartition<T>(
      startPartition, 
      query, 
      startMemberId
    );
    
    // Determine if we need cross-partition data
    if (query.depth > 1) {
      return this.executeFederatedQuery(query, localResult);
    }
    
    return localResult;
  }
 
  // Federated query across partitions
  private async executeFederatedQuery<T>(
    query: GraphQuery,
    initialResult: PartialResult
  ): Promise<T> {
    const affectedPartitions = this.getAffectedPartitions(
      initialResult.frontierMemberIds
    );
    
    // Parallel query to all affected partitions
    const partitionResults = await Promise.all(
      Array.from(affectedPartitions).map(partition =>
        this.queryPartition(partition, query.nextLevel(), 
                           initialResult.frontierMemberIds)
      )
    );
    
    // Merge results
    return this.mergeResults(initialResult, partitionResults);
  }
}
 
// Supernode-aware partitioning
// Supernodes are replicated across all partitions
class SupernodeAwarePartitioner extends GraphPartitioner {
  private supernodeThreshold = 10000;  // Connections count
  private supernodeReplicas: Map<string, SupernodeReplica> = new Map();
 
  async addConnection(member1: string, member2: string): Promise<void> {
    // Check if either is a supernode
    const [count1, count2] = await Promise.all([
      this.getConnectionCount(member1),
      this.getConnectionCount(member2),
    ]);
    
    if (count1 > this.supernodeThreshold) {
      await this.handleSupernodeConnection(member1, member2);
    } else if (count2 > this.supernodeThreshold) {
      await this.handleSupernodeConnection(member2, member1);
    } else {
      // Normal connection - store in both members' partitions
      await this.storeNormalConnection(member1, member2);
    }
  }
 
  private async handleSupernodeConnection(
    supernode: string,
    normal: string
  ): Promise<void> {
    // Store in supernode's central replicated store
    await this.supernodeStore.addConnection(supernode, normal);
    
    // Also store inverse in normal user's partition for their queries
    const partition = this.getPartition(normal);
    await this.partitions[partition].addSupernodeConnection(normal, supernode);
  }
 
  // Query optimization for supernodes
  async getConnections(memberId: string, limit: number): Promise<string[]> {
    const connectionCount = await this.getConnectionCount(memberId);
    
    if (connectionCount > this.supernodeThreshold) {
      // Use supernode-specific storage
      return this.supernodeStore.getConnections(memberId, limit);
    }
    
    // Normal path
    const partition = this.getPartition(memberId);
    return this.partitions[partition].getConnections(memberId, limit);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

class GraphCacheLayer {
  private redis: RedisCluster;
  private localCache: LRUCache<string, any>;  // L1 in-process cache
  
  // TTLs based on data volatility
  private TTL = {
    connectionCount: 300,      // 5 min - rarely queried for exact
    adjacencyList: 900,        // 15 min - moderately stable
    mutualConnections: 3600,   // 1 hour - changes slowly
    connectionState: 60,       // 1 min - needs freshness
    secondDegree: 7200,        // 2 hours - expensive to compute
  };
 
  // Multi-tier caching for adjacency lists
  async getConnections(memberId: string, limit: number): Promise<string[]> {
    const cacheKey = `adj:${memberId}`;
    
    // L1: In-process cache (microseconds)
    const l1Hit = this.localCache.get(cacheKey);
    if (l1Hit) return l1Hit.slice(0, limit);
    
    // L2: Redis (milliseconds)
    const l2Hit = await this.redis.zrevrange(cacheKey, 0, limit - 1);
    if (l2Hit.length > 0) {
      this.localCache.set(cacheKey, l2Hit);
      return l2Hit;
    }
    
    // L3: Database (tens of milliseconds)
    const connections = await this.loadFromDatabase(memberId);
    
    // Populate caches
    await this.populateCache(memberId, connections);
    
    return connections.slice(0, limit);
  }
 
  // Smart cache invalidation on connection change
  async onConnectionCreated(member1: string, member2: string): Promise<void> {
    // Invalidate adjacency lists
    await this.invalidateAdjacency(member1);
    await this.invalidateAdjacency(member2);
    
    // Invalidate connection counts
    await this.invalidateCount(member1);
    await this.invalidateCount(member2);
    
    // Invalidate mutual connection caches for all of member1's connections
    // This is expensive - we batch and async it
    this.queueMutualInvalidation(member1, member2);
    
    // Don't invalidate 2nd-degree caches - too expensive
    // They'll expire naturally via TTL
  }
 
  // Lazy 2nd-degree computation with caching
  async getSecondDegreeNetwork(memberId: string): Promise<SecondDegreeResult> {
    const cacheKey = `2nd:${memberId}`;
    
    const cached = await this.redis.get(cacheKey);
    if (cached) return JSON.parse(cached);
    
    // Check if computation is already in progress
    const lockKey = `lock:2nd:${memberId}`;
    const lockAcquired = await this.redis.set(lockKey, '1', 'NX', 'EX', 60);
    
    if (!lockAcquired) {
      // Another request is computing - wait and retry
      await sleep(100);
      return this.getSecondDegreeNetwork(memberId);
    }
    
    try {
      // Compute 2nd-degree network
      const result = await this.computeSecondDegree(memberId);
      
      // Cache the result
      await this.redis.setex(
        cacheKey, 
        this.TTL.secondDegree, 
        JSON.stringify(result)
      );
      
      return result;
    } finally {
      await this.redis.del(lockKey);
    }
  }
 
  // Connection state with negative caching
  async areConnected(member1: string, member2: string): Promise<boolean> {
    const pair = [member1, member2].sort().join(':');
    const cacheKey = `connected:${pair}`;
    
    const cached = await this.redis.get(cacheKey);
    if (cached !== null) {
      return cached === '1';
    }
    
    const connected = await this.checkDatabase(member1, member2);
    
    // Cache both positive and negative results
    // Negative cache prevents repeated DB lookups for non-connections
    await this.redis.setex(cacheKey, this.TTL.connectionState, connected ? '1' : '0');
    
    return connected;
  }
}
 
// Bloom filter for quick negative lookups
class ConnectionBloomFilter {
  private bloom: BloomFilter;
  private memberId: string;
  
  // False positive rate ~1%, no false negatives
  static async create(memberId: string, connections: string[]): Promise<ConnectionBloomFilter> {
    const filter = new ConnectionBloomFilter();
    filter.memberId = memberId;
    filter.bloom = new BloomFilter(connections.length * 10, 7);
    
    for (const conn of connections) {
      filter.bloom.add(conn);
    }
    
    return filter;
  }
 
  definitelyNotConnected(otherId: string): boolean {
    return !this.bloom.mightContain(otherId);
  }
}