Odysseus/SNS: Reclaiming Relational Supremacy in Massive Social Networks

TL;DR

Odysseus/SNS proves that the Relational Model is not only viable but superior for Social Networking Services (SNS) at the scale of billions of users. By leveraging Hierarchical Clustering and a Deferred Delete Strategy, the system eliminates expensive inter-node joins and multi-node transactions, achieving up to 90% better performance on critical operations like Timeline and Newsfeed views compared to traditional graph-based architectures.

Problem: The "Random Distribution" Trap of Graph NoSQL

Modern giants like Facebook often use a hybrid approach: data is stored in a massively parallel system but represented as a low-level Graph Model (objects and associations).

While NoSQL offers high horizontal scalability through simple key-value lookups, it suffers from a lack of "semantic awareness." Because objects are often hashed and distributed randomly, a single user's timeline query might require the system to "scatter-gather" data from dozens of different machines. This incurs heavy network latency and makes complex operations like joins nearly impossible without massive overhead.

Methodology: Semantic-Aware Data Distribution

The core insight of the authors is that if the system understands the relationships between entities, it can place them geographically close (on the same node).

1. Hierarchical Clustering via Identifying Keys

The authors transform traditional "one-to-many" relationships into Identifying Relationships.

• The Concept: A "Comment" doesn't just exist; it belongs to a "Post," which belongs to a "User."
• The Implementation: The primary key of the root entity (e.g., user_id) is cascaded down as an Identifying Key. By hashing all related tuples (User, Posts, Comments) on this same key, the system ensures they reside on the same physical node.
• The Result: A "Timeline" operation, which previously required inter-node joins, becomes a single-node transaction.

Figure: Partitioning relations by identifying key ensures hierarchical data stays on the same node.

2. Amortizing the Cost of Many-to-Many Deletes

Many-to-Many (M:N) relationships (like Group memberships) are harder to cluster because an entity can belong to many roots. Standard distributed databases use a "Two-Phase Commit" (2PC) to ensure consistency, which is a notorious performance killer.

Odysseus/SNS uses a Deferred Delete Strategy:

1. When a user deactivates, the system deletes the primary record immediately.
2. It defers removing references to that user in distant group lists.
3. These dangling references are cleaned up only when someone actually tries to access them. This effectively turns a global, multi-node heavy transaction into multiple, lightweight single-node updates.

Performance: Breaking the Scale Barrier

The evaluation used a workload modeled after Facebook's published statistics, scaled to 1.2 billion objects per node.

Figure: Comparative analysis of normalized processing times.

Significant gains were recorded:

• Timeline Access: Reduced by ~90% due to local execution.
• Newsfeed Generation: Reduced by ~68% by minimizing the number of nodes involved.
• Delete Operations: Drastically faster (up to 96% reduction) because the system stops waiting for network-wide acknowledgments.

Critical Analysis & Conclusion

The success of Odysseus/SNS suggests that the industry's shift away from Relational DBMS (RDBMS) toward NoSQL might have been premature, driven by a lack of sophisticated partitioning strategies rather than inherent flaws in the relational model.

Takeaways:

• Intelligence over Brute Force: Hierarchical clustering allows RDBMS to retain ACID properties without sacrificing the "scale-out" benefits of NoSQL.
• Semantic Design: The database schema isn't just for storage; it's a tool for network optimization.

Limitations:

• Deletions & Garbage: While deferred deletes help performance, they may leave "dead references" temporarily, which might not be suitable for systems requiring immediate, strict referential integrity.
• Insert Overhead: Insertions into M:N relationships still require some coordination, though the authors note this is mitigated by the binary nature of SNS relationships.

In conclusion, Odysseus/SNS provides a blueprint for the "NewSQL" era, proving that with the right semantic optimizations, we can have both the reliability of SQL and the speed of the social web.