6 ms·
I enjoyed the callout to this when I was reading Google's Percolator paper a few years ago: > The random-scanning approach requires one additional tweak: when
by brian_cloutier 8y ago
I enjoyed the callout to this when I was reading Google's Percolator paper a few years ago:
> The random-scanning approach requires one additional tweak: when it was first deployed we noticed that scanning threads would tend to clump together in a few regions of the table, effectively reducing the parallelism of the scan. This phenomenon is commonly seen in public transportation systems where it is known as “platooning” or “bus clumping” and occurs when a bus is slowed down (perhaps by traffic or slow loading). Since the number of passengers at each stop grows with time, loading delays become even worse, further slowing the bus. Simultaneously, any bus behind the slow bus speeds up as it needs to load fewer passengers at each stop. The result is a clump of buses arriving simultaneously at a stop [19]. Our scanning threads behaved analogously: a thread that was running observers slowed down while threads “behind” it quickly skipped past the now-clean rows to clump with the lead thread and failed to pass the lead thread because the clump of threads overloaded tablet servers. To solve this problem, we modified our system in a way that public transportation systems cannot: when a scanning thread discovers that it is scanning the same row as another thread, it chooses a new random location in the table to scan. To further the transportation analogy, the buses (scanner threads) in our city avoid clumping by teleporting themselves to a random stop (location in the table) if they get too close to the bus in front of them.
From here: https://ai.google/research/pubs/pub36726 https://ai.google/research/pubs/pub36726
- phinnaeus 8y agoTL;DR - Teleportation will solve public transit problems.
- Aeolun 8y agoExcept for all those poor people that are still in the bus when it teleports :P
- gpderetta 8y agothen again, if you have teleportation, you probably do not need the bus in the first place (did I just explain the joke?).
- m463 8y agoif teleportation is impractical you could just use a faster bus, like USB 3.0 or more lanes like PCIe
- angel_j 8y agoeverybody gets on/off at the same time instead of one by one (every seat has it's own door?)
- Skye 8y agoOn old British rail trains, commuter trains had many doors, I think on each side there was a door for each pair of row of seats? There was also no door lock, so people could start leaving the train before it fully stopped. The lack of a door lock is also why they're not used anymore.
- zhte415 8y ago> To further the transportation analogy, the buses (scanner threads) in our city avoid clumping by teleporting themselves to a random stop (location in the table) if they get too close to the bus in front of them. Subway trains do this "to regulate service" iirc is the term used on the London Underground. Takt time［1］and Drum Buffer Rope［2］both related concepts of regulating flow through a process/system. ［1］ https://en.m.wikipedia.org/wiki/Takt_time https://en.m.wikipedia.org/wiki/Takt_time ［2］ https://en.m.wikipedia.org/wiki/Theory_of_constraints https://en.m.wikipedia.org/wiki/Theory_of_constraints
- icebraining 8y agoLondon subway trains teleport themselves?
- joncrocks 8y agoNo they don't. When you hear "to regulate the service" what they actually do in my experience is delay trains to try and introduce a more even service. So if you have trains that are: |--|--|--|------------|--| Then they will delay some of the trains such that it becomes: ---|--|--|--|--------|----| i.e. reduce the speed of the lead trains to try and reduce bunching. So generally if you hear "to regulate the service" it means you're in for a longer journey than normal. I believe there are passing points along the tracks, I don't think they can be used to leapfrog, and there's no such thing as "express" services.
- falsedan 8y agoLothian buses regulate as well, but only to maintain published timetables (if a bus is running fast, it will sit at a stop until it's back on schedule) The usual clumping is multiple buses on separate routes arriving at one, since they enforce strict stacking (can disembark in the approach to the stop but can only embark passengers at the stop sign)
- Mvandenbergh 8y agoThere are express services but only on the metropolitan line (which uses above ground tracks shared with non-TFL trains).
- dominotw 8y agoThis is possible with public transportation too. Trains run express and skip stops all the time. I think that would be too much hassle with buses but it's possible.
- jpatokal 8y agoI have seen full or near-full buses skip scheduled stops to alleviate this. Although from a waiting passenger's POV, having an already delayed bus that has space left zoom past you without stopping is pretty infuriating...!
- btbuildem 8y agoPerhaps the bus that caught up to the full bus should pass it, and relieve the next stop - presumably there are extra passengers waiting at that one too, since the bus is late. This way the bus that caught up will now risk slowing down (dealing with fuller stops), but the original full bus that was slow is likely to not speed up that much, having an above-average number of potentially disembarking passengers.
- Izkata 8y agoThis is what CTA buses in Chicago do, though the full bus doesn't slow down. They end up leapfrogging down the route.
- mjevans 8y agoYeah, the correct customer service solution is to have the full bus HOLD at a stop and let the emptier bus leave first (and stay ahead).
- adrianN 8y agoThat delays all people who are already on the delayed bus even more.
- 8y ago
- Tarean 8y agoThis also happened with routing messages - they are periodic and start at random offsets but they bunch up without added randomness https://ee.lbl.gov/papers/sync_94.pdf https://ee.lbl.gov/papers/sync_94.pdf