A data-locality-aware task scheduler for distributed social graph queries

For large-scale online social networks such as Facebook and Twitter, network analysis often uses graph queries to extract network information. Because of the work and memory required, usually such queries are performed in a distributed manner. However, most existing distributed graph computation systems optimize for offline graph analysis rather than online graph queries. The problem with this approach is that graph query tasks then must transfer a large volume of data and interactively answer queries within a short time frame. To resolve this, we propose a novel data-locality-aware task scheduling algorithm that optimizes interactive distributed graph queries. The scheduling algorithm jointly considers data placement and graph topology to reduce data transfer costs. After implementing the scheduling algorithm in a real-world distributed graph computation system, we evaluate the task scheduler’s effectiveness through simulations and real-life social graph queries. Results show that our scheduler reduces the querying time by one order of magnitude.