UE21CS461A –Project Phase – 2

​

Project Progress Review #3

Project Title : Scalable Indexing Mechanisms for Modular,

Google Zanzibar based Systems

Project ID : 132

Project Guide : Dr. Vinodha K

Project Team : Varuni H K PES2UG21CS597

Sai Sudhir Sunku PES2UG21CS460

Sai Smaran Jawalkar PES2UG21CS459

Samarth Ramesh PES2UG21CS465

​

​

​

​

​

​

• Abstract and Scope of the Project
• Suggestions from Review – 2
• Implementation Details
• Project Demonstration
• Test Plan and Strategy - benchmarking
• Results and Discussion
• Project Report Draft
• Conclusion and Future Work
• References

​

​

Outline

“Faster Fully Dynamic Transitive Closure in Practice” �Hanauer et al. (2020)

• Static BFS and DFS perform poorly on larger graphs .

​

• Motivated by these findings, Hanauer et al. designed a family of algorithms for dynamic transitive closure and proved it to be better by orders of magnitude than static BFS/DFS in practice.

​

• We refer to this family of algos as the SV family of algorithms

​

• We have decided to use this algorithm for our Indexing engine

• Inefficient indexing in Zanzibar-like systems causes scalability challenges.
• Aim to develop and evaluate an indexing framework with:
1. Partial transitive closures
2. Consistent hashing
3. Distributed transitive closure indexes
• Current systems lack efficient indexing mechanisms, reducing query performance and scalability.
• Propose a novel approach to improve indexing efficiency and to rigorously assess the solution against industry benchmarks.
• Expect to enhance query efficiency and scalability in large-scale distributed systems like Zanzibar.

​

Abstract and Scope

Problem Statement

• Google Zanzibar is a relation-based access control system designed for the immense scale of Google’s operations. The Zanzibar paper proposed a graph-based approach towards authorization, an approach which at the time of publication was absolutely novel!
• Dynamic Transitive Closure based Indexing for Zanzibar like authorisation systems .

​

​

​

1. Check and ensure correctness in the write queue implementation
1. As a part of the write queue implementation, extensive testing has been done by comparing results given by our index against results from vanilla SpiceDB.
2. We also can deliver a bounded write latency for a given server loading pattern (and graph size Order of Magnitude)

Suggestions from Review - 2

• SVA rebuilds the index every ‘A’ requests.
• Index itself uses SV[1] algorithm proposed by Katherine et al.
• The SV Algorithm uses three key observations on the properties of partial transitive closures of a directed acyclic graph [2].
• As a part of an index build, R+ and R- Tree is calculated from a chosen vertex

Implementation Details - SVA(1)

Indexing Algorithm - SV Family

Support Vertices:

​

Support Vertices are designed to determine the reachability of a specific node in a large directed graph.

It focuses on optimizing the computation of transitive closure for a single node.

Utilizes precomputed reachability information (R+ and R- sets) to reduce the need for full graph traversal.

​

On Initialize() we choose a list of Support Vertices

Indexing Algorithm - R+

Support Vertices:

​

R+(A) = { B, D, E, F, C}

​

Indexing Algorithm : R -

R-(A) = {C, F, G}

​

​

Observations Driving SV(K)

O1: If a node s is in R-(v) and t is in R+(v), then s can reach t.

​

O2: If s is in R+(v) but t is not, s cannot reach t.

​

O3: If t is in R-(v) but s is not, s cannot reach t.

​

given SV(a) , find if there is a path from f to b �

f to b using O(1)

R+(A) = {A, B, D, E, F, C}: Nodes that A can reach.

R-(A) = {C, F, G}: Nodes that can reach A.

​

​

Let s = F (since F ∈ R-(A), F can reach A).

Let t = B (since B ∈ R+(A), A can reach B).

There is a path F → A → B; hence, F can reach B.

​

How it works

1. Initialize: Identify node v whose reachability we need to compute.

​

• Check Reachability:
• Apply R+ and R- to check if a direct path exists.
• Use Observations (O1, O2, O3) to quickly determine reachability without full traversal.
• Fallback: If the precomputed reachability information is insufficient, fall back to BFS for accurate path discovery.

​

• Onyx is a custom built wrapper for providing a gograph interface with an persistent backend.
• It is a threadsafe, MVCC Compliant graph library.
• It allows for multiple inserts and deletes at the same time.
• The library uses Badger as its backing store.

​

Implementation Details - Onyx

• The R+ and R- Trees are the most expensive part of an index rebuild
• These R+ and R- (in our case, they have been flattened to lists)

Implementation Details - SVA

• Fetch edge list via Onyx from the serialized data structure
• Use R+ and R- trees for optimized edge-list retrieval
• Handle for multiple reads in Serializable Isolation mode, to ensure consistency without transaction interference
• Validate against last index update, if query fails strict staleness guarantees, they fall back to SpiceDB’s resolver

Implementation Details - Read Path

• Transaction-Based Writes: Users write queues for concurrent atomic write operations with Onyx-based transactions
• Write Queue system: Alternates between active and inactive queues (blue-green) approach for managing and applying writes efficiently
• Index Recompute: Triggered based on read volume or elapsed time since last write, ensuring dynamic index updates
• Concurrency Control: Applies locks for queue swapping to prevent loss, during index recompute cycles

​

Implementation Details - Write Path

• To mitigate cost of index rebuilds, we batch writes (to the index) and recalculate the R+ and R- Trees concurrently to the load.
• This ensures that utmost 1 read request per write is affected by this.
• We have two queues, one active and another inactive.
• New writes are always appended to the active queue
• If there are unapplied writes that are older than 500ms, and no other writes are currently on going, then a rebuild is triggered.

Implementation Details - Write Queues

Implementation Details - Write Queue

• When a new rebuild happens, the active and the inactive queues are swapped.
• So the inactive (and empty) queue is now used for writes, and the active queue is drained into the index’s datastore
• Then the index is rebuilt (as described earlier)
• After a rebuild happens, the new R+ and R- trees get used.
• The old ones just get deallocated by the garbage collector

Implementation Details - Write Queue

The graph dataset problem

• We couldn't find auth graphs anywhere
• So we have no clue what a real time auth graph looks like

​

Data Collection

Objective: To generate a synthetic dataset representing an authorization request graph.

​

Approach: We utilized an Erdos-Renyi model (ERM) variant to create a graph with specific properties like long traversals and high latency.

​

Tools Used: Python, NetworkX library, NumPy

​

Data Collection

What is Erdos Renyi model?

​

• The ERM is a method for generating random graphs. It constructs a graph by connecting nodes randomly, with each possible edge included with a fixed probability.

​

Key Parameters:

• Number of Nodes (n): The total number of nodes in the graph.
• Edge Probability (p): The probability of any two nodes being connected by an edge.

Data Interpretation

Metrics Calculation:

We computed metrics like in-degree, out-degree, and graph density to validate the structure.

​

Network Structure:

We ensured that intermediate nodes have the desired properties to maintain the integrity of the graph.

​

Layers: 2120

Total Edges generated: 155,848,612

Total Nodes generated: 20,136,726

In-Degree Mean: 7.762, In-Degree Std: 7.04

Out-Degree Mean: 11.63, Out-Degree Std: 9.49

Density: 3.84 e-07

• As a part of testing, we have built the following tools:
• A load testing integration using Locust[1]
• A Ingestor that provides a chunked upload to spiceDB for a pre-warmed index system
• A tool for validating correctness against spiceDB in fully consistent mode
• As a part of the main loadtest, we have configured both vanilla spiceDB and our version of spiceDB to have similar settings and performance tuning applied.
• Our tests have been executed on a bare metal linux machine running Fedora Server 37 and has 4 CPUs and 12GB of Ram

Test Plan and Strategy

Architecture and Infra

Case 1: Pure Read Workload

Vanilla SpiceDB

Modified SpiceDB

Vanilla SpiceDB

Modified SpiceDB

Case 2: Mixed Workload

( 1% Writes , 99% Read )

Vanilla SpiceDB

Modified SpiceDB

Request Statistics

Vanilla SpiceDB

Modified SpiceDB

Response Time Statistics

Vanilla SpiceDB

Modified SpiceDB

Vanilla SpiceDB

Modified SpiceDB

Results and Discussion

When comparing the our implementation against SpiceDB's implementation, we find that our latency is on average 57% lesser than the baseline SpiceDB.

​

For a similar load, our implementation has much better (see graph above) CPU utilization when compared with baseline SpiceDB. (25-30% sustained vs 80% sustained)

​

Project Demonstration

Timeline – Update on Tasks

The project has been completed in all the aspects of implementation.

​

• Our implementation of SpiceDB has a 57% better performance on the read path, and does not significantly impact write performance
• Our project has overshot the initial improvement expectation by 50% (we expected a 25% boost, but got 57%).
• We hope to further improve our latency numbers by implementing SVA(k) algorithm and improving the choice of SV. (“earlier” in a graph SVs are better)

​

​

Conclusion and Future work

References

• R. Pang, R. Caceres, M. Burrows, Z. Chen, P. Dave, N. Ger- mer, A. Golynski, K. Graney, N. Kang, L. Kissner, et al., “Zanzibar:{Google’s} Consistent, Global Authorization System,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 33– 46, 2019. �
• J. Moshenko, “Implementing Google Zanzibar Open Source: The Architecture of SpiceDB,” Nov. 2021.

​

• K. Hanauer, M. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” arXiv preprint arXiv:2002.00813, 2020.

• R. Agrawal, A. Borgida, and H. V. Jagadish, “Efficient management of transitive relationships in large data and knowledge bases,” ACM SIGMOD Record, vol. 18, no. 2, pp. 253–262, 1989. �

Thank You