Dynamic routes

This PR is a work in progress towards adding dynamic routes #77. I validated my understanding of the problem and the solution I sketched out on #77 by first updating the mock Datastore. Then I wrote more tests and some benchmarks. The postgres implementation was a little more complicated than I first thought, but it's working (check my tests for any missed edge cases!). I'll start on Bolt next.

TODO:

[x] Mock [x] Tests [x] Benchmarks [x] Postgres [x] Bolt [x] Cleanup

Benchmarks

I wrote a handful of benchmarks to measure route lookup speed in a few situations: - standard: varying numbers of apps and 'standard' routes - segmentCount: varying numbers of path segments - /test /test/test - branchFactor: vary numbers of paths per segment/node - /test1 /test2/ /test3 - segmentSize: varying numbers of characters per path segment - /a /aa /aaa

Mock

This one is pretty snappy as expected. It will be interesting to see how it maps onto Bolt.

BenchmarkDatastore/GetRoute/standard/apps=100/routes=10-4            3000000           569 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=100-4           3000000           578 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=1000-4          2000000           705 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=10000-4         2000000           724 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=10-4             3000000           486 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=100-4            3000000           585 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=1000-4           2000000           642 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=10000-4          2000000           679 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=10-4              3000000           466 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=100-4             3000000           535 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=1000-4            3000000           556 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=10000-4           2000000           633 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=1-4               10000000           190 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=5-4                3000000           428 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=10-4               2000000           698 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=50-4                500000          2902 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=100-4               200000          5689 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=1-4               10000000           197 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=5-4                5000000           219 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=10-4              10000000           219 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=50-4              10000000           258 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=100-4             10000000           218 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=500-4             10000000           227 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=1000-4             5000000           229 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=5000-4            10000000           235 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=10000-4           10000000           239 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=1-4                    5000000           447 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=5-4                    3000000           433 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=10-4                   3000000           503 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=50-4                   1000000          1085 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=100-4                  1000000          1674 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=200-4                   500000          2954 ns/op

Postgres

I haven't investigated the limiting factors here, but it's a starting point, and it would be interesting to see the difference a real postgres instance makes, compared to the on-demand local container used here.

In general, these numbers would be greatly improved through the use of a custom index, but this regex approach is much simpler and more portable.

BenchmarkDatastore/GetRoute/standard/apps=100/routes=10-4               5000        255551 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=100-4              1000       2069528 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=1000-4             1000       1929290 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=10000-4             500       2244895 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=100000-4              300       4623863 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=10-4                5000        378152 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=100-4               1000       2074248 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=1000-4              1000       2190993 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=10000-4              500       4118233 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=10-4                 3000        432084 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=100-4                 500       2427358 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=1000-4                500       3858346 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=10000-4               100      14040583 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=1-4                   5000        297277 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=5-4                   3000        335625 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=10-4                  3000        384372 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=50-4                  2000        987397 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=100-4                 1000       1977562 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=1-4                   5000        346381 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=5-4                   5000        329776 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=10-4                  3000        346472 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=50-4                  2000        699068 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=100-4                 2000        767996 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=500-4                 1000       1089479 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=1000-4                1000       1642663 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=5000-4                 300       5156957 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=10000-4                200       9478381 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=1-4                       5000        287341 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=5-4                      10000        234003 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=10-4                      5000        243681 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=50-4                      3000        423030 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=100-4                     2000        697696 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=200-4                     1000       2105683 ns/op

Bolt

BenchmarkDatastore/GetRoute/standard/apps=100/routes=10-4             100000         10394 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=100-4            100000         11161 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=1000-4           100000         11792 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=10000-4          100000         12266 ns/op
BenchmarkDatastore/GetRoute/standard/apps=100/routes=100000-4                 3000        620729 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=10-4              100000         10154 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=100-4             100000         10718 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=1000-4            100000         11782 ns/op
BenchmarkDatastore/GetRoute/standard/apps=10/routes=10000-4             3000        501588 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=10-4               100000         10026 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=100-4              100000         10925 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=1000-4             100000         11803 ns/op
BenchmarkDatastore/GetRoute/standard/apps=1/routes=10000-4              3000        499176 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=1-4                 200000          8758 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=5-4                 200000         10325 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=10-4                100000         13882 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=50-4                 30000         42406 ns/op
BenchmarkDatastore/GetRoute/segmentCount/segments=100-4                20000         75791 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=1-4                 200000          7748 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=5-4                 200000          7778 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=10-4                200000          7797 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=50-4                200000          9140 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=100-4               200000          8018 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=500-4               200000          8145 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=1000-4              200000          8279 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=5000-4              200000          8536 ns/op
BenchmarkDatastore/GetRoute/branchFactor/branches=10000-4             100000         10752 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=1-4                     200000         10066 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=5-4                     100000         10360 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=10-4                    100000         10975 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=50-4                    100000         13087 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=100-4                   100000         16011 ns/op
BenchmarkDatastore/GetRoute/segmentSize/chars=200-4                   100000         21656 ns/op

UPDATE Throwing up some Bolt numbers now that it's functional: It appears to be roughly 10x slower than the mock, and roughly 100x faster than postgres. After I do some cleanup I'll re-run them all fresh and update. UPDATE 2 New numbers for all three. UPDATE 3 100,000 routes for bolt and postgres.

该提问来源于开源项目：iron-io/functions