RRRR Rapid Real-time Routing
RRRR (usually pronounced R4) is a C-language implementation of the RAPTOR public transit routing algorithm. It is the core routing component of the Bliksem journey planner and passenger information system. The goal of this project is to generate sets of Pareto-optimal itineraries over large geographic areas (e.g. BeNeLux or all of Europe), improving on the resource consumption and complexity of existing more flexible alternatives. The system should eventually support real-time vehicle/trip updates reflected in trip plans and be capable of running directly on a mobile device with no Internet connection.
Multiple RRRR processes running on the same machine map the same read-only data file into their private address space. This file contains a structured and indexed representation of transit timetables and other information from a GTFS feed. Additional handler processes should only increase physical memory consumption by the amount needed for search state (roughly 16 * num_stops * max_transfers bytes, on the order of a few megabytes). Eventually the real-time updater process will probably also use memory-mapped files for interprocess communication.
Each worker is a separate process and keeps a permanent scratch buffer that is reused from one request to the next, so no dynamic memory allocation is performed in inner loops. Transit stops are the only locations considered. On-street searches will not be handled in the first phase of development. Eventually we will probably use protocol buffers over a 0MQ fan-out pattern to distribute real-time updates. This is basically standard GTFS-RT over a message passing system instead of HTTP pull.
It looks like in may be possible to keep memory consumption for a Portland, Oregon-sized system under 10MiB. Full Netherlands coverage should be possible in about 20MiB.
zeromq and libczmq: Message passing / concurrency framework used by RRRR for load balancing and scaling.
libprotobuf-c: For decoding incoming realtime messages. https://code.google.com/p/protobuf-c/downloads/list, Ubuntu packages libprotobuf-c0 and libprotobuf-c0-dev.
libwebsockets: For receiving incremental realtime messages. https://github.com/warmcat/libwebsockets.
shapelib: For visualizing realtime messages in OpenGL using a map of choice. http://download.osgeo.org/shapelib/.
libsdl: For visualizing realtime messages in OpenGL via een SDL surface. http://libsdl.org/download-1.2.php.
gcc or clang: clang provides very good error messages and warnings. RRRR benefits greatly from -O2 and link-time optimization. http://clang.llvm.org/.
check: a unit testing framework for c. http://check.sourceforge.net/.
Building transit data
Download a GTFS feed for your favorite transit agency. We typically work with http://gtfs.ovapi.nl/gtfs-nl.zip.
We used to depend on Graphserver for its gtfsdb Python class which loads a GTFS feed into Sqlite and
provides query methods. We have now copied our customized gtfsdb class into the RRRR repository.
python gtfsdb.py input.gtfs.zip output.gtfsdb to load your GTFS feed into an SQLite database.
python transfers.py output.gtfsdb to add distance-based transfers to the transfers table in the database.
python timetable.py output.gtfsdb to create the timetable file
timetable.dat based on that GTFS database.
Use specific types from stdint.h for cross-platform compatibility. Absolute times are stored in uint64 and referenced from the Epoch. The absolute time are always stored with DST disabled this as DST is defined at serviceday instead of the usual 3 am. Times in schedules are uint16 and referenced from midnight. 2**16 / 60 / 60 is only 18 hours, but by right-shifting all times one bit we get 36 hours (1.5 days) at 2 second resolution. When the result of a function is an array, the function should return a pointer to the array and store the number of elements in an indirected parameter (rather than the other way around). The data file is mostly a column store.
Building and starting up RRRR
~/git/rrrr$ make clean && make && ./rrrr.sh
you should see make output followed by the broker and workers restarting:
killing old processes rrrr: broker terminating rrrr: worker terminating rrrr: worker terminating rrrr: worker terminating rrrr: worker terminating starting new processes rrrr: broker starting up rrrr: worker starting up rrrr: worker starting up rrrr: worker starting up rrrr: worker starting up rrrr: worker sent ready message to load balancer rrrr: worker sent ready message to load balancer rrrr: worker sent ready message to load balancer rrrr: worker sent ready message to load balancer rrrr: test client starting rrrr: test client number of requests: 1 rrrr: test client concurrency: 1 rrrr: test client thread will send 1 requests rrrr: test client received response: OK rrrr: test client thread terminating rrrr: 1 threads, 1 total requests, 0.036565 sec total time (27.348557 req/sec)
Then you should be able to run the test client:
~/git/rrrr$ ./client rand 1000 4 rrrr: test client starting rrrr: test client number of requests: 1000 rrrr: test client concurrency: 4 rrrr: test client thread will send 250 requests rrrr: test client thread will send 250 requests rrrr: test client thread will send 250 requests rrrr: test client thread will send 250 requests rrrr: worker received 100 requests rrrr: worker received 100 requests rrrr: worker received 100 requests rrrr: worker received 100 requests rrrr: broker: frx 0502 ftx 0499 brx 0499 btx 0502 / 4 workers rrrr: worker received 200 requests rrrr: worker received 200 requests rrrr: worker received 200 requests rrrr: worker received 200 requests rrrr: test client thread terminating rrrr: test client thread terminating rrrr: test client thread terminating rrrr: test client thread terminating rrrr: 4 threads, 1000 total requests, 3.893521 sec total time (256.836935 req/sec)
This project distinguishes between several types of tests. The unit tests check individual C units related to the RRRR router repository, such as the BitSet or RadixTree implementations. They make use of the
check framework [http://check.sourceforge.net/]. The functional tests demonstrate that the Bliksem system meets the functional requirements of the MMRI project through which it was created. The performance tests demonstrate response time and throughput on journey planning operations connecting 50 points throughout the Netherlands. The performance tests and functional tests are types of integration tests, in that they test the process of issuing requests to a fully-assembled trip planner system rather than its individual components.
testerrrr tool is a single-binary planner which allows planning simple queries without starting up separate broker or worker processes. It is simple to use this tool on a planner validation set such as the one used by MMRI.
Given a test, zip the test to a GTFS-file and compile the GTFS-file to a GTFSdb. Use the resulting GTFSdb as input for our timetable builder.
zip test.zip *.txt gs_gtfsdb_compile test.zip test.gtfsdb timetable.py test.gtfsdb
The tool can now be executed:
./testerrrr --from-idx=1 --to-idx=2 -a -D 2014-01-01T00:00:00 -T timetable.dat ./testerrrr --from-idx=1 --to-idx=2 -d -D 2014-01-01T00:00:00 -T timetable.dat
Copyright 2013 Bliksem Labs. See the LICENSE file at the top-level directory of this distribution and at https://github.com/bliksemlabs/rrrr/. RRRR is released under the BSD 2-clause (simplified) license.