3 ms·

http://research.google.com/pubs/pub41684.html http://research.google.com/pubs/pub41684.html Basically, there's a server that holds state for the cluster. When

http://research.google.com/pubs/pub41684.html http://research.google.com/pubs/pub41684.html Basically, there's a server that holds state for the cluster. When a scheduler attempts to load a job into the cluster, it grabs state from the aforementioned server, performs its job placement calculations, and then tries to submit its answer to the master state. Since there are many such schedulers, and the amount of time it takes to place a job is non-trivial, its possible that during the processing time to calculate placement, another scheduler might've consumed the requested resources. In this case, the first scheduler will provision whichever services are not in conflict for placement location, and perform a new calculation with the new state to place the remaining conflicted servers. The general idea is that most services don't have such a high affinity that the components need to be started all at the same time (a MapReduce job on 10,000 nodes can still run with 5,000 nodes while the second 5k are provisioning). The tradeoff here is that you have to manage conflicts, but the hope is that there are few enough that your optimism is rewarded. Does that make sense?

derefr 11y ago
Sounds more like "greedy" than "optimistic" scheduling: the early jobs get the worms. In most scheduling systems, two 10,000-node jobs that each would saturate a cluster on their own will time-share if submitted together, with each job acting in practice more like 10,000 single-node jobs. The result is usually each job getting a probabilistic 50% share of the cluster while they're both running, and then whichever one runs longer saturating the cluster once the other ends. This scheduling system, meanwhile, would seem to just hand the 10,000 nodes over to job A, and then sleep job B until job A is done. Admittedly, in the case where the jobs aren't submitted at the same time, and job A has already grabbed and saturated the cluster, the two cases collapse together: job B must wait (unless you want to schedule processes rather than containers; then you just degrade the cluster's performance.) But for batch-processing applications, you'd usually schedule everything to start at once, precisely so that the scheduler could interleave the jobs.
- josh2600 11y ago
  This job swapping problem is a different sort of problem. In your example, I have cluster saturation as a concern. Google would love to saturate their cluster, but I would wager they usually are nowhere near saturation (scheduling a job on Borg takes something like 90 seconds at minimum; there's a lot of ground to cover). The innovation in optimistic schedulers is that you can have multiple schedulers running against a master state. This is in contrast to a single scheduler, single state system like Mesos (forgive me if I've misspoken about Mesos, but this is how I remember it).
  - krenoten 11y ago
    Mesos is a two-level scheduler, where the elected master is more of a broker for offers from agents to external schedulers that decide to act on the offer or not. By default it's pessimistic, but this is pluggable and there's no reason you can't write an optimistic allocator module that will hand out offers to multiple schedulers.
    - josh2600 11y ago
      Part of the beauty of Omega is that there aren't just multiple schedulers, but schedulers with different profiles (this solves the head of line problem for long-running jobs while accelerating small jobs). Mesos, from the Borg paper[0], seems to have issues with head of line problems (including going so far as to silently fail jobs without queueing them). FWIW, Omega seems like the answer if the overhead for resolving inconsistencies becomes low enough such that the benefits of optimistic scheduling outweigh the costs. [0]http://www.slideshare.net/sameertiwari33/scheduling-on-large-clusters http://www.slideshare.net/sameertiwari33/scheduling-on-large... See slide 6.
      - krenoten 11y ago
        That link isn't working for me, unfortunately. I'm assuming that the HOL you're referring to stems from the assumption of the default DRF allocator of fast decisions, which can cause issues for mixed workloads if there's a lot of hoarding happening. This is something that could be addressed with an allocator module, but nobody has yet to my knowledge, leading me to think it's not a massive problem for many people. I think the people who care about this use case end up running multiple mesos clusters. One note on priorities a la Borg (what I think people are actually using at Google today, but I don't know to what extent Omega was merged with it after the Omega paper or if Borg currently runs as an Omega scheduler or what), is that it sometimes causes annoyance for people at Google, as the optimal priority is not always assigned to certain workloads, leading to starvation or overpreemption of things that were not given a healthy number. I believe that Mesos' work on oversubscription took concerns around this issue into consideration. It's really fascinating to compare the architecture of Nomad vs K8s, because both claim heavy descendence from Omega + Borg. If I squint, it seems like Nomad is more of a direct implementation based on those papers. K8s more explicitly modularizes more components, which I think is why a lot of companies are jumping behind it, as they can mold it in the ways they want.

derefr 11y ago

Sounds more like "greedy" than "optimistic" scheduling: the early jobs get the worms. In most scheduling systems, two 10,000-node jobs that each would saturate a cluster on their own will time-share if submitted together, with each job acting in practice more like 10,000 single-node jobs. The result is usually each job getting a probabilistic 50% share of the cluster while they're both running, and then whichever one runs longer saturating the cluster once the other ends. This scheduling system, meanwhile, would seem to just hand the 10,000 nodes over to job A, and then sleep job B until job A is done. Admittedly, in the case where the jobs aren't submitted at the same time, and job A has already grabbed and saturated the cluster, the two cases collapse together: job B must wait (unless you want to schedule processes rather than containers; then you just degrade the cluster's performance.) But for batch-processing applications, you'd usually schedule everything to start at once, precisely so that the scheduler could interleave the jobs.

josh2600 11y ago
This job swapping problem is a different sort of problem. In your example, I have cluster saturation as a concern. Google would love to saturate their cluster, but I would wager they usually are nowhere near saturation (scheduling a job on Borg takes something like 90 seconds at minimum; there's a lot of ground to cover). The innovation in optimistic schedulers is that you can have multiple schedulers running against a master state. This is in contrast to a single scheduler, single state system like Mesos (forgive me if I've misspoken about Mesos, but this is how I remember it).
- krenoten 11y ago
  Mesos is a two-level scheduler, where the elected master is more of a broker for offers from agents to external schedulers that decide to act on the offer or not. By default it's pessimistic, but this is pluggable and there's no reason you can't write an optimistic allocator module that will hand out offers to multiple schedulers.
  - josh2600 11y ago
    Part of the beauty of Omega is that there aren't just multiple schedulers, but schedulers with different profiles (this solves the head of line problem for long-running jobs while accelerating small jobs). Mesos, from the Borg paper[0], seems to have issues with head of line problems (including going so far as to silently fail jobs without queueing them). FWIW, Omega seems like the answer if the overhead for resolving inconsistencies becomes low enough such that the benefits of optimistic scheduling outweigh the costs. [0]http://www.slideshare.net/sameertiwari33/scheduling-on-large-clusters http://www.slideshare.net/sameertiwari33/scheduling-on-large... See slide 6.
    - krenoten 11y ago
      That link isn't working for me, unfortunately. I'm assuming that the HOL you're referring to stems from the assumption of the default DRF allocator of fast decisions, which can cause issues for mixed workloads if there's a lot of hoarding happening. This is something that could be addressed with an allocator module, but nobody has yet to my knowledge, leading me to think it's not a massive problem for many people. I think the people who care about this use case end up running multiple mesos clusters. One note on priorities a la Borg (what I think people are actually using at Google today, but I don't know to what extent Omega was merged with it after the Omega paper or if Borg currently runs as an Omega scheduler or what), is that it sometimes causes annoyance for people at Google, as the optimal priority is not always assigned to certain workloads, leading to starvation or overpreemption of things that were not given a healthy number. I believe that Mesos' work on oversubscription took concerns around this issue into consideration. It's really fascinating to compare the architecture of Nomad vs K8s, because both claim heavy descendence from Omega + Borg. If I squint, it seems like Nomad is more of a direct implementation based on those papers. K8s more explicitly modularizes more components, which I think is why a lot of companies are jumping behind it, as they can mold it in the ways they want.