[PROPOSAL] Isolation Scheduler Can Have Free Slots Check as a Secondary Sorting Check

[meetjain74]

The issue is a follow up to issue #8704 @rzo1

Currently, the isolation scheduler sorts the machines in decreasing order of assignable slots (total slots available). As the condition written in code is:

// returns list of list of slots, reverse sorted by number of slots
private LinkedList<HostAssignableSlots> hostAssignableSlots(Cluster cluster) {
    List<WorkerSlot> assignableSlots = cluster.getAssignableSlots(); // getAssignableSlots here -> primary sort

    // .....

    // Sort Assignable slots by reverse number of slots
    List<HostAssignableSlots> sortHostAssignSlots = new ArrayList<HostAssignableSlots>();
    for (Map.Entry<String, List<WorkerSlot>> entry : hostAssignableSlots.entrySet()) {
        sortHostAssignSlots.add(new HostAssignableSlots(entry.getKey(), entry.getValue()));
    }
    Collections.sort(sortHostAssignSlots, new Comparator<HostAssignableSlots>() {
        @Override
        public int compare(HostAssignableSlots o1, HostAssignableSlots o2) {
            return o2.getWorkerSlots().size() - o1.getWorkerSlots().size();
        }
    });

    return new LinkedList<HostAssignableSlots>(sortHostAssignSlots);
}

Why was the design choice taken to use getAssignableSlots instead of getAvailableSlots which takes number of free slots in consideration? If we sort by getAvailableSlots, we would choose machines with more number of free slots and have the less number of evictions.

My idea is that we can have a secondary sort where we check getAvailableSlots post getAssignableSlots in IsolationScheduler?

[rzo1]

I cannot tell anything about design choices. You would need to either search in the dev list archive or in the git history for an explanation ;-)

[meetjain74]

I can see this in the first commit for IsolationScheduler d44970a by Nathan Marz on Dec 20, 2012, getAssignableSlots is used in host-assignable-slots

;; returns list of list of slots, reverse sorted by number of slots
(defn- host-assignable-slots [^Cluster cluster]
  (-<> cluster
       .getAssignableSlots
       (group-by #(.getHost cluster (.getNodeId ^WorkerSlot %)) <>)
       (dissoc <> nil)
       (sort-by #(-> % second count -) <>)
       (LinkedList. <>)
       ))

The only valid explanation that seems to me is this:

getAssignableSlots is intentional because the IsolationScheduler is an eviction-by-design scheduler. When it picks a host for an isolated topology, the very next thing it does is forcibly free every used slot on that host. So "currently free slots" is not a feasibility constraint — what matters is the total non-blacklisted capacity of the host.

In IsolationScheduler.schedule(...), after the first pass marks "already correctly-isolated" hosts as blacklisted, it picks a host and then evicts everything on it before assigning isolated workers:

if (slot != null && slot.size() >= num) {
    hss.poll();
    cluster.freeSlots(hostUsedSlots.get(hostSlots.getHostName()));
    for (WorkerSlot tmpSlot : slot.subList(0, num)) {
        Set<ExecutorDetails> executor = removeElemFromExecutorsSet(executorSet);
        cluster.assign(tmpSlot, topologyId, executor);
    }
    cluster.blacklistHost(hostSlots.getHostName());
}

That cluster.freeSlots(hostUsedSlots.get(...)) call is the key: any non-isolated worker on the chosen host is killed to make room. Once we know that's the policy, sorting by currently free slots would actually be misleading — we'd skip a 16-slot host with 2 non-isolated workers in favor of a sparse 8-slot host, even though the 16-slot host is the strictly better placement for an isolated topology that needs 10 workers.

The sort maximizes a single iso-topology landing on as few large machines as possible (which is the whole point of the isolation distribution computed in machineDistribution).

But I am still in favor of adding a secondary check on basis of getAvailableSlots so as to have less number of evictions on machines with same number of slots.
Adding getAvailableSlots as a secondary key would deterministically prefer hosts that need fewer evictions, without changing the isolation contract — large hosts still win primarily, we just break ties in favor of less disruption.

[meetjain74]

I have raised a PR corresponding to the same #8709
Can you please check this.

cc: @nathanmarz