apache/spark — pull request #7 by CodingCat (2014-02-26 23:45:36+00:00)
Title: [SPARK-979] a LRU scheduler for load balancing in TaskSchedulerImpl

this PR is for SPARK-979(https://spark-project.atlassian.net/browse/SPARK-979), where @rxin pointed out that the Spark Scheduler is very deterministic.

the main changes include

Add a LRUMap in util package (based on org.apache.commons.collections.map.LRUMap , its implementation is pretty neat, it implements LRU with a double linked list, and it does not need to really move data, but just changes the pointers)

remove freeCores in CoarseGrainedSchedulerBackend.scala and save WorkerOffer in a LRUMap/HashMap(Configurable) to avoid new operation everytime

change the implementation of resourceOffers in TaskSchedulerImpl. Now it takes a Map as input and balances the load with LRU principle (LRU scheduling is configurable, if user does not want this feature (by default), then we will pass a HashMap to resourceOffers, otherwise, we will pass a LRUMap)

For clarification, in the code, I give an initial size 1000 to LRUMap, which will not impose the limitation on the max number of executors each application can use. I double checked the implementation of commons.collections, it turns out that when the map is full, the implementation will automatically double-size the original map until there are 1<<30 elements (in practice, we will not have so many executors to use)