• Stars
    star
    694
  • Rank 61,295 (Top 2 %)
  • Language
    Java
  • License
    Apache License 2.0
  • Created almost 8 years ago
  • Updated 11 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

GraphJet is a real-time graph processing library.

GraphJet

Build Status

GraphJet is a real-time graph processing library written in Java that maintains a full graph index over a sliding time window in memory on a single server. This index supports a variety of graph algorithms including personalized recommendation algorithms based on collaborative filtering. These algorithms power a variety of real-time recommendation services within Twitter, notably content (tweets/URLs) recommendations that require collaborative filtering over a heterogeneous, rapidly evolving graph.

GraphJet is able to support rapid ingestion of edges in an evolving graph while concurrently serving lookup queries through a combination of compact edge encoding and a dynamic memory allocation scheme. Each GraphJet server can ingest up to one million graph edges per second, and in steady state, computes up to 500 recommendations per second, which translates into several million edge read operations per second. More information about the internals of GraphJet can be found in the VLDB'16 paper.

Quick Start and Example

After cloning the repo, build as follows (for the impatient, use option -DskipTests to skip tests):

$ mvn package install

GraphJet includes a demo that reads from the Twitter public sample stream using the Twitter4j library and maintains two separate in-memory bipartite graphs:

  • A bipartite graph of user-tweet interactions. The left-hand side vertices represent users, the right-hand side vertices represent tweets, and the edges represent tweet posts and retweets.
  • A bipartite graph of tweet-hashtag contents. The left-hand side vertices represent tweets, the right-hand side vertices represent hashtags, and the edges represent content association (e.g., a tweet contains a hashtag).

To run the demo, create a file called twitter4j.properties in the GraphJet base directory with your Twitter credentials (replace xxxx with actual credentials):

oauth.consumerKey=xxxx
oauth.consumerSecret=xxxx
oauth.accessToken=xxxx
oauth.accessTokenSecret=xxxx

For obtaining the credentials, see documentation on obtaining Twitter OAuth tokens. The public sample stream is available to registered users, see documentation about Twitter streaming APIs for more details.

Once you've built GraphJet, start the demo as follows:

$ mvn exec:java -pl graphjet-demo -Dexec.mainClass=com.twitter.graphjet.demo.TwitterStreamReader

Once the demo starts up, it begins ingesting the Twitter public sample stream. The program will print out a sequence of status messages indicating the internal state of the user-tweet graph and the tweet-hashtag graph.

You can interact with the graph via a REST API, running on port 8888 by default; use -Dexec.args="-port xxxx" to specify a different port.

The following calls are available to query the state of the in-memory bipartite graph of user-tweet interactions:

  • userTweetGraph/topTweets: queries for the top tweets in terms of interactions (retweets). Use parameter k to specify number of results to return (default ten). Sample invocation:
curl http://localhost:8888/userTweetGraph/topTweets?k=5
  • userTweetGraph/topUsers: queries for the top users in terms of interactions (retweets). Use parameter k to specify number of results to return (default ten). Sample invocation:
curl http://localhost:8888/userTweetGraph/topUsers?k=5
  • userTweetGraphEdges/tweets: queries for the edges incident to a particular tweet in the user-tweet graph, i.e., users who have interacted with the tweet. Use parameter id to specify tweetId (e.g., from userTweetGraph/topTweets above). Sample invocation:
curl http://localhost:8888/userTweetGraphEdges/tweets?id=xxx
  • userTweetGraphEdges/users: queries for the edges incident to a particular user in the user-tweet graph, i.e., tweets the user interacted with. Use parameter id to specify userId (e.g., from userTweetGraph/topUsers above). Sample invocation:
curl http://localhost:8888/userTweetGraphEdges/users?id=xxx

The following calls are available to query the state of the in-memory bipartite graph of tweet-hashtag contents:

  • tweetHashtagGraph/topTweets: queries for the top tweets in terms of hashtags. Use parameter k to specify number of results to return (default ten). Sample invocation:
curl http://localhost:8888/tweetHashtagGraph/topTweets?k=5
  • tweetHashtagGraph/topHashtags: queries for the top hashtags in terms of tweets. Use parameter k to specify number of results to return (default ten). Sample invocation:
curl http://localhost:8888/tweetHashtagGraph/topHashtags?k=5
  • tweetHashtagGraphEdges/tweets: queries for the edges incident to a particular tweet in the tweet-hashtag graph, i.e., hashtags contained in the tweet. Use parameter id to specify tweetId (e.g., from tweetHashtagGraph/topTweets above). Sample invocation:
curl http://localhost:8888/tweetHashtagGraphEdges/tweets?id=xxx
  • tweetHashtagGraphEdges/hashtags: queries for the edges incident to a particular hashtag in the tweet-hashtag graph, i.e., tweets the given hashtag is contained in. Use parameter id to specify hashtagId (e.g., from tweetHashtagGraph/topHashtags above). Sample invocation:
curl http://localhost:8888/tweetHashtagGraphEdges/hashtags?id=xxx

The demo program illustrates collaborative filtering via similarity queries on the tweet-hashtag graph. Note that the demo does not offer personalized recommendation algorithms on the user-tweet graph (as is deployed inside Twitter) because the public sample stream API is too sparse in terms of interactions to give good results. The following endpoint for similarity queries offers related hashtags given an input hashtag:

  • similarHashtags: computes similar hashtag to the input hashtag based on real time data. Use parameter hashtag to specify hashtag (e.g., from tweetHashtagGraph/topHashtags above). Sample invocation:
curl http://localhost:8888/similarHashtags?hashtag=trump&k=10

License

Copyright 2016 Twitter, Inc.

Licensed under the Apache License, Version 2.0

More Repositories

1

the-algorithm

Source code for Twitter's Recommendation Algorithm
Scala
60,419
star
2

typeahead.js

typeahead.js is a fast and fully-featured autocomplete library
JavaScript
16,540
star
3

twemoji

Emoji for everyone. https://twemoji.twitter.com/
HTML
16,448
star
4

twemproxy

A fast, light-weight proxy for memcached and redis
C
11,940
star
5

the-algorithm-ml

Source code for Twitter's Recommendation Algorithm
Python
9,788
star
6

finagle

A fault tolerant, protocol-agnostic RPC system
Scala
8,716
star
7

hogan.js

A compiler for the Mustache templating language
JavaScript
5,139
star
8

labella.js

Placing labels on a timeline without overlap.
JavaScript
3,864
star
9

scala_school

Lessons in the Fundamentals of Scala
HTML
3,698
star
10

AnomalyDetection

Anomaly Detection with R
R
3,525
star
11

scalding

A Scala API for Cascading
Scala
3,465
star
12

twitter-text

Twitter Text Libraries. This code is used at Twitter to tokenize and parse text to meet the expectations for what can be used on the platform.
HTML
3,041
star
13

TwitterTextEditor

A standalone, flexible API that provides a full-featured rich text editor for iOS applications.
Swift
2,938
star
14

opensource-website

Twitter's open source website, identifying projects we've released, organizations we support, and the work we do to support open source.
SCSS
2,852
star
15

util

Wonderful reusable code from Twitter
Scala
2,671
star
16

algebird

Abstract Algebra for Scala
Scala
2,275
star
17

finatra

Fast, testable, Scala services built on TwitterServer and Finagle
Scala
2,269
star
18

effectivescala

Twitter's Effective Scala Guide
HTML
2,237
star
19

summingbird

Streaming MapReduce with Scalding and Storm
Scala
2,137
star
20

pelikan

Pelikan is Twitter's unified cache backend
C
1,914
star
21

ios-twitter-image-pipeline

Twitter Image Pipeline is a robust and performant image loading and caching framework for iOS clients
C
1,850
star
22

twurl

OAuth-enabled curl for the Twitter API
Ruby
1,782
star
23

rezolus

Systems performance telemetry
Rust
1,539
star
24

twitter-server

Twitter-Server defines a template from which services at Twitter are built
Scala
1,522
star
25

activerecord-reputation-system

An Active Record Reputation System for Rails
Ruby
1,335
star
26

fatcache

Memcache on SSD
C
1,306
star
27

compose-rules

Static checks to aid with a healthy adoption of Compose
Kotlin
1,293
star
28

rsc

Experimental Scala compiler focused on compilation speed
Scala
1,243
star
29

communitynotes

Documentation and source code powering Twitter's Community Notes
Python
1,146
star
30

elephant-bird

Twitter's collection of LZO and Protocol Buffer-related Hadoop, Pig, Hive, and HBase code.
Java
1,139
star
31

cassovary

Cassovary is a simple big graph processing library for the JVM
Scala
1,039
star
32

Serial

Light-weight, fast framework for object serialization in Java, with Android support.
Java
982
star
33

hbc

A Java HTTP client for consuming Twitter's realtime Streaming API
Java
962
star
34

twemcache

Twemcache is the Twitter Memcached
C
926
star
35

innovators-patent-agreement

Innovators Patent Agreement (IPA)
917
star
36

vireo

Vireo is a lightweight and versatile video processing library written in C++11
C++
915
star
37

twitter-korean-text

Korean tokenizer
Scala
831
star
38

scrooge

A Thrift parser/generator
Scala
785
star
39

BreakoutDetection

Breakout Detection via Robust E-Statistics
C++
751
star
40

twitter-cldr-rb

Ruby implementation of the ICU (International Components for Unicode) that uses the Common Locale Data Repository to format dates, plurals, and more.
Ruby
663
star
41

bijection

Reversible conversions between types
Scala
662
star
42

chill

Scala extensions for the Kryo serialization library
Scala
603
star
43

ios-twitter-network-layer

Twitter Network Layer is a scalable and feature rich network layer built on top of NSURLSession for Apple platforms
Objective-C
572
star
44

hadoop-lzo

Refactored version of code.google.com/hadoop-gpl-compression for hadoop 0.20
Shell
544
star
45

storehaus

Storehaus is a library that makes it easy to work with asynchronous key value stores
Scala
465
star
46

rpc-perf

A tool for benchmarking RPC services
Rust
459
star
47

d3kit

D3Kit is a set tools to speed D3 related project development
JavaScript
427
star
48

scoot

Scoot is a distributed task runner, supporting both a proprietary API and Bazel's Remote Execution.
Go
347
star
49

twitter-cldr-js

JavaScript implementation of the ICU (International Components for Unicode) that uses the Common Locale Data Repository to format dates, plurals, and more. Based on twitter-cldr-rb.
JavaScript
344
star
50

scala_school2

Scala School 2
Scala
342
star
51

rustcommon

Common Twitter Rust lib
Rust
340
star
52

wordpress

The official Twitter plugin for WordPress. Embed Twitter content and grow your audience on Twitter.
PHP
311
star
53

ios-twitter-logging-service

Twitter Logging Service is a robust and performant logging framework for iOS clients
Objective-C
300
star
54

nodes

A library to implement asynchronous dependency graphs for services in Java
Java
246
star
55

SentenTree

A novel text visualization technique
JavaScript
223
star
56

interactive

Twitter interactive visualization
HTML
213
star
57

joauth

A Java library for authenticating HTTP Requests using OAuth
Java
210
star
58

thrift_client

A Thrift client wrapper that encapsulates some common failover behavior
Ruby
196
star
59

hpack

Header Compression for HTTP/2
Java
194
star
60

zktraffic

ZooKeeper protocol analyzer and stats gathering daemon
Python
164
star
61

twemoji-parser

A simple library for identifying emoji entities within a string in order to render them as Twemoji.
Scala
157
star
62

sbf

Java
154
star
63

cache-trace

A collection of Twitter's anonymized production cache traces.
Shell
151
star
64

tormenta

Scala extensions for Storm
Scala
132
star
65

whiskey

HTTP library for Android (beta)
Java
132
star
66

hraven

hRaven collects run time data and statistics from MapReduce jobs in an easily queryable format
Java
129
star
67

netty-http2

HTTP/2 for Netty
Java
121
star
68

ccommon

Cache Commons
C
99
star
69

sqrl

A Safe, Stateful Rules Language for Event Streams
TypeScript
99
star
70

focus

Focus aligns Git worktree content based on outlines of a repository's Bazel build graph. Focused repos are sparse, shallow, and thin and unlock markedly better performance in large repos.
Rust
89
star
71

dict_minimize

Access scipy optimizers from your favorite deep learning framework.
Python
74
star
72

metrics

74
star
73

twitter.github.io

HTML
71
star
74

go-bindata

Go
67
star
75

diffusion-rl

Python
65
star
76

birdwatch

64
star
77

cloudhopper-commons

Cloudhopper Commons
Java
57
star
78

twitter-cldr-npm

TwitterCldr npm package
JavaScript
49
star
79

.github

Twitter GitHub Organization-wide files
46
star
80

bazel-multiversion

Bazel rules to resolve, fetch and manage 3rdparty JVM dependencies with support for multiple parallel versions of the same dependency. Powered by Coursier.
Scala
45
star
81

libwatchman

A C interface to watchman
C
44
star
82

sslconfig

Twitter's OpenSSL Configuration
42
star
83

gatekeeper-service

GateKeeper is a service built to automate the manual steps involved in onboarding, offboarding, and lost asset scenarios.
Python
36
star
84

ios-twitter-apache-thrift

A thrift encoding and decoding library for Swift
Swift
36
star
85

dodo

The Twitter OSS Project Builder
Shell
35
star
86

repo-scaffolding

Tools for creating repos based on open source standards and best practices
31
star
87

iago2

A load generator, built for engineers
Scala
24
star
88

caladrius

Performance modelling system for Distributed Stream Processing Systems (DSPS) such as Apache Heron and Apache Storm
Python
22
star
89

ossdecks

Repository for Twitter Open Source Decks
10
star
90

curation-style-guide

Document Repository for Twitter's Curation Style Guide
10
star
91

analytics-infra-governance

Description of the process for how to commit, review, and release code to the Scalding OSS family (Scalding, Summingbird, Algebird, Bijection, Storehaus, etc)
9
star
92

gpl-commitment

Twitter's GPL Cooperation Commitment
5
star
93

second-control-probability-distributions

4
star
94

google-tag-manager-event-tag

Smarty
3
star
95

google-tag-manager-base-tag

Smarty
2
star