| | | 1 | | using System; |
| | | 2 | | using System.Collections.Concurrent; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using System.Threading; |
| | | 5 | | using Itinero.Network; |
| | | 6 | | using Itinero.Network.Tiles.Standalone.Global; |
| | | 7 | | |
| | | 8 | | namespace Itinero.Data; |
| | | 9 | | |
| | | 10 | | /// <summary> |
| | | 11 | | /// A manager to manage mapping or vertex and edge ids and turn restrictions. |
| | | 12 | | /// </summary> |
| | | 13 | | /// <remarks> |
| | | 14 | | /// Safe for concurrent tile insertion. Every structure here is bookkeeping that spans tiles — |
| | | 15 | | /// the tile data itself lives in the tiles — so this is what several inserts running at once |
| | | 16 | | /// contend on, and each piece needs a different guarantee: |
| | | 17 | | /// |
| | | 18 | | /// <list type="bullet"> |
| | | 19 | | /// <item>the id sets only ever gain independent entries, so a concurrent dictionary is enough;</item> |
| | | 20 | | /// <item>a boundary crossing has to be claimed <b>atomically</b> — two tiles must not both |
| | | 21 | | /// believe they matched the same crossing and each create the edge;</item> |
| | | 22 | | /// <item>pending restrictions are scanned and removed as a batch, which a concurrent collection |
| | | 23 | | /// cannot express, so they keep a lock and it is held inside this class rather than left to |
| | | 24 | | /// callers to remember.</item> |
| | | 25 | | /// </list> |
| | | 26 | | /// </remarks> |
| | | 27 | | public class GlobalNetworkManager |
| | | 28 | | { |
| | | 29 | | /// <summary> |
| | | 30 | | /// Creates a new global network manager. |
| | | 31 | | /// </summary> |
| | 126 | 32 | | public GlobalNetworkManager() |
| | 126 | 33 | | { |
| | 126 | 34 | | this.VertexIdSet = new GlobalVertexIdSet(); |
| | 126 | 35 | | this.EdgeIdSet = new GlobalEdgeIdSet(); |
| | 126 | 36 | | } |
| | | 37 | | |
| | | 38 | | /// <summary> |
| | | 39 | | /// The global vertex id set. |
| | | 40 | | /// </summary> |
| | 0 | 41 | | public GlobalVertexIdSet VertexIdSet { get; } |
| | | 42 | | |
| | | 43 | | /// <summary> |
| | | 44 | | /// The global edge id set. |
| | | 45 | | /// </summary> |
| | 17870 | 46 | | public GlobalEdgeIdSet EdgeIdSet { get; } |
| | | 47 | | |
| | | 48 | | /// <summary> |
| | | 49 | | /// Pending boundary crossings keyed by GlobalEdgeId. |
| | | 50 | | /// When a crossing's matching tile isn't loaded yet, store the local vertex and metadata here. |
| | | 51 | | /// When the other tile loads and has a crossing with the same GlobalEdgeId, it creates the edge. |
| | | 52 | | /// </summary> |
| | 126 | 53 | | private readonly ConcurrentDictionary<GlobalEdgeId, (VertexId vertex, |
| | 126 | 54 | | IEnumerable<(string key, string value)> attributes, uint edgeTypeId, bool isIncoming)> |
| | 126 | 55 | | _pendingBoundaryCrossings = new(); |
| | | 56 | | |
| | | 57 | | /// <summary> |
| | | 58 | | /// Claims the pending half of a boundary crossing, or records this half and waits for the other. |
| | | 59 | | /// </summary> |
| | | 60 | | /// <param name="globalEdgeId">The crossing's global edge id.</param> |
| | | 61 | | /// <param name="half">This tile's half of the crossing.</param> |
| | | 62 | | /// <param name="other">The other half, when this call claimed it.</param> |
| | | 63 | | /// <returns>True when the pair is complete and the caller should create the edge.</returns> |
| | | 64 | | /// <remarks> |
| | | 65 | | /// The claim is what makes this safe: exactly one of the two tiles gets <c>true</c>, because |
| | | 66 | | /// <c>TryRemove</c> hands the stored half to a single caller. A read-then-remove would let |
| | | 67 | | /// both tiles see the other's half and both create the edge — which is the kind of race that |
| | | 68 | | /// produces a duplicated boundary edge rather than an exception. |
| | | 69 | | /// |
| | | 70 | | /// A failed <c>TryAdd</c> must retry the claim rather than give up, and that is not a |
| | | 71 | | /// refinement — it is the difference between working and silently losing edges. Both halves |
| | | 72 | | /// can arrive at once: each finds nothing to claim, then one wins the add and the other's |
| | | 73 | | /// <c>TryAdd</c> fails. Returning false there drops the losing half entirely and leaves the |
| | | 74 | | /// winner's half waiting for a partner that has already been and gone, so the boundary edge |
| | | 75 | | /// is never created. Looping turns that lost race into a claim, because the other half is |
| | | 76 | | /// necessarily present the moment the add fails. |
| | | 77 | | /// |
| | | 78 | | /// The loop terminates: a crossing has exactly two halves, so at most one add can be lost. |
| | | 79 | | /// </remarks> |
| | | 80 | | public bool TryClaimBoundaryCrossing(GlobalEdgeId globalEdgeId, |
| | | 81 | | (VertexId vertex, IEnumerable<(string key, string value)> attributes, uint edgeTypeId, |
| | | 82 | | bool isIncoming) half, |
| | | 83 | | out (VertexId vertex, IEnumerable<(string key, string value)> attributes, uint edgeTypeId, |
| | | 84 | | bool isIncoming) other) |
| | 3664 | 85 | | { |
| | 3680 | 86 | | while (true) |
| | 3680 | 87 | | { |
| | 5482 | 88 | | if (_pendingBoundaryCrossings.TryRemove(globalEdgeId, out other)) return true; |
| | 3740 | 89 | | if (_pendingBoundaryCrossings.TryAdd(globalEdgeId, half)) return false; |
| | 16 | 90 | | } |
| | 3664 | 91 | | } |
| | | 92 | | |
| | | 93 | | /// <summary> |
| | | 94 | | /// How many boundary crossings are still waiting for their other half. |
| | | 95 | | /// </summary> |
| | 55 | 96 | | public int PendingBoundaryCrossingCount => _pendingBoundaryCrossings.Count; |
| | | 97 | | |
| | | 98 | | /// <summary> |
| | | 99 | | /// Restrictions that couldn't be resolved yet because not all edges are available. |
| | | 100 | | /// </summary> |
| | 126 | 101 | | private readonly List<GlobalRestriction> _pendingRestrictions = new(); |
| | | 102 | | |
| | 126 | 103 | | private readonly object _pendingRestrictionsLock = new(); |
| | | 104 | | |
| | | 105 | | /// <summary> |
| | | 106 | | /// <see cref="_pendingRestrictions"/>.Count, readable without the lock. |
| | | 107 | | /// </summary> |
| | | 108 | | /// <remarks> |
| | | 109 | | /// Only ever read to answer "is there anything at all to do", and a stale zero is harmless: |
| | | 110 | | /// whoever adds a restriction publishes the new count after adding it, and the retry that |
| | | 111 | | /// misses it runs on the next insert instead. Restrictions are resolved eventually, not |
| | | 112 | | /// immediately, which is already how the deferred queue works. |
| | | 113 | | /// </remarks> |
| | | 114 | | private int _pendingRestrictionCount; |
| | | 115 | | |
| | | 116 | | /// <summary> |
| | | 117 | | /// Pending restrictions indexed by the ways they name. |
| | | 118 | | /// </summary> |
| | | 119 | | /// <remarks> |
| | | 120 | | /// Without this, every insert retried every pending restriction. Measured over one cold block: |
| | | 121 | | /// 7,157 retry passes examined 535,147 restrictions and resolved 2,335 — a 0.44% hit rate, with |
| | | 122 | | /// ~75 permanently unresolvable restrictions re-walked by every later insert. Cost quadratic in |
| | | 123 | | /// tiles, and it made restriction resolution ~39% of tile insertion. |
| | | 124 | | /// |
| | | 125 | | /// Keyed on the <b>way</b> (<see cref="GlobalEdgeId.EdgeId"/>), not the full edge id, because |
| | | 126 | | /// the resolver does not require the exact id a restriction names: it falls back to |
| | | 127 | | /// <c>WalkFromAnchor</c>, which tries every sub-span <c>(EdgeId, anchor, other)</c> of the same |
| | | 128 | | /// way. So the id that arrives is usually a *piece* of the way the restriction asked for, and |
| | | 129 | | /// indexing by exact id parks restrictions under keys that never arrive. Two turn-restriction |
| | | 130 | | /// tests caught exactly that. Inversion needs no special handling here — it swaps tail and head |
| | | 131 | | /// and leaves the way alone. |
| | | 132 | | /// |
| | | 133 | | /// Every way a restriction names is indexed, not just one, so it is retried whenever any of |
| | | 134 | | /// them gains an edge. A resolved restriction leaves its other entries behind; they are |
| | | 135 | | /// filtered by <see cref="_pending"/> on the way out and cleared by the next full sweep. |
| | | 136 | | /// </remarks> |
| | 126 | 137 | | private readonly Dictionary<long, List<GlobalRestriction>> _pendingByWay = new(); |
| | | 138 | | |
| | | 139 | | /// <summary> |
| | | 140 | | /// Which restrictions are still pending, so a stale index entry can be recognised. |
| | | 141 | | /// </summary> |
| | 126 | 142 | | private readonly HashSet<GlobalRestriction> _pending = new(); |
| | | 143 | | |
| | | 144 | | /// <summary> |
| | | 145 | | /// Records a restriction whose edges are not all loaded yet. |
| | | 146 | | /// </summary> |
| | | 147 | | public void AddPendingRestriction(GlobalRestriction restriction) |
| | 576 | 148 | | { |
| | 576 | 149 | | lock (_pendingRestrictionsLock) |
| | 576 | 150 | | { |
| | 576 | 151 | | _pendingRestrictions.Add(restriction); |
| | 576 | 152 | | this.ParkNoLock(restriction); |
| | 576 | 153 | | Volatile.Write(ref _pendingRestrictionCount, _pendingRestrictions.Count); |
| | 576 | 154 | | } |
| | 576 | 155 | | } |
| | | 156 | | |
| | | 157 | | /// <summary> |
| | | 158 | | /// How long a parked restriction waits, measured in inserts. |
| | | 159 | | /// </summary> |
| | | 160 | | /// <remarks> |
| | | 161 | | /// The question this answers: is parking a property of the data, or an artifact of the order |
| | | 162 | | /// tiles happen to be inserted in? A restriction at a tile boundary can only resolve once the |
| | | 163 | | /// boundary edge exists, and that edge is created by whichever of the two tiles is inserted |
| | | 164 | | /// second — so the restriction in the first one parks even though its partner arrives |
| | | 165 | | /// milliseconds later in the same batch of nine. |
| | | 166 | | /// |
| | | 167 | | /// If the waits cluster under ~9 inserts, parking is intra-batch ordering and the fix is to |
| | | 168 | | /// resolve after the batch rather than per tile. If they are long, the edges genuinely live |
| | | 169 | | /// outside the batch and the retry has to stay. |
| | | 170 | | /// </remarks> |
| | 126 | 171 | | private readonly Dictionary<GlobalRestriction, int> _parkedAt = new(); |
| | | 172 | | |
| | | 173 | | private int _insertSeq; |
| | | 174 | | |
| | | 175 | | private long _waitSum; |
| | | 176 | | |
| | | 177 | | private int _waitCount; |
| | | 178 | | |
| | | 179 | | private int _waitMax; |
| | | 180 | | |
| | | 181 | | private int _waitWithinBatch; |
| | | 182 | | |
| | | 183 | | /// Parked-restriction waits: how many inserts passed before each resolved. |
| | | 184 | | public (int count, double meanInserts, int maxInserts, int withinBatch) ParkWaits |
| | | 185 | | { |
| | | 186 | | get |
| | 0 | 187 | | { |
| | 0 | 188 | | lock (_pendingRestrictionsLock) |
| | 0 | 189 | | { |
| | 0 | 190 | | return (_waitCount, _waitCount == 0 ? 0 : _waitSum / (double)_waitCount, |
| | 0 | 191 | | _waitMax, _waitWithinBatch); |
| | | 192 | | } |
| | 0 | 193 | | } |
| | | 194 | | } |
| | | 195 | | |
| | | 196 | | /// Records how long a restriction waited. Caller holds the lock. |
| | | 197 | | private void RecordWaitNoLock(GlobalRestriction restriction) |
| | 576 | 198 | | { |
| | 576 | 199 | | if (!_parkedAt.Remove(restriction, out var parkedAt)) return; |
| | | 200 | | |
| | 576 | 201 | | var waited = _insertSeq - parkedAt; |
| | 576 | 202 | | _waitSum += waited; |
| | 576 | 203 | | _waitCount++; |
| | 674 | 204 | | if (waited > _waitMax) _waitMax = waited; |
| | | 205 | | |
| | | 206 | | // Nine is the batch: VertexTouched loads a tile plus its eight neighbours together. |
| | 1139 | 207 | | if (waited <= 9) _waitWithinBatch++; |
| | 576 | 208 | | } |
| | | 209 | | |
| | | 210 | | /// Indexes a restriction under every way it names. Caller holds the lock. |
| | | 211 | | private void ParkNoLock(GlobalRestriction restriction) |
| | 576 | 212 | | { |
| | 576 | 213 | | _pending.Add(restriction); |
| | 1152 | 214 | | if (!_parkedAt.ContainsKey(restriction)) _parkedAt[restriction] = _insertSeq; |
| | 4032 | 215 | | foreach (var edge in restriction) |
| | 1152 | 216 | | { |
| | 1152 | 217 | | if (!_pendingByWay.TryGetValue(edge.EdgeId, out var waiting)) |
| | 263 | 218 | | { |
| | 263 | 219 | | waiting = new List<GlobalRestriction>(1); |
| | 263 | 220 | | _pendingByWay[edge.EdgeId] = waiting; |
| | 263 | 221 | | } |
| | | 222 | | |
| | | 223 | | // A restriction naming the same way twice (a U-turn) would otherwise be retried |
| | | 224 | | // twice for one arrival. |
| | 1732 | 225 | | if (!waiting.Contains(restriction)) waiting.Add(restriction); |
| | 1152 | 226 | | } |
| | 576 | 227 | | } |
| | | 228 | | |
| | | 229 | | /// <summary> |
| | | 230 | | /// Inserts between full sweeps of the pending list. |
| | | 231 | | /// </summary> |
| | | 232 | | /// <remarks> |
| | | 233 | | /// The index above is the mechanism; this is the safety net for the one case it cannot see — a |
| | | 234 | | /// restriction parked under an edge that is already present, so no arrival will ever probe its |
| | | 235 | | /// key. Rare (it needs the race in <see cref="FirstMissingEdge"/>), but a restriction stuck |
| | | 236 | | /// forever is a missing turn restriction, which is a correctness bug, not a slow one. |
| | | 237 | | /// |
| | | 238 | | /// It is also what bounds how much later a restriction can resolve than it used to. Measured |
| | | 239 | | /// at 512, one cold block resolved 2,271 pending restrictions against 2,335 before — 64 were |
| | | 240 | | /// still waiting when the block ended. A server keeps inserting and would resolve them; a |
| | | 241 | | /// finite run does not, and a turn restriction that is briefly absent lets a route take a |
| | | 242 | | /// forbidden turn. At 64 the residue window is 8x smaller and the sweep still costs ~1/64 of |
| | | 243 | | /// the unconditional pass. |
| | | 244 | | /// </remarks> |
| | | 245 | | private const int SweepInterval = 64; |
| | | 246 | | |
| | | 247 | | private int _insertsSinceSweep; |
| | | 248 | | |
| | | 249 | | /// <summary> |
| | | 250 | | /// Retries the restrictions waiting for any of the edges that just became available. |
| | | 251 | | /// </summary> |
| | | 252 | | /// <param name="arrived">Global edge ids registered by the insert that just ran.</param> |
| | | 253 | | /// <param name="tryResolve">Attempts one restriction; true when it resolved.</param> |
| | | 254 | | public void RetryPendingRestrictionsFor(IReadOnlyList<GlobalEdgeId> arrived, |
| | | 255 | | Func<GlobalRestriction, bool> tryResolve) |
| | 1928 | 256 | | { |
| | | 257 | | // Same lock-free fast path as the full sweep: nothing pending, nothing to do, and this |
| | | 258 | | // runs on every insert. |
| | 1928 | 259 | | if (Volatile.Read(ref _pendingRestrictionCount) == 0) |
| | 1138 | 260 | | { |
| | | 261 | | // Still count the insert, so a sweep is not skipped forever by empty fast paths and so |
| | | 262 | | // the wait measurement is against a clock that keeps moving. |
| | 1138 | 263 | | Interlocked.Increment(ref _insertsSinceSweep); |
| | 1138 | 264 | | Interlocked.Increment(ref _insertSeq); |
| | 1138 | 265 | | return; |
| | | 266 | | } |
| | | 267 | | |
| | 790 | 268 | | Interlocked.Increment(ref _insertSeq); |
| | 790 | 269 | | var sweep = Interlocked.Increment(ref _insertsSinceSweep) >= SweepInterval; |
| | 790 | 270 | | if (sweep) |
| | 0 | 271 | | { |
| | 0 | 272 | | Volatile.Write(ref _insertsSinceSweep, 0); |
| | 0 | 273 | | this.RetryPendingRestrictions(tryResolve); |
| | 0 | 274 | | return; |
| | | 275 | | } |
| | | 276 | | |
| | 790 | 277 | | var examined = 0; |
| | 790 | 278 | | var resolved = 0; |
| | 790 | 279 | | lock (_pendingRestrictionsLock) |
| | 790 | 280 | | { |
| | 845 | 281 | | if (_pendingByWay.Count == 0) return; |
| | | 282 | | |
| | | 283 | | // Distinct ways only: a tile contributes hundreds of edges but they belong to far |
| | | 284 | | // fewer ways, and one lookup per way is the point of the index. |
| | 735 | 285 | | var ways = new HashSet<long>(); |
| | 8577 | 286 | | foreach (var edge in arrived) ways.Add(edge.EdgeId); |
| | | 287 | | |
| | 3677 | 288 | | foreach (var way in ways) |
| | 736 | 289 | | { |
| | 737 | 290 | | if (!_pendingByWay.TryGetValue(way, out var waiting)) continue; |
| | | 291 | | |
| | | 292 | | // Snapshot: tryResolve can re-park a restriction, which appends to this list. |
| | 4430 | 293 | | for (var i = waiting.Count - 1; i >= 0; i--) |
| | 1480 | 294 | | { |
| | 1480 | 295 | | var restriction = waiting[i]; |
| | | 296 | | |
| | | 297 | | // Resolved through one of its other ways already. |
| | 1480 | 298 | | if (!_pending.Contains(restriction)) |
| | 0 | 299 | | { |
| | 0 | 300 | | waiting.RemoveAt(i); |
| | 0 | 301 | | continue; |
| | | 302 | | } |
| | | 303 | | |
| | 1480 | 304 | | examined++; |
| | 2384 | 305 | | if (!tryResolve(restriction)) continue; |
| | | 306 | | |
| | 576 | 307 | | resolved++; |
| | 576 | 308 | | this.RecordWaitNoLock(restriction); |
| | 576 | 309 | | _pending.Remove(restriction); |
| | 576 | 310 | | _pendingRestrictions.Remove(restriction); |
| | 576 | 311 | | waiting.RemoveAt(i); |
| | 576 | 312 | | } |
| | | 313 | | |
| | 996 | 314 | | if (waiting.Count == 0) _pendingByWay.Remove(way); |
| | 735 | 315 | | } |
| | | 316 | | |
| | 735 | 317 | | Volatile.Write(ref _pendingRestrictionCount, _pendingRestrictions.Count); |
| | 735 | 318 | | } |
| | | 319 | | |
| | 1928 | 320 | | } |
| | | 321 | | |
| | | 322 | | /// <summary> |
| | | 323 | | /// Retries every pending restriction, dropping the ones that now resolve. |
| | | 324 | | /// </summary> |
| | | 325 | | /// <param name="tryResolve">Attempts one restriction; true when it resolved.</param> |
| | | 326 | | /// <remarks> |
| | | 327 | | /// The lock spans the whole pass because the operation is a scan-and-remove over the list, |
| | | 328 | | /// which no concurrent collection expresses: an index-based removal is only meaningful while |
| | | 329 | | /// the list cannot shift underneath it. |
| | | 330 | | /// |
| | | 331 | | /// Note what this means for the caller — <paramref name="tryResolve"/> runs while the lock is |
| | | 332 | | /// held, and it writes turn costs to arbitrary tiles. So restriction resolution serialises |
| | | 333 | | /// against itself across all concurrent inserts. That is deliberate: restrictions name edges |
| | | 334 | | /// in tiles that cannot be predicted from the tile being inserted, so they cannot be |
| | | 335 | | /// partitioned by tile the way edges can. They are also rare compared to edges. |
| | | 336 | | /// </remarks> |
| | | 337 | | public void RetryPendingRestrictions(Func<GlobalRestriction, bool> tryResolve) |
| | 0 | 338 | | { |
| | | 339 | | // Lock-free when there is nothing to retry, which is the overwhelming majority of |
| | | 340 | | // inserts. This pass runs on EVERY tile insert, so taking the lock unconditionally made |
| | | 341 | | // it a global serialisation point for all concurrent inserts — measured at 29.6% of all |
| | | 342 | | // blocked time in cold, plus another 8.7% on the add side, for a list that is almost |
| | | 343 | | // always empty. |
| | 0 | 344 | | if (Volatile.Read(ref _pendingRestrictionCount) == 0) return; |
| | | 345 | | |
| | 0 | 346 | | lock (_pendingRestrictionsLock) |
| | 0 | 347 | | { |
| | 0 | 348 | | var examined = _pendingRestrictions.Count; |
| | 0 | 349 | | var resolved = 0; |
| | 0 | 350 | | for (var i = _pendingRestrictions.Count - 1; i >= 0; i--) |
| | 0 | 351 | | { |
| | 0 | 352 | | if (tryResolve(_pendingRestrictions[i])) |
| | 0 | 353 | | { |
| | 0 | 354 | | this.RecordWaitNoLock(_pendingRestrictions[i]); |
| | 0 | 355 | | _pendingRestrictions.RemoveAt(i); |
| | 0 | 356 | | resolved++; |
| | 0 | 357 | | } |
| | 0 | 358 | | } |
| | | 359 | | |
| | | 360 | | // Rebuild the index from the survivors. The sweep resolved restrictions without |
| | | 361 | | // going through their parked keys, so every entry in there is now suspect: a |
| | | 362 | | // resolved restriction would linger, and a survivor may be waiting on a different |
| | | 363 | | // edge than when it was parked. |
| | 0 | 364 | | _pendingByWay.Clear(); |
| | 0 | 365 | | _pending.Clear(); |
| | 0 | 366 | | foreach (var restriction in _pendingRestrictions) |
| | 0 | 367 | | { |
| | 0 | 368 | | this.ParkNoLock(restriction); |
| | 0 | 369 | | } |
| | | 370 | | |
| | 0 | 371 | | Volatile.Write(ref _pendingRestrictionCount, _pendingRestrictions.Count); |
| | 0 | 372 | | } |
| | 0 | 373 | | } |
| | | 374 | | |
| | | 375 | | /// <summary> |
| | | 376 | | /// How many restrictions are still unresolved. |
| | | 377 | | /// </summary> |
| | | 378 | | public int PendingRestrictionCount |
| | | 379 | | { |
| | | 380 | | get |
| | 70 | 381 | | { |
| | 70 | 382 | | lock (_pendingRestrictionsLock) |
| | 70 | 383 | | { |
| | 70 | 384 | | return _pendingRestrictions.Count; |
| | | 385 | | } |
| | 70 | 386 | | } |
| | | 387 | | } |
| | | 388 | | } |