Design a Social Graph Distance Service

Design a real-time social graph service that calculates the shortest path (degree of separation) between any two users in a network of 1 billion users. The system must handle friend additions and removals with strong consistency and return accurate distances within 200ms.