To further clarify, the dependency, ideally, should not be on the implementation but rather on some kind of interface exposed by the shuffle service.
That's exactly my point. It should not depend on a specific implementation class but rather an SPI that both the app and the shuffle implementation depend on. In this case, the SPI is the service id at the moment. If you rename the ShuffleHandler to ShuffleHandlerImpl the code would look wrong too.
Now you have a runtime classpath dependency on a specific shuffle implementation for mr app. If you replace the jar with a different class and update the config, the NM will happily load the service but the mr app won't even run due to class not found exception.