Github user jerrypeng commented on a diff in the pull request:
https://github.com/apache/storm/pull/2400#discussion_r148923218
--- Diff: docs/Resource_Aware_Scheduler_overview.md ---
@@ -243,58 +243,81 @@ http://dl.acm.org/citation.cfm?id=2814808
<div id='Specifying-Topology-Prioritization-Strategy'/>
### Specifying Topology Prioritization Strategy
-The order of scheduling is a pluggable interface in which a user could
define a strategy that prioritizes topologies. For a user to define his or her
own prioritization strategy, he or she needs to implement the
ISchedulingPriorityStrategy interface. A user can set the scheduling priority
strategy by setting the *Config.RESOURCE_AWARE_SCHEDULER_PRIORITY_STRATEGY* to
point to the class that implements the strategy. For instance:
+The order of scheduling and eviction is determined by a pluggable
interface in which the cluster owner can define how topologies should be
scheduled. For the owner to define his or her own prioritization strategy, she
or he needs to implement the ISchedulingPriorityStrategy interface. A user can
set the scheduling priority strategy by setting the
`DaemonConfig.RESOURCE_AWARE_SCHEDULER_PRIORITY_STRATEGY` to point to the class
that implements the strategy. For instance:
```
resource.aware.scheduler.priority.strategy:
"org.apache.storm.scheduler.resource.strategies.priority.DefaultSchedulingPriorityStrategy"
```
-A default strategy will be provided. The following explains how the
default scheduling priority strategy works.
+
+Topologies are scheduled starting at the beginning of the list returned by
this plugin. If there are not enough resources to schedule the topology others
are evicted starting at the end of the list. Eviction stops when there are no
lower priority topologies left to evict.
**DefaultSchedulingPriorityStrategy**
-The order of scheduling should be based on the distance between a userâs
current resource allocation and his or her guaranteed allocation. We should
prioritize the users who are the furthest away from their resource guarantee.
The difficulty of this problem is that a user may have multiple resource
guarantees, and another user can have another set of resource guarantees, so
how can we compare them in a fair manner? Let's use the average percentage of
resource guarantees satisfied as a method of comparison.
+In the past the order of scheduling was based on the distance between a
userâs current resource allocation and his or her guaranteed allocation.
+
+We currently use a slightly different approach. We simulate scheduling the
highest priority topology for each user and score the topology for each of the
resources using the formula
+
+```
+(Requested + Assigned - Guaranteed)/Available
+```
+
+Where
+
+ * `Requested` is the resource requested by this topology (or a
approximation of it for complex requests like shared memory)
+ * `Assigned` is the resources already assigned by the simulation.
+ * `Guaranteed` is the resource guarantee for this user
+ * `Available` is the amount of that resource currently available in the
cluster.
-For example:
+This gives a score that is negative for guaranteed requests and a score
that is positive for requests that are not within the guarantee.
-|User|Resource Guarantee|Resource Allocated|
-|----|------------------|------------------|
-|A|<10 CPU, 50GB>|<2 CPU, 40 GB>|
-|B|< 20 CPU, 25GB>|<15 CPU, 10 GB>|
+To combine different resources the maximum of all the indavidual resource
scores is used. This guarantees that if a user would go over a guarantee for a
single resource it would not be offset by being under guarantee on any other
resources.
-User Aâs average percentage satisfied of resource guarantee:
+For Example:
-(2/10+40/50)/2 = 0.5
+Assume we have to schedule the following topologies.
-User Bâs average percentage satisfied of resource guarantee:
+|ID|User|CPU|Memory|Priority|
+|---|----|---|------|-------|
+|A-1|A|100|1,000|1|
+|A-2|A|100|1,000|10|
+|B-1|B|100|1,000|1|
+|B-2|B|100|1,000|10|
-(15/20+10/25)/2 = 0.575
+The cluster as a whole has 300 CPU and 4,000 Memory.
-Thus, in this example User A has a smaller average percentage of his or
her resource guarantee satisfied than User B. Thus, User A should get priority
to be allocated more resource, i.e., schedule a topology submitted by User A.
+User A is guaranteed 100 CPU and 1,000 Memory. User B is guaranteed 200
CPU and 1,500 Memory. The scores for the most important, lowest priority
number, topologies for each user would be.
+
+```
+A-1 Score = max(CPU: (100 + 0 - 100)/300, MEM: (1,000 + 0 - 1,000)/4,000)
= 0
+B-1 Score = max(CPU: (100 + 0 - 200)/300, MEM: (1,000 + 0 - 1,500)/4,000)
= -0.125
+```
-When scheduling, RAS sorts users by the average percentage satisfied of
resource guarantee and schedule topologies from users based on that ordering
starting from the users with the lowest average percentage satisfied of
resource guarantee. When a userâs resource guarantee is completely
satisfied, the userâs average percentage satisfied of resource guarantee will
be greater than or equal to 1.
+`B-1` has the lowest score so it would be the highest priority topology to
schedule. In the next round the scores would be.
-<div id='Specifying-Eviction-Strategy'/>
-### Specifying Eviction Strategy
-The eviction strategy is used when there are not enough free resources in
the cluster to schedule new topologies. If the cluster is full, we need a
mechanism to evict topologies so that user resource guarantees can be met and
additional resource can be shared fairly among users. The strategy for evicting
topologies is also a pluggable interface in which the user can implement his or
her own topology eviction strategy. For a user to implement his or her own
eviction strategy, he or she needs to implement the IEvictionStrategy Interface
and set *Config.RESOURCE_AWARE_SCHEDULER_EVICTION_STRATEGY* to point to the
implemented strategy class. For instance:
```
- resource.aware.scheduler.eviction.strategy:
"org.apache.storm.scheduler.resource.strategies.eviction.DefaultEvictionStrategy"
+A-1 Score = max(CPU: (100 + 0 - 100)/200, MEM: (1,000 + 0 - 1,000)/3,000)
= 0
+B-2 Score = max(CPU: (100 + 100 - 200)/200, MEM: (1,000 + 1,000 -
1,500)/3,000) = 0.167
```
-A default eviction strategy is provided. The following explains how the
default topology eviction strategy works
-**DefaultEvictionStrategy**
+`A-1` has the lowest score now so it would be the next higest priority
topology to schedule.
--- End diff --
misspelling "higest"
---
