README.md

   1 STINGER
   2 =======
   3 [![Build Status](https://travis-ci.org/robmccoll/stinger.png?branch=master)](https://travis-ci.org/robmccoll/stinger)
   4
   5 Learn more at [stingergraph.com](http://stingergraph.com).
   6
   7 Directory Structure
   8 ===================
   9
  10     .
  11     ├── CMakeLists.txt
  12     ├── README.md
  13     ├── SOURCEME.sh
  14     └── src
  15     ├── bin
  16     │   ├── clients
  17     │   │   ├── algorithms
  18     │   │   ├── streams
  19     │   │   └── tools
  20     │   ├── server
  21     │   └── standalone
  22     │       ├── breadth_first_search
  23     │       ├── community_reagglomeration
  24     │       ├── connected_components
  25     │       ├── insert_remove_benchmark
  26     │       ├── protobuf_test
  27     │       ├── streaming_clustering_coefficients
  28     │       └── streaming_connected_components
  29     └── lib
  30         ├── fmemopen
  31         ├── int_hm_seq
  32         ├── int_ht_seq
  33         ├── intvec
  34         ├── kv_store
  35         ├── protobuf
  36         ├── pugixml
  37         ├── stinger_core
  38         ├── stinger_utils
  39         ├── string
  40         └── vtx_set
  41
  42 Building
  43 ========
  44
  45 STINGER is built using [CMake](http://www.cmake.org).  From the root of STINGER, first create a build directory:
  46
  47     mkdir build && cd build
  48     . ../SOURCME.sh
  49
  50 Then call CMake from that build directory to automatically configure the build and to create a Makefile:
  51
  52     cmake .. -DCMAKE_BUILD_TYPE=Release
  53
  54 Change `Release` to `Debug` for a debugging build during development.  Finally, call make to build all libraries and executable targets (or call make and the name of an executable or library to build):
  55
  56     make
  57
  58 All binary targets will be built and placed in build/bin.  They are named according to the folder from which they were
  59 built (so src/bin/server produces build/bin/server, src/bin/clients/tools/json\_rpc\_server produces
  60 build/bin/json\_rpc\_server, etc.).  If you ran SOURCEME.sh from the build directory as instructed above, the build/bin
  61 directory is appended to your path.
  62
  63 All library targets are built as both static and shared libraries by default and are placed in build/lib as .so and .a files
  64 (or .dylib on Mac).  Headers for these libraries are copied into build/include/library\_name.  The build/include directory
  65 is in the include path of all targets.
  66
  67 Executable Targets
  68 ==================
  69
  70 As indicated by the directory structure, there are three primary types of targets (client, server, standalone)
  71 and subtypes in the case of clients.
  72
  73 Standalone executables are generally self-contained and use the STINGER
  74 libraries for the graph structure and supporting functions.  Most of the existing standalone executables demonstrate
  75 a single streaming or static algorithm on a synthetic R-MAT graph and edge stream.
  76
  77 The STINGER server maintains a STINGER graph in memory and can maintain multiple connections with clients.
  78
  79 Client streams can send edges consisting of source, destination, weight, time, and type where some fields are optional
  80 and others can optionally be text strings.
  81
  82 Client algorithms will receive these batches of updates in a somewhat
  83 synchronous manner as well as shared-memory read only access to the complete graph.  The server provides the capability
  84 for client algorithms to request a shared memory space to store results and communicate with other algorithms.
  85 Client algorithms declare dependencies when they connect and receive the mapped data in the returned structure.
  86 The server guarantees that all of an algorithm's dependencies will finish processing before that algorithm is executed.
  87 Clients algorithms are required to provide a description string that indicates what data is stored and the type of the data.
  88
  89 Client tools are intended to be read-only, but are notified of all running algorithms and shared data.  An example
  90 of this kind of client is the JSON RPC server (src/bin/clients/tools/json\_rpc\_server).  This server provides access
  91 to shared algorithm data via JSON RPC calls over HTTP.  Additionally, some primitive operations are provided to support
  92 selecting the top vertices as scored by a particular algorithm or obtaining the shortest paths between two vertices.
  93
  94 Running
  95 =======
  96
  97 Using the Server
  98 ----------------
  99 To run an example using the server and five terminals:
 100
 101     term1:build$ env STINGER_MAX_MEMSIZE=1G ./bin/server
 102     term2:build$ ./bin/json_rpc_server
 103     term3:build$ ./bin/static_components
 104     term4:build$ ./bin/pagerank
 105     term5:build$ ./bin/rmat_edge_generator -n 100000 -x 10000
 106
 107 This will start a stream of R-MAT edges over 100,000 vertices in batches of 10,000 edges.  A connected component labeling
 108 and PageRank scoring will be maintained.  The JSON RPC server will host interactive web pages at
 109 http://localhost:8088/full.html are powered by the live streaming analysis.  The total memory usage of the dynamic graph is limited to 1 GiB.
 110
 111 To run the above in a single script, you can use the -d option to launch the server in the background.  The server will detach once it is ready for client connections.  Then launch the analysis kernels, possibly gathering the output.  Insert edges, then kill the running server with the -K option when finished.  For example, to insert ten batches of 10000 R-MAT edges:
 112
 113     env STINGER_MAX_MEMSIZE=1G ./bin/server -d
 114     ./bin/simple_communities > simple_communities.out 2>&1 &
 115     ./bin/pagerank_updating > pagerank_updating.out 2>&1 &
 116     sleep 2 # Let the above fully launch.
 117     ./bin/rmat_edge_generator -n 100000 -x 10000 -y 10
 118     ./bin/server -K
 119
 120 Example: Parsing Twitter
 121 ------------------------
 122
 123 Given a stream of Tweets in Twitter's default format (a stream of JSON objects, one per line), it is fairly easy to pipe
 124 the user mentions / retweets graph into STINGER using the json\_stream.  The json\_stream is a templated JSON stream parser
 125 designed to consume one object per line like the Twitter stream and to produce edges from this stream based on a template.
 126
 127 The templates can use the following variables (where one of the two source and one of the two destination variables
 128 must be used):
 129
 130     $source_str         - The source vertex name.
 131     $source             - The source of the edge as a number (must be able to parse as an integer
 132                           less than the maximum vertex ID in the STINGER server).
 133     $source_type        - A string representing the type of the source vertex.
 134     $source_weight      - A number to be added to the weight of the source vertex (vertex weights
 135                           start at zero).
 136     $destination_str    - The destination vertex name
 137     $destination        - The destination of the edge as a number (must be able to parse as an
 138                           integer less than the maximum vertex ID in the STINGER server).
 139     $destination_type   - A string representing the type of the destination vertex
 140     $destination_weight - A number to be added to the weight of the destination vertex (vertex
 141                           weights start at zero).
 142     $type_str           - The edge type as a string
 143     $weight             - The weight of the edge (must be able to parse as an integer).
 144     $time               - The time of the edge (must be able to parse as an integer).
 145     $time_ttr           - Must be a string of either the form "Mon Sep 24 03:35:21 +0000 2012" or
 146                           "Sun, 28 Oct 2012 17:32:08 +0000".  These will be converted internally
 147                           into integers of the form YYYYMMDDHHMMSS.  Note that this does not currently support
 148                           setting a constant value.
 149
 150 For example, the simplest template for Twitter mentions and retweets would be (we'll call this template.json):
 151
 152     {
 153       "user": {
 154         "screen_name": "$source_str1"
 155       },
 156       "entities": {
 157         "user_mentions": [
 158           {
 159             "screen_name": "$destination_str1"
 160           }
 161         ]
 162       },
 163       "this_doesnt_matter": "$source_type=user",
 164       "same_here": "$destination_type=user",
 165       "and_here": "$type=mention"
 166     }
 167
 168 To parse a Twitter stream into STINGER using this template:
 169
 170     cat twitter_sample.json | ./bin/json_stream template.json
 171
 172 You can replace the 'cat twitter\_sample.json' command with one of the curl commands from the Twitter developer
 173 API page to directly inject a live Twitter stream (obviously you should go to dev.twitter.com to get your
 174 own OAuth data):
 175
 176     curl --request 'POST' 'https://stream.twitter.com/1.1/statuses/sample.json' --header
 177     'Authorization: OAuth oauth_consumer_key="KEYKEYKEY", oauth_nonce="NONCENONCENONCE",
 178     oauth_signature="SIGSIGSIG", oauth_signature_method="HMAC-SHA1", oauth_timestamp="ts",
 179     oauth_token="TOKENTOKENTOKEN", oauth_version="1.0"' --verbose | ./bin/json_stream template.json
 180
 181 Example: Parsing CSV Files / Streams
 182 ---------------------------
 183
 184 The csv\_stream parser follows a simpilar templated format to the json parser, so parsing edges out of a file might look like:
 185
 186     id,email_a,config_a,email_b,config_b,unix_time,length
 187     na,$source_str1,na,$destination_str1,na,$time1,$weight1, $source_type1=email, $destination_type1=email
 188
 189 This file would create edges between email addresses using the lenght field as the weight and the Unix timestamp field as the time.  To use this template, pipe the file or stream into the parser and pass the template as a parameter like so:
 190
 191     cat emails.csv | ./bin/csv_stream template.csv
 192
 193 Please be aware that the CSV parser and the underlying code to parse CSV files does not currently trim whitespace, and does not treat quoted strings of any kind as quoted.
 194
 195 Using a Standalone Client
 196 -------------------------
 197 To create a toy R-MAT graph (256K vertices and 2M undirected edges) and run the insert-remove benchmark:
 198
 199     term1:build$ rmat_graph_generator -s 18 -e 8
 200     term1:build$ insert_remove_benchmark -n 1 -b 100000 g.18.8.bin a.18.8.100000.bin
 201
 202
 203 [![githalytics.com alpha](https://cruel-carlota.pagodabox.com/a7d82e7aa670122314238336dbbd7c89 "githalytics.com")](http://githalytics.com/robmccoll/stinger)
 204
 205 Handling Common Errors
 206 ======================
 207
 208 Runtime Issues
 209 --------------
 210
 211 The first thing to understand is how STINGER manages memory. When STINGER starts, it allocates one large block of memory (enough to hold its maximum size), and then manages its own memory allocation from that pool.  The server version of STINGER does this in shared memory so that multiple processes can see the graph.  Unfortunately, the error handling for memory allocations is not particularly user-friendly at the moment.  Changing the way that this works is on the issues list (see https://github.com/robmccoll/stinger/issues/8).
 212
 213 - "Bus error" when running the server: The size of STINGER that the server is trying to allocate is too large for your memory.  Reduce the size of your STINGER and recompile.
 214 - "XXX: eb pool exhausted" or "STINGER has run out of internal storage space" when running the server, standalone executables, or anything else using stinger\_core: you have run out of internal edge storage.  Increase the size of STINGER and recompile.
 215
 216 To solve these problems: there are a few values in stinger\_defs.h (https://github.com/robmccoll/stinger/blob/master/src/lib/stinger_core/inc/stinger_defs.h) that determine the maximum size of the graph.  You can tune these values and recompile (you will need to do a clean rebuild - make clean beforehand).
 217
 218     /** Maximum number of vertices in STINGER */
 219     #if !defined(STINGER_MAX_LVERTICES)
 220     #if defined (__MTA__)
 221     /* XXX: Assume only 2**25 vertices */
 222     #define STINGER_MAX_LVERTICES (1L<<27)
 223     #else
 224     /* much smaller for quick testing */
 225     #define STINGER_MAX_LVERTICES (1L<<22)
 226     #endif
 227     #endif
 228     /** Edges per edge block */
 229     #define STINGER_EDGEBLOCKSIZE 14
 230     /** Number of edge types */
 231     #define STINGER_NUMETYPES 5
 232     /** Number of vertex types (with names) */
 233     #define STINGER_NUMVTYPES 128
 234
 235 STINGER\_MAX\_LVERTICES determines the maximum number of vertices (here written as 1L<<22 or roughly 4 million).
 236 STINGER\_EDGEBLOCKSIZE determines how many edges are in each edge block (there are 4 * STINGER\_MAX\_LVERTICES edge blocks, so 4 * STINGER\_MAX\_LVERTICES * STINGER\_EDGEBLOCKSIZE is the maximum number of directed edges).
 237 STINGER\_NUMETYPES determines the maximum number of edge types.
 238
 239 Make sure to modify the STINGER\_MAX\_LVERTICES listed under much smaller for quick testing.  These are listed in the order of how much of an affect they will have on the size of Stinger.
 240
 241 Build Problems
 242 --------------
 243
 244 First check the STINGER GitHub page to verify that the build is passing (icon immediately under the title).  If it is not passing, the issue resides within the current version itself.  Please checkout a previous revision - the build should be fixed shortly as failing builds sent notifications to the authors.
 245
 246 Build problems after pulling updates are frequently the result of changes to the Protocol Buffer formats used in STINGER.  These are currently unavoidable as an unfortunate side effect of how we distribute PB and tie it into CMake.  To fix, remove your build directory and build STINGER from scratch.
 247
 248 Additionally, this version of the STINGER tool suite is tested almost exclusively on Linux machines running later version of Debian, Ubuntu, and Fedora.  While we would like to have multi-platform compatibility with Mac (via "real" GCC) and Windows (via GCC on cygwin), these are lower priority for our team - unless a project sponsor requires it.