понедельник, 15 ноября 2021 г.

Non-formal overview of Token Bucket rate-limiting algorithm

What is the motivation to write this article about the Token Bucket algorithm?

I am the author of Bucket4j rate-limiting library, and too often I deal with fact that users want to use my library, but do not want to learn the foundations of the token-bucket algorithm and math model. 

So, to make my users to be motivated to learn about Token-Bucket I decided to write this article in a non-traditional style. Instead of being focusing on math and algorithms, this article step-by-step describes the problems that you can be faced with when implementing a rate-limiting algorithm by yourself from scratch. 

I hope that when users found from how many problems Token Bucket protects, they will become more motivated to follow and learn this Wikipedia link

Simple rate-limiter implementation

Let's implement a simple algorithm for limitation defined in terms N events per M rolling time window.
import java.util.LinkedList;

/**
* The naive solution for rate limiter which potentially leads to crash JVM with out-of memory error.
*/
public class NoneEffectiveRateLimiter {

private long availableTokens;
private final long periodMillis;

private LinkedList<Issue> issuedTokens = new LinkedList<>();

/**
* Creates instance of rate limiter which provides guarantee that consumption rate will be >= tokens/periodMillis
*/
public NoneEffectiveRateLimiter(long tokens, long periodMillis) {
this.availableTokens = tokens;
this.periodMillis = periodMillis;
}

synchronized public boolean tryConsume(int numberTokens) {
long nowMillis = System.currentTimeMillis();
clearObsoleteIssues(nowMillis);

if (availableTokens < numberTokens) {
// has no requested tokens in the bucket
return false;
} else {
issuedTokens.addLast(new Issue(numberTokens, nowMillis));
availableTokens -= numberTokens;
return true;
}
}

private void clearObsoleteIssues(long nowMillis) {
while (!issuedTokens.isEmpty()) {
Issue issue = issuedTokens.getFirst();
if (nowMillis - issue.timestampMillis > periodMillis) {
availableTokens += issue.tokens;
issuedTokens.removeFirst();
} else {
return;
}
}
}

private static final class Issue {
private final long tokens;
private final long timestampMillis;

private Issue(long tokens, long timestampMillis) {
this.tokens = tokens;
this.timestampMillis = timestampMillis;
}
}

private static final class SelfTest {

public static void main(String[] args) {
// 100 tokens per 1 second
NoneEffectiveRateLimiter limiter = new NoneEffectiveRateLimiter(100, 1000);

long startMillis = System.currentTimeMillis();
long consumed = 0;
while (System.currentTimeMillis() - startMillis < 10000) {
if (limiter.tryConsume(1)) {
consumed++;
}
}
System.out.println(consumed);
}

}

}
What are the problems with this naive implementation?
The solution above consumes memory in a non-effective way, in order to control the rate, it stores each particular fact about issued tokens at least for ```periodMillis```.
And this behavior can lead to the following problems:
  • JVM can crash with out of memory error in case of rate of events to high or the period is too large.
  • If JVM can survive, the problem of unnecessary promotion from young to tenured memory regions still exists.
Imagine that minor garbage collections happen every 5 seconds, and you have to deal with 1 minute period of the limiter. It is obvious that memory for each issued permit is primarily allocated to a new generation and then will be promoted to the tenured generation because the time to live of the permit is enough to survive several collections in the new generation. Hence this naive implementation will lead to more frequent Full GC pauses.

Attempt to optimize memory consumption

Ok, the previous attempt failed, but I can optimize memory consumption by refilling available tokens in the background thread instead of storing each fact about consumption.

Let's do it:
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

/**
* The ineffective solution for rate limiter which wast CPU to refill tokens in background executor
*/
public class SchedulerBasedTokenBucket {

private final long maxTokens;
private long availableTokens;

/**
* Creates instance of rate limiter which provides guarantee that consumption rate will be >= tokens/periodMillis
*/
public SchedulerBasedTokenBucket(long tokens, long periodMillis, ScheduledExecutorService scheduler) {
long millisToRefillOneToken = periodMillis / tokens;
scheduler.scheduleAtFixedRate(this::addToken, periodMillis, millisToRefillOneToken, TimeUnit.MILLISECONDS);

this.maxTokens = tokens;
this.availableTokens = tokens;
}

synchronized private void addToken() {
availableTokens = Math.min(maxTokens, availableTokens + 1);
}

synchronized public boolean tryConsume(int numberTokens) {
if (availableTokens < numberTokens) {
return false;
} else {
availableTokens -= numberTokens;
return true;
}
}

private static final class SelfTest {

public static void main(String[] args) {
// 100 tokens per 1 second
ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);
SchedulerBasedTokenBucket limiter = new SchedulerBasedTokenBucket(100, 1000, scheduler);

long startMillis = System.currentTimeMillis();
long consumed = 0;
while (System.currentTimeMillis() - startMillis < 10000) {
if (limiter.tryConsume(1)) {
consumed++;
}
}
scheduler.shutdown();
System.out.println(consumed);
}

}

}
What are the problems? This implementation is not self-sufficient because requires ScheduledExecutorService, and this leads to the following disadvantages:
  • Requires at least one background thread.
  • CPU can be heavily consumed in case of multiple limiters or high granular refill. For example, a limit rate of 100 events per 1 second, requires 100 executions per second inside scheduler, for a case with 100 independent limiters it needs to 10000 executions per second.
  • CPU is used for scheduling background tasks even if the limiter was unused for a long time.
  • Requires tricky management of memory and tasks: it is needed to cancel tasks in the scheduler when the limiter is not needed anymore, also references(task in scheduler holds a strong reference to limiter which makes limiter reachable).

So, what kinds of problems can be solved by the token bucket?

Token bucket algorithm solves rate-limiting problems in the way:
  • Which requires a small and predefined amount of memory, independently of the incoming request rate the memory consumed by token-bucket is always constant.
  • There are no additional background threads required by token-bucket.

Example of Token-bucket algorithm implementation

The formal description of Token Bucket can be found in this Wikipedia article. I do not want to copy this article there, but I have a major note: pay attention that wikipedia's article just describes a formal model of token-bucket, it is not the algorithm by itself. Concrete implementations of token-bucket can significantly differ from each other by details, but any implementation which called itself a "token-bucket" must produce results in a way that can be checked by this model.

Example of a pretty basic java token-bucket implementation:
/**
* The minimalistic token-bucket implementation
*/
public class MinimalisticTokenBucket {

private final long capacity;
private final double refillTokensPerOneMillis;

private double availableTokens;
private long lastRefillTimestamp;

/**
* Creates token-bucket with specified capacity and refill rate equals to refillTokens/refillPeriodMillis
*/
public MinimalisticTokenBucket(long capacity, long refillTokens, long refillPeriodMillis) {
this.capacity = capacity;
this.refillTokensPerOneMillis = (double) refillTokens / (double) refillPeriodMillis;

this.availableTokens = capacity;
this.lastRefillTimestamp = System.currentTimeMillis();
}

synchronized public boolean tryConsume(int numberTokens) {
refill();
if (availableTokens < numberTokens) {
return false;
} else {
availableTokens -= numberTokens;
return true;
}
}

private void refill() {
long currentTimeMillis = System.currentTimeMillis();
if (currentTimeMillis > lastRefillTimestamp) {
long millisSinceLastRefill = currentTimeMillis - lastRefillTimestamp;
double refill = millisSinceLastRefill * refillTokensPerOneMillis;
this.availableTokens = Math.min(capacity, availableTokens + refill);
this.lastRefillTimestamp = currentTimeMillis;
}
}

private static final class SelfTest {

public static void main(String[] args) {
// 100 tokens per 1 second
MinimalisticTokenBucket limiter = new MinimalisticTokenBucket(100, 100, 1000);

long startMillis = System.currentTimeMillis();
long consumed = 0;
while (System.currentTimeMillis() - startMillis < 10000) {
if (limiter.tryConsume(1)) {
consumed++;
}
}
System.out.println(consumed);
}

}

}
The MinimalisticTokenBucket is just a learning example that helps to understand how to implement token-bucket quickly, please do not make assumptions about how to Bucket4j internally works by looking at the code above.


Thank you for reading.

воскресенье, 17 апреля 2016 г.

Jar Helsing - боремся с jar hell в springframework

О чем здесь?

Это статья о моей библиотеке Spring-Jar-Helsing, которую я создал в качестве легковесного средства, которое иногда полезно применить для того, чтобы побороть проблему Jar Hell в приложениях на базе Spring Framework

Суть проблемы

Современное программное обеспечение никогда не создаётся полностью с нуля. С целью экономии времени и денег на разработку, программы строятся из уже готовых библиотек. В наши дни, когда опенсурс движение набрало огромные обороты, и практически в каждой области можно найти готовую бесплатную библиотеку, следовать такому подходу проще простого, заиспользовать готовое и бесплатное ничего не стоит. Вопрос с разбуханием дистрибудива от большого количесва зависимостей, для серверных приложений в отличии от мобильных тоже не стоит, на сервере у нас всегда много места на диске. Таким образом даже небольшой микросервис на java состоит из десятков библиотек, а счёт библиотек в кровавомтиповом ынтерпрайз приложении идёт на сотни.

Однако медаль имеет и обратную сторону. Не только разработчики конечных продуктов любят переиспользовать готовые решения, часто разработчики библиотек тоже так делают, в итоге мы получаем библиотеки, которые зависят от других библиотек, а это уже при определенных условиях может серьезно усложнить нам жизнь. Например, если наше приложение зависит от библиотек A и B,  а те в свою очередь зависят от библиотеки C, но при этом A требует свою версию C, а B свою, иначе либо A либо B не работает, то мы можем столкнуться с проблемой которую в Java принято называть Jar hell. Собственно проблема относится не только к языку Java, по своей сути она глобальна и имеет обобщенное название Dependency Hell.

Попытаться решить проблему Dependency Hell нужно следующими способами:

  1. Попытаться найти такие версии A и B подхядище вашему приложению, которые зависили бы в идеальном случае от одной версии С, либо от версии C которая бинарно совместима с A и B.  В java как на уровне платформы, так и на уровне библитек лишний раз обратную совместимость стараются не ломать, так что вооружившись гуглом и терпением, можно пожанглировать с версиями и прийти к успеху.
  2. Если  общего знаменателя найти не удается, то можно пропатчить либо A, либо B, либо C и устранить несовместимость своими собственными руками. Этот путь может Вам иногда не подойти, либо по соображением трудоемкости создания форка, либо банально по соображениям лицензионной политики, иногда хотелось бы чонить форкнуть, да проприетарная лицензия не позволяет. 
  3. И так мы дошли до пункта 3 и мы в жопе - продукт выпускать надо, а значит нужно какое-то средсво которое позволило бы в одном приложении иметь сразу две версии библиотеки C. Тут для Вас как Spring разработчика на сцену выходит либо тяжелая артилерия в виде OSGI, обещающего решить большинство проблем с classpath, либо самодельные хаки с класслоадерами, которые в определенных юзкейсах внедрить намного быстрее и проще чем OSGI, и это не потребует зависимости от тяжлого OSGI контейнера. Spring-Jar-Helsing по сути является легковесной альтернативой OSGI, которую можно применять в ограниченных случаях, которые описанны далее.

Жизненные примеры использования Spring Jar Helsing

Использовать Jar Helsing в своей практике мне приходилось в двух случаях. Первый раз когда, он ещё не представлял из себя отдельную библиотеку. Работал я на госзаказе, попиливали мы баблишко создавая интеграционные приложения под Mule ESB которая плоть от крови базируется на springframework. Поскольку дело было в госсекторе, то приходилось иметь дело с особо извращенными крипто-алгоритмами естественно уже дадеными свыше в виде готовых библиотек обязательных к использованию под страхом смертной казни, и получилось так что Mule использовал библиотеку apache-codec(зачем-то форкнутую под нужды Mule), и библиотека для работы с цифровыми подписями, которую согласно ТЗ мы должны были использовать тоже внутри себя шла со своим форком apache-codec, и получалсь так, что эти форки apache-codec оказались несовместимыми и не работала либо базовая функциональность Mule, либо библиотека для создания криптоподписей. Не Mule, не криптобиблиотеку из-за политических ограничений патчить не было никакой возможности, поэтому проблему я решил грязным хаком. Вынес в отдельный артефакт в который выделил API для работы с цифровыми подписями, а реализацию по интеграции с криптобиблиотекой вынес в отдельный модуль, так чтобы основная часть приложения зависела от API но не зависела от реализации. Джарник реализации подгружал собственно ручно написанным класслоадером который работал таким образом чтобы при резолвинге классов для криптобиблиотеки классы для apache-codec брались из специального места которое не входило в основной classpath приложения. Когда нужно было поставть куданить подпись, приложение делало это через API даже не подозревая, что реализация работает по сути на отдельном classpath.

Когда столкнулся с аналогичной проблемой втрой раз, я решил оформить свои костыли с класслоадерами в повторно используемую библиотеку. Случилось это при использовании системы нагрузочного тестирования Jagger, которая тоже вся на спринге, и нагрузочные сценарии к ней пишутся в виде обычных спринговых бинов. Jagger очень многое делает для разработчика, и равномерно распределяет нагрузку по кластеру нагрузчиков, и собирает релультаты с кластера нагрузчиков, агрегирует их и сохраяет в базу, и отчеты генерит, и вебморда есть для просмотра результатов сессий, короче классная штука, за исключением того что у него самого около сотни библиотек в зависимостях, а такую важную вещь как загрузку пользовательских сценариев в отдельном класслоадере разработчики не предусмотрели. В итоге случилось так, что Jagger использует guava древней версии, а тестить мне нужно было, сервак который предоставляет thrift интерфейс и клиентское SDK для работы через thrift, и этот SDK тоже зависил от guava но самой свежей. Эти редискиразработчики guava ломают обратную совместимость в guava как нефиг делать. Поскольку разбег между версиями guava составлял 6 мажорных версий, то не удивительно что я столкнулся с множественными несовместимостями, когда методы удалены, переименованны или перемещенны, классы перемещены или удаленны. Тут конечно я имел пространство для маневра, я мог и патчить Jagger, и отказаться от использования SDK перейдя на работу напрямую с thrift, можно было и написать свою обертку без Guava, можно было собрать свою guava совместимую и с Jagger и с SDK, но я счел это нерациональным, в виду того что повторение хака с класслоадерами у меня заняло меньше времени. Точно тем же способом я загрузил бины своих нагрузчиков отдельным класслоадером и закрыл проблему.

Ключевые информация про Spring Jar Helsing

Я называю Spring-Jar-Helsing легковесным, потому что он не такой монструозный как OSGI состоит из всего двух классов, ресурсов никаких не жрёт, и внедрить его в приложение можно достаточно быстро и не надо читать килотонны документации и натаптывать киллометры конфигурационных файлов. Для того, чтобы начать работать достаточно прочитать README проекта на github и посмотреть пример использования там же на github.

Разберем все классы по косточкам:
  • JarHelsingClassLoader - утилитарный класс отвечающий за загрузку классов из кастомных путей не входящих в основной classpath приложения. Его реализация работает немного не так как написанно в рекомендациях из джавадоков по реализации класслоадеров, а именно при необходимости загрузить класс, он сначала смотрит в свой кастомный список ресурсов, и лишь в случае если класс не найден он делегирует загрузку родительском класслоадеру, но именно это и нужно, иначе мы бы не получили возможность иметь одну версию библиотеки классы коорой загруженны родительским класслоадером, и другую версию классы которой загруженны нашим класслоадером. JarHelsingClassLoader очень тонкий класс, всю тяжелую работу он делегирует классу URLClassLoader из JDK от которого он наследуется. Наследование от URLClassLoader позволяет из коробки получить множество способов задать кастомный класспаз, через файловые пути, ссылки на сетевые ресурсы, jar архивы внутри других jar архивов, короче всё на что может быть описанно как URL можно смело использовать при составлении кастомного classpath. Возможность ссылаться на Jar внутри Jar это очень удобная штука, классы находящиеся в Jar внутри другого Jar никогда не попадают в основной classpath, а вот сослаться на такой jar очень просто, так как java поддерживает такие URL на ресурсы внутри JAR из коробки, а засунуть при сборки приложения один JAR в другой не должно составлять больших трудностей для благородного дона.
  • JarHelsingBeanFactoryPostProcessor - это главная часть. Будучи объявленной в каком-нибудь спринговом контексте, он создает новый контекст, бины которого могут иметь свой отдельный classpath, а затем экспортирует все синглтоны из созданного контекста в главный с сохранением имён, из главного конекста можно ссылаться потом на такие бины по имени. При объявлении нужно задать два апарметра список XML файлов в которых сконфигурированны бины вспомогательного контекста и пути составляющие кастомный classpath. Объявление корневой точки вспомогательного контекста поддерживается из коробки только для XML, ежели он вам постыл то можно внутри XML настроить уже как надо DI на аннотациях и прочие упростяшки.  Пример объявления JarHelsingBeanFactoryPostProcessor
<bean class="com.github.springjarhelsing.JarHelsingBeanFactoryPostProcessor">
        <property name="resourceLocations">
            <list>
                <value>classpath:context-for-beans-with-custom-classpath.xml</value>
            </list>
        </property>
        <property name="overridenClasspathUrls">
            <list>
                <value>file:/opt/mycompany/libs/something-lib.jar</value> <!-- Points to file -->
                <value>http:mycomapny.com/java-libs/yet-another-library.jar</value> <!-- Points to file in internet -->
                <value>classpath:custom-libs/killer-library-6.6.6.jar</value> <!-- Points to file accessible as resource. Pay double attention that this file should not be by itself a valid source for parent classloader which can be used by parent classloader to class resolution -->
            </list>
        </property>
    </bean>

Если что то еще остается не ясным как начать использовать Spring Jar Helsing, то обратитесь к примеру, в рамках которого продемонстированно как внутри одного spring приложения использовать две разных версии guava.

Область эффективного применения и ограничения

  • Первый случай, когда  очевидно Spring-Jar-Helsing вам не нужен как средсво борьбы с Jar Hell, это когда ваше приложение уже работает на чем-то тяжеловесном вроде OSGI или полноценном JEE сервере с поддержкой EAR архивов. Поскольку там проблемы поиметь отдельный classpath для чего-то решены на высшем уровне, то тащить Jar Helsing нет смысла, просто правильно разбейте приложение на модули.
  • Так же, увы Jar Helsing ничем не поможет, если у Вас слоны отказываются стоять на черепахах, например вам нужны две разных версии системообразующих библиотек например таких как spring или hibernate. В общем Jar Helsing хорош когда можно четко очертить границы того, что требует специфический classpath, закрыть это интерфейсами не содержащими детали реализации, а реализацию выпинать в отдельный модуль и в Runtime прогружать с отдельным classpath. То есть Jar Helsing это скальпель для хирургических микроопераций.


воскресенье, 3 января 2016 г.

Юнит тестирование Java кода работающего со временем

Симптомы кода приводящего к плохим юнит тестам:

Часто нам приходится писать java код которому необходимо предпринимать различные действия в зависимости от текущего времени: 
Я искренне надеюсь что Вы сознательный пограммист, следовательно не менее часто Вам приходится писать юнит тесты к такому коду, которые тестируют пошел ли код по определенной ветке или нет в зависимости от того истек ли определенный интервал времени.

Рассмотрим простой пример кода, который написан таким образом что затрудняет своё тестирование. Ниже приведен класс представляющий собой некий аларм тобишь сигнал о том, что в приложении что-то не так, после того как зажегся аларм остаётся взведенным в течении сконфигурированного периода времени, а потом затухает:
public class TemporaryAlarm {

    private final AtomicLong lastUpdateTime = new AtomicLong(0L);    
    private final long expirationTimeInMillis;        
    
    public TemporaryAlarm(long expirationTimeMillis) {
        this.expirationTimeInMillis = expirationTimeMillis;    
    }

    public void turnOn() {
        lastUpdateTime.set(System.currentTimeMillis());    
    }

    public boolean isTurnedOn() {
        return System.currentTimeMillis() - lastUpdateTime.get() < expirationTimeInMillis;    
    }

}
Аларм в конструкторе конфигурируется временем в течении которого он должен хранить взведенное состояние, в методе turnOn запоминается время взведение тревоги, а метод проверяющий взведен ли аларм isTurnedOn  сравнивает время прошедшее с момента последнего взведения с сконфигурированным интервалом. Код осуществлющий валидацию параметров конструктра намеренно опущен.

Вот код юнит теста покрывающего все ветки:
public class TemporaryAlarmTest {
    
    @Test
    public void testInitStateShouldBeTurnedOff() {
        TemporaryAlarm alarm = new TemporaryAlarm(1000);
        Assert.assertFalse(alarm.isTurnedOn());
    }

    @Test    
    public void testStateShouldBeTurnedOnDuringExpirationTimeout() {
        TemporaryAlarm alarm = new TemporaryAlarm(1_000);        
        alarm.turnOn();
        Assert.assertTrue(alarm.isTurnedOn());
        Thread.sleep(50);
        Assert.assertTrue(alarm.isTurnedOn());
     }

     @Test
     public void testStateShouldBeTurnedOffAfterExpirationTimeout() {
        TemporaryAlarm alarm = new TemporaryAlarm(1000);
        alarm.turnOn();        
        Assert.assertTrue(alarm.isTurnedOn());
        Thread.sleep(TimeUnit.SECONDS.toMillis(2));
        Assert.assertFalse(alarm.isTurnedOn()); 
     }

}
На первый взгляд кажется, что с этим тестом всё хорошо, он стабильно проходит и инструменты анализа coverage показывают, что он покрывает все ветки в тестируемом классе, мы фиксируем код теста и класса в общем репозитарии, сборка на continuous integration сервере проходит и мы благополучно забываем про этот класс и тест к нему.

Но забыть на долго этот код у нас увы не получится. Спустя некторое время с continuous integration сервера приходит письмо о том, что сборка упала, мы проходим по ссылке с отчетом и видим что упал testStateShouldBeTurnedOnDuringExpirationTimeout, смотрим код класса и теста не поменял ли там кто что-нибудь - да нет ничто не менялось, тогда в непонимании чешем репу, запускаем сборку заново, она проходит и мы с чувством выполненного долга и твердой уверенностью, что опять в этом вашем JUnit что-то набыдлокодили забываем про этот тест.

Но увы опять не надолго, к нам приходит коллега которого мы недолюбливаем из-за того, что ему вечно спокойно не сидится и всегда хочется чего-то странного. На этот раз он решил что maven сборка проходит слишком долго а именно 4 минуты, он решил задействать возможности по паралельной сборке, которые на его машине сокращают врем билда до одной минуты, но при запуске билда в паралельном режиме он обнаружил что опять же тест testStateShouldBeTurnedOnDuringExpirationTimeout то проходит, то нет.

Что же не так с этим тестом? Мы настроили время жизни аларма в одну секунду, взвели его, отправили поток в сон всего лишь на 50 милисекунд, следовательно, когда поток выходит из сна остается еще 950 милисекундный запас, и выйдя из сна поток должен увидеть флаг взведенным, однако тесты иногда показывают что это не так и флаг выключен. Всё дело в том, что поток выходит из сна, не сразу когда истечет время переданное в метод sleep, всё сильно зависит от текущей загруки и процессора и наличия паралельно выполняющихся потоков желающих откусить свой кусок пирога от  ресурсов процессора, и может случится так, что пройдёт и более одной секунды прежде чем планировщик операционной системы поставит поток обратно на выполнение. Этим объясняется и случайные подения на continuous integration сервере, когда сервер не сильно загружен то тест успешно проходит, но может случиться так что на сервере будет запущенно паралельно сразу много сборок и тогда при достижении определенного порога нагрузки на процессор этот тест может упасть. То же самое и про падения на машинах разработчиков, когда я запускаю maven сборку в паралельном режиме, у меня даже движения курсора мыши по экрану медленно прорисовывается, соответсвенно тест опять работает нестабильно.

Нестабильность это не единственная проблема, с такими рода тестами. Всегда когда мы используеем Thread.sleep() в тестах мы тем самым увеличиваем вермя сборки на то время котрое потоки проводят в этих самых слипах. Это не так страшно когда таких тестов несколько штук, однако в продукте истрия которого длится не один год, таких тестов может накопится сотни, а то и тысячи, а почем зря потраченное время может исчисляться минутами. Это всё напросно потраченные деньги компании, ведь когда разработчик запускает сборку на локальной машине, прежде чем зафиксировать код в общий репозитарий, ему достаточно сложно играть в многорукого шиву и паралельно выполнять еще какую-то полезную работу, большинстве случаев мы тупо залипаем в конслоль и ждём. Заканчиваются такого рода истории как правило тем, что разработчики из-за долгих сборок вообще перестают их выполнять локально на своих машинах или делают это через раз, или локально собирают только то, что по их мнению могло сломаться после внесенных изменений.

Анализируем проблему:

И так наш тест: первое нестабилен, второе увеличивает время сборки. Для обретения стабильности нам нужно заставить метод System.currentTimeMillis() возвращать то время которое нам нужно, а не то которе сейчас реально на машинных часах, а если мы сможем настраивать поведение currentTimeMillis как нам нужно, то автоматически мы избавимся от пробемы со слипами, когда нам потребуется получить момент времени на 100 милисекунд позже текущего, вместо того чтобы реально отправлять поток в сон на 100 милесекунд, мы можем просто указать методу currentTimeMillis сразу вернуть нужное нам значение времени. 

Всё бы хорошо, но метод System.currentTimeMillis()является статическим, и с помощью таких библиотек как Mockito или EasyMock стандартно входящих в инструментарий любого Java разработчика настроить его поведение на нужное не удастся, так как обычные библиотеки для мокирования подделывать поведения статических методов не умеют. Но не всё потерянно, если решать проблему в лоб и винить во всём только тест, то для мокирования можно взять более тяжелую артилерию как библиотеку PowerMock, и легко добиться нужного нам результата. Однако я не буду приводить здесь код теста написанного с помощью PowerMock, и вовсе не потому, что считаю тесты написанные с помощью PowerMock более медленными чем обычные из-за того что под каждый тест они создают отдельный экземпляр класслоадера, или из-за того что считаю их нестабильными и рендомно отправляющими JVM в креш, а перспективы вообще запустить такие тесты на JDK отличающихся от OpenJDK например на J9 от IBM весьма туманны. Вовсе нет, есть более резонные причины в нашем конкретном случае не использовать PowerMock, и давайте пофилософствуем о них:

В написанном нами коде мы получаем текущее время через статику, однако при этом ни одному здравомыслящему Java программисту не прийдёт в голову к примеру через статические методы делать запросы в базу данных. Для запросов к БД мы всегда выделяем отдельный Data Access Object(или его собрат Repository) с нестатическими методами такими как записать, изменить, найти по критерию и.т.д. То есть остальной код приложения не имеет статических завязок на базу данных, код в приложении зависит от полноценного объекта и подложив в тест специально настренный mock вместо реального DAO мы можем протестировать бизнесс логику приложения без привязки к БД. Теперь вернемся ко времени, значение текущего время по отношению к нашей программе является точно таким же внешним ни коем образом неконтроллируемым фактором как и какая-то строка в таблице во внешней СУБД, так почему же мы в одних случаях позволяем работать с внешними по отношению к приложению понятиями через статику а в других случаях нет? Мне кажется ответ достаточно прост - мало кто об этом задумывается, вообще число разработчиков которые при написании кода рассуждают, философствуют и задают задают себе вопрос а не фигню ли я делаю, достаточно мало, а текущий дизайн стандартной библиотеки Java просто подталкивает считывать текущее время посредством статических методов, поскольку ничего другого банально в стандартной библиотеке нет!!!

Итог анализа проблемы следующий: виной плохих тестов является вовсе не непосредственно код самих тестов, как может показаться на первый взгляд, всему причина, то что сам продакшен код работает с внешними ресурсами способом, который человеческим образом невозможно замокать. Каков стол таков и стул каков код таков и тест.

Исправляем проблему:

Решение достаточно тривиально. Если стандартная бибилиотека Java не предоставляет на никаких способов без примения статических методов получать текущее время, так давайте создадим класс-обертку, который будет позволять это делать:
public interface Clock {

    long currentTimeMillis();

    long nanoTime();

    static Clock getDefaultClock() {
        return DEFAULT;    
    }

    Clock DEFAULT = new Clock() {
        @Override        
        public long currentTimeMillis() {
            return System.currentTimeMillis();        
        }

        @Override        
        public long nanoTime() {
            return System.nanoTime();        
        }
    }; 
}

Как видим получившийся класс Clock является интерфейсом, во все места в коде где идёт работа со временем и это нужно протестировать, теперь можно инжектить реализации этого интерфейса, вместо того чтобы, запрашивать время напрямую у системы. Экземпляр дефолтной имплементации запомнен в константу и его можно повсеместно использовать, чтобы не порождать зря одинаковые объекты. Создавать моки можно легко как с использованием таких библиотек как Mockito или EasyMock так и без них.

Теперь исходный класс TemporaryAlarm преобразуется в следующий:
public class TemporaryAlarm {

    private final AtomicLong lastUpdateTime = new AtomicLong(0L);    
    private final long expirationTimeInMillis;    
    private final Clock clock;
    
    public TemporaryAlarm(long expirationTimeMillis) {
        this(expirationTimeMillis, Clock.getDefaultClock());    
    }
    
    // visible for testing    
    TemporaryAlarm(long expirationTimeMillis, Clock clock) {
        this.expirationTimeInMillis = expirationTimeMillis;        
        this.clock = clock;    
    }

    public void turnOn() {
        lastUpdateTime.set(clock.currentTimeMillis());    
    }

    public boolean isTurnedOn() {
        return clock.currentTimeMillis() - lastUpdateTime.get() < expirationTimeInMillis;    
    }

}

Как видно код не сильно то и изменился. Для удобства был создан еще один конструктор, который помимо таймаута действия аларма, еще как параметр принимает экзэмпляр объекта часы. Так нам врятли где захочется менять способ получения текущего времения кроме как в тестах, то с этого констуктора убран модификатор public ибо в продакшене он нам не нужен.

Теперь посмотрим как изменился тест:
public class TemporaryAlarmTest {

    Clock clock = Mockito.mock(Clock.class);

    @Test    
     public void testInitStateShouldBeTurnedOff() {
        TemporaryAlarm alarm = new TemporaryAlarm(1000);        
        Assert.assertFalse(alarm.isTurnedOn());    
     }

    @Test    
    public void testStateShouldBeTurnedOnDuringExpirationTimeout() {
         TemporaryAlarm alarm = new TemporaryAlarm(1_000, clock);        
         when(clock.currentTimeMillis()).thenReturn(100_000_000_000L, 100_000_000_001L, 100_000_000_050L);
         alarm.turnOn();        
         Assert.assertTrue(alarm.isTurnedOn());        
         Assert.assertTrue(alarm.isTurnedOn());    
     }

    @Test    
    public void testStateShouldBeTurnedOffAfterExpirationTimeout() {
        TemporaryAlarm alarm = new TemporaryAlarm(1000, clock);        
        when(clock.currentTimeMillis()).thenReturn(100_000_000_000L, 100_000_000_001L, 100_000_002_000L);         
        alarm.turnOn();        
        Assert.assertTrue(alarm.isTurnedOn());        
        Assert.assertFalse(alarm.isTurnedOn());    
     }

}

В тестах теперь вместо того, чтобы отправлять поток в сон, мы настраиваем серию значений которую должна возвращать заглушка для часов. И всё - мы победили как непредсказуемость результата так и долгое выполнение тестов, без использования грубых хаков в стиле PowerMock. 
Теперь по поводу хаков: если Вы мучаетесь вопросом, а не велосипед ли здесь написан, и решает ли такие проблемы таким же способом еще хоть кто-то в обозреваемой галактике, то будте уверенны что Вы не одиноки. Java обычно используется в больших проектах с множеством зафисимостей, Вы можете в своем проекте просто в IDE запустить поиск по классу Clock, у меня нашлись следующие примеры:
  1. org.apache.http.impl.client.Clock
  2. com.codahale.metrics.Clock
Эти классы предназначенны ровно для того, для чего мы создавали свой. Так что как видно, что проблема эффективного тестирования кода зависящего от времени таки мучает широкую общественность. Так же во многих библиотеках абстракции для времени могут называться по разному, например в Guava обертка над временем называется Ticker.

О java 8 замолвите слово:

Утверждая, что стандартная бибилиотека Java подталкивает писать трудно тестируемый код, нужно конечно же указывать, а про какую именно версию java идёт речь. В java 8 API для работы с датами и временем был серьезно доработан давайте-ка посмотрим, что получилось и не решена в восьмерке проблема абстракции над получением текущего времени. Класс который нам нужен достаточно быстро обнаруживается в новом пакете java.time, он неожиданно также называется Clock, и он  решает нашу проблему с написанием легко тестируемого кода, но к сожалению лишь частично. Почему всего лишь частично и в каких случаях он нам не подойдёт(или не совсем подойдёт) будет написанно в самом конце статьи. Пока же порадуемся, что мы в своем проекте перешли на Java 8, и перепишем наш код на использование java.time.Clock,  я подразумеваю что джавадоки к классу Вы осилите самостоятельно:
import java.time.Clock;
import java.util.concurrent.atomic.AtomicLong;

public class TemporaryAlarm {

    private final AtomicLong lastUpdateTime = new AtomicLong(0L);    
    private final long expirationTimeInMillis;    
    private final Clock clock;
    
    public TemporaryAlarm(long expirationTimeMillis) {
        this(expirationTimeMillis, Clock.systemUTC());    
    }

    // visible for testing    
    TemporaryAlarm(long expirationTimeMillis, Clock clock) {
        this.expirationTimeInMillis = expirationTimeMillis;        
        this.clock = clock;    
    }

    public void turnOn() {
        lastUpdateTime.set(clock.millis());    
    }

    public boolean isTurnedOn() {
        return clock.millis() - lastUpdateTime.get() < expirationTimeInMillis;
    }

}

Как видно продакшен код практически не изменился. Не сильно изменился и соответсвующий юнит тест, всего то вместо одного класса мокаем другой:
import java.time.Clock;
import static org.mockito.Mockito.*;

public class TemporaryAlarmTest {

    Clock clock = Mockito.mock(Clock.class);

    @Test    
    public void testInitStateShouldBeTurnedOff() {
        TemporaryAlarm alarm = new TemporaryAlarm(1000);
        Assert.assertFalse(alarm.isTurnedOn());
    }
    @Test
    public void testStateShouldBeTurnedOnDuringExpirationTimeout() {
        TemporaryAlarm alarm = new TemporaryAlarm(1_000, clock);
        when(clock.millis()).thenReturn(100_000_000_000L, 100_000_000_001L, 100_000_000_050L);
        alarm.turnOn();
        Assert.assertTrue(alarm.isTurnedOn());
        Assert.assertTrue(alarm.isTurnedOn());
    }
    @Test
    public void testStateShouldBeTurnedOffAfterExpirationTimeout() {
        TemporaryAlarm alarm = new TemporaryAlarm(1000, clock);
        when(clock.millis()).thenReturn(100_000_000_000L, 100_000_000_001L, 100_000_002_000L);
        alarm.turnOn();
        Assert.assertTrue(alarm.isTurnedOn());
        Assert.assertFalse(alarm.isTurnedOn());
    }
}


Однако что же не решено по обозначенной в начале посте проблеме в восьмерке?
- Ну что ж, давайте бросим ложку дёгтя в цистерну бочку мёда восьмерки. Если вы посмотрите обертку для времени которую мы написали своим собственными руками, то помимо метода получения текущего времени в милисекундах, также есть метод получения времени в наносекундах. К сожалению в классе Clock из стандартной библиотеке Java 8 есть метод получение времени в милисекундах millis(), но отcутствуют метод для получения времени в наносекундах. Это в принципе даже понятно почему, пакет java.time он больше про работу на уровне Wall-clock time - то есть со временем которое имеет значение для человеческих человеков, а наносекунды человекам нужны достаточно редко, а если кому-то и потребуются, то сначала следует разобраться, что это за человеки такие. Вот к примеру в TemporaryAlarm наносекунды были не нужны, могу поспорить, что в 99% кода, который Вы пишите наносекунды тоже не нужны, так что Clock из java time в большинстве, то что Вам нужно для написания тестируемого кода, ну это конечно при условии, что Вы можете себе позволить писать на Java 8, многие на восьмерку еще не перешли и такой роскоши себе позволить не могут.

Однако если Вы пишите специфический инфраструктурный код, например код связанный со сбором телеметрии, профилированием, бенчмаркингом и прочими прелестями при написании которых нужно точно знать сколько вешать в граммах, то без кастомной обертки над временем, Вы никак не обойдётесь если захотите написать к нему хорошие юнит тесты. Правда наверно обертку не всегда нужно писать самим и копипастить таскать за сосбой из проекта в проект, к примеру в библиотеке Guava, которая претендует быт расширением стандартной библиотеки java и как правило так же есть в зависимостях у любого Java проекта, уже есть готовая абстракция над получением времения в наносекундах которая называется Ticker.

Постскриптум:

Ну и напоследок. Юнит тесты это конечно же хорошо, но не стоит забывать и про полноценное интеграционное тестирование вашего кода работающего со временем, не поленитесь написать хоть чуть-чуть полноценных тестов работающих по принципу черного ящика, иначе с вашим кодом который юнит тестами покрыт на 146%, может приключиться такая история: 

Из-за разницы в календарях (Россия – Юлианский календарь, Англия – Григорианский календарь) сборная России в 1908 году опоздала на Олимпиаду на 12 дней.