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

Задачу стояла так:

авторОчередь заданий с относительным порядком

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


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

Пример: подход, при котором очередь выполняет все задания последовательно в единственном потоке, удовлетворяет условию на порядок выполнения заданий с одинаковым значением ключа.


Примерный интерфейс задания:
interface Task implements Runnable {
String getKey();
}

Примерный интерфейс очереди:
interface TaskExecutor {
void submit(Task task);
}



Решение должно использовать только стандартную библиотеку Java 8, плюс тестовые фреймвоки на выбор.

Решение должно использовать более одного потока для выполнения заданий.
Решение должно контроллировать (ограничивать) максимальное количество используемых потоков.

Не требуется делать решение, покрывающее все возможные варианты, учтённые или не учтённые в описании выше.

Мы ожидаем, что решение займет несколько часов.
Если есть сомнения, делайте как проще и задокументируйте, какие упрощения или предположения вы сделали.

Давайте тесты обсуждать не будем, только экзекутор.

я решил задачу двумя способами. Первый - очень очевидно и просто, но с неточностью(не учёл, что hashCode может быть отрицательным), но не достаточно производительно.

Хотел бы обсудить второй способ. Лично мне он очень понравился и я был удовлетворён, что смог решить.

вот код:




а вот комментарий от проверяющего(Кстати спасибо ему большое, что он его выдал - всё таки я потратил время, выполнял задачу, услышать фидбэк очень интересно):

автор## Второй вариант решения

Преимущество этого подхода в том, что задачи с разными ключами будут занимать все доступные потоки.

Проблема предложенной реализации в том, что при использовании метода ConcurrentMap.compute функция ремапинга может быть вызвана несколько раз.
Если несколько потоков одновременно добавляют новые задания с одним и тем же ключом, некоторые из заданий будут многократно добавлены в цепочку CompletableFuture.

Простейший пример - какое-то задание T0 с ключом Х находится в обработке, то есть в мапе присутствует CompletableFuture F0.
Два разных потока одновременно добавляют новые задания T1 и Т2 с тем же ключом Х. В обоих потоках вычисляется taskMap.compute от F0, внутри функции ремапинга оба потока добавляют свои задания в цепочку на F0, но только одному потоку удаётся завершить taskMap.compute, например первому потоку, который создаст CompletableFuture F1. Второй поток вычисляет ремапинг ещё раз, на этот раз от F1, и добавляет своё задание в цепочку поверх F1.

В итоге, если в poolExecutor достаточно свободных потоков, после завершения T0 оба задания T1 и Т2 начнут выполняться одновременно, а после завершения Т1 запуститься ещё один экземпляр Т2.

Дальше я задал следующий вопрос:

По первому решению я согласен с комментариями, а вот что касается второго - хотелось бы уточнений.

авторВ jdk ConcurrentHashMap compute не может исполняться Параллельно для ключей из одного бакета. То есть потоки с задачами T1 и T2 выстроятся в очередь и не будет описанных выше проблем.
/**
* Attempts to compute a mapping for the specified key and its
* current mapped value (or {@code null} if there is no current
* mapping). The entire method invocation is performed atomically.
* Some attempted update operations on this map by other threads
* may be blocked while computation is in progress, so the
* computation should be short and simple, and must not attempt to
* update any other mappings of this Map.
*/
Это довольно легко проверить если сделать Thread.sleep внутри compute и сделать из разных потоков put с одинаковыми ключами.
Я полагаю, что проблема в том, что я использовал ConcurrentHashMap через интерфейс ConcurrentMap, документацию которого я не прочитал. ConcurrentMap интерфейс действительно разрешает несколько раз выполнять compute(видимо для CAS алгоритмов)
/*The default implementation may retry these steps when multiple
* threads attempt updates including potentially calling the remapping
* function multiple times.
*/
И тогда я понимаю как может произойти описанная ситуация.

Мои мысли правильны?

Но на это сообщение мне ответили, что коллеги не имеют достаточно свободного времени, чтобы мне отвечать.

Я полагаю, что неправильное решение значит решение не такое какое они считают наиболее правильным.

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

авторПо первому решению я согласен с комментариями, а вот что касается второго - хотелось бы уточнений.

это часть письма была, конечно.

irbis_alquestioner,

Я в толк не возьму,а Вы тестировали...или просто сделали...Когда речь идёт о многопоточном,то там надо эмулировать ситуации...
В Вашем случае должна быть эмуляция и быть бы лог эмуляции
Типа
Начинает исполнятся задача такая-то(с ключом)
Исполняется задача такая-то
Исполнилась задача такая-то
Начинает исполнятся задача такая-то(с ключом)
Исполняется задача такая-то
Начинает исполнятся задача такая-то(с ключом)
Исполнилась задача такая-то
Исполняется задача такая-то
Начинает исполнятся задача такая-то(с ключом) Опаньки...а уже этот ключ не закончил выполнение
поэтому wait

В частности в эмуляцию подаём все с одинаковыми ключами и я в логе должен видеть однозначно последовательное выполнение.

Для себя на этапе разработки делал, но потом написал тест, который делает это "более умно". Но это совсем другая история. Предлагаю в данном топике тесты не обсуждать.

irbis_al,

Безусловно, такие тесты есть, у меня тоже вызвало вопросы, что тест не валился, а они говорят, что такое может быть. Но это ж конечно многопоточка, если ты не получил ни разу - не значит, что все верно

irbis_alquestionerirbis_al,

Безусловно, такие тесты есть, у меня тоже вызвало вопросы, что тест не валился, а они говорят, что такое может быть. Но это ж конечно многопоточка, если ты не получил ни разу - не значит, что все верно

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

Раз уж зашёл разговор про тесты...я в начале таски пробовал добавлять в сет(потокобезопасный) ключ, в конце - удалял. Если в начале не получалось добавлять - значит случилось что-то, что не должно было случиться и я этот факт регистрировал, в конце теста смотрел сколько инцидентов случилось. Тест сабмитил 100_000 тасков по 10 ключам, то есть по 10_000 на каждый ключ. Внутри каждой таски Thread.sleep длительностью от 5 до 30 мс. случайно.

А про семафор я чего-то не понял. Кто с кем сцепиться должен был и по какой причине? семафор же позволяет n потокам войти в критическую секцию.

Но дело явно не в тестах - они ведь явно написали, что код не потоко безопасный, содержит race condition-ы

scf,

Ну мы же все понимаем, что "может" случается для конкурентной модификации в рамках бакета.

vimbaquestioner,

Я детально не вчитывался, но напервый взгляд нигде не сказано, что удалять из мапы нельзя находясь внутри compute, однако по факту это так, по крайней мере для openjdk 1.8.111. Вот этот кода кусок намертво виснет, ровно по той же причине по которой у меня повис и ваш экзекьютор:



В вашем коде действительно как и сказали проверяющие, есть ещё и возможность паралельного выполнения тасок по одному и тому же ключу, только причины другие, не те которые Вам отписали. Но прежде чем я вам их назову, сначала исключите зависание, вызванное тем что whenComplete может вызваться внутри compute, из-за того что фьюча уже закомплечена. Именно расстановка слипов вас и сгубила при тестировании.

А вас не смущает, что я тесты запускал и они проходили? Как это связано со слипами не понятно
Если Вы внимательно посмотрите, что remove выполняется не в compute треде

авторвас и сгубила при тестировании

Зачем пытаться, что-то придумывать если люди явно текстом написали, что их смущает?

забыл никquestionerМы ожидаем, что решение займет несколько часов.


сли останется время, большим плюсом будет написание своей ОС, компилятора Java и аналога Варкрафта.

Да, я в эти оценки тоже не верю. Год наверное назад был в одной конторе на собеседовании, поотвечал на вопросы, потом меня начинают спрашивать готов ли я сделать тестовое задание. А тогда у меня свободного времени особо не было и я скептически начал спрашивать что примерно за задание, какой объём. Мне говорят мол задачка небольшая часа на 3(на дом, естественно). В итоге я сказал, что мне лень её делать(текста я не получал). Потом спрашиваю знакомого из этой фирмы что за задание они дают и на сколько большое. В итоге выяснилось, что тот человек, который меня собеседовал с опытом 15+ лет буквально за полгода до моего собеседования пришёл в компанию и решал эту задачу. У него ушло 3 дня!

Alexey TominquestionerА вас не смущает, что я тесты запускал и они проходили? Как это связано со слипами не понятно

То, что тесты проходят, не гарантирует правильность кода. Особенно если это многопоточность.
Самая плохая бага- которая случается в одном случае из миллиона- на тестах не поймать, в проде- пожалуйста, будет приходить.
Непонимание этого- уже достаточная причина отказать.
А ваша агрессия- причина не объяснять отказ.

20765509

Судя по сообщению человека с ником Vimba у него виснет некий код. Судя по всему всегда. Имхо он либо виснет либо нет.

vimbaнапервый взгляд нигде не сказано, что удалять из мапы нельзя находясь внутри compute

автор /**
* Attempts to compute a mapping for the specified key and its
* current mapped value (or {@code null} if there is no current
* mapping). The entire method invocation is performed atomically.
* Some attempted update operations on this map by other threads
* may be blocked while computation is in progress, so the
* computation should be short and simple, and must not attempt to
* update any other mappings of this Map.
*
* @param key key with which the specified value is to be associated
* @param remappingFunction the function to compute a value
* @return the new value associated with the specified key, or null if none
* @throws NullPointerException if the specified key or remappingFunction
* is null
* @throws IllegalStateException if the computation detectably
* attempts a recursive update to this map that would
* otherwise never complete
* @throws RuntimeException or Error if the remappingFunction does so,
* in which case the mapping is unchanged
*/

vimba сначала исключите зависание, вызванное тем что whenComplete может вызваться внутри compute, из-за того что фьюча уже закомплечена.

Поясните что это и зачем, как вы решили, что это неправильно.

questionervimba сначала исключите зависание, вызванное тем что whenComplete может вызваться внутри compute, из-за того что фьюча уже закомплечена.

Поясните что это и зачем, как вы решили, что это неправильно.

Ок, действительно такое имеет место быть.




авторMain thread:1
Before sleep thread:11
After sleep
whenCompleted thread:1


Только они этого не нашли)

Надо подумать как это решить... из спортивного интереса

Alexey TominВаше решение- по сути своей хак.
Такой код нельзя пускать в production. Он чрезвычайно неочевиден.
Можно терпеть медленный код, но нельзя непонятный.
Тут дискутировать нечего- это вопрос вкуса. Работает или нет- уже вторично, на самом деле.

у всех свои критерии понятности... У меня был отослан понятный код если что(как раз на этот случай). Передаём параметром количество потоков и создаём в соответствии с этим столько же очередей и воркеров и по хешу от ключа - кидаем в очередь. Но тут сказали, что распределение не нравится и судя по всему второе решение понравилось больше.

Да и заказчику зачастую на%?#ть понятно написано или нет - лишь бы работало. Как объясните заказчику, что есть рабочий непонятный код, который быстро работает, а есть медленный, но понятный. Думаю заказчик выберет быстрый вариант, если для него это критично. Но я опять же не агитирую писать непонятную ахинею. Я вообще не очень согласен, что код совсем уж непонятный. не простой - да, но и задача не самая очевидная не очень то делится на подзадачи.

Alexey Tominquestioner


На самом деле имя "queue" для этого параметра- уже смертный приговор.

Почему?

Вот кстати рабочий вариант, который исключает ситуацию, что задача закончилась до того, как мы прилепили ей коллбэк

Alexey TominquestionerДа и заказчику зачастую на%?#ть понятно написано или нет - лишь бы работало.

Вас оценивали потенциальные коллеги. Они не заказчики, им важна понятность.


По разному бывает.

Вообще странно как-то писать, что у вас не работает корректно детально то-то и то-то, а по факту подразумевать, что код не понятен. Не находите?
questionerпропущено...
Alexey TominПочему?

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

То, что Вы не смогли это сразу понять ещё не значит, что это непонятно написано.

Скажем есть список рукописный и у вас есть ссылка на голову. Нельзя назвать эту ссылку list ? Этот аргумент по сути является очередью задач, а для меня ожидателем выполнения всей очереди до этого элемента включительно. Именование дело такое... как не назови - все не поймут, но мне кажется я постарался.

Alexey Tominquestioner

Вот кстати рабочий вариант, который исключает ситуацию, что задача закончилась до того, как мы прилепили ей коллбэк

Т.е. опять- пишут "метод должен отрабатывать как можно быстрее", а тут await.
Не, я понимаю, тут может всё достаточно быстро, но нафига писать такой код? Его трудно понимать, трудно поддерживать.

Предложите вариант получше? я не смог просто. Думаете я стараюсь посложнее специально написать?

Alexey Tominquestionerпропущено...

По разному бывает.

Не понял. Что, кто-то любит непонятный код в репозитории? Не знаю, я бы не хотел там работать...


Этот комментарий относился к тому, что иногда оценивают коллеги, а иногда и заказчику могут заслать.

Alexey TominquestionerВообще странно как-то писать, что у вас не работает корректно детально то-то и то-то, а по факту подразумевать, что код не понятен. Не находите?

1. Я оцениваю код, а не тех, кто оценивал код
2. Может там и ошибка. Мне не хочется разбираться.

Собственно суть топика в том, чтобы обсудить аргументацию. Да, дополнительно обсудить какие-то другие решения тоже интересно.


Alexey TominquestionerСкажем есть список рукописный и у вас есть ссылка на голову. Нельзя назвать эту ссылку list ?

head, по-моему, правильнее. Например потом, что queue не может быть null. А head - может.

Согласен, но это название допустимо всё же.
Alexey TominquestionerПредложите вариант получше? я не смог просто. Думаете я стараюсь посложнее специально написать?

Не знаю. В соседней теме я показал то, что написал за неполный час.
По мне- так намного проще. Возможно чуть медленнее, но для начала точно хватит.

Для какого начала? это тестовое задание) Тем более вариант попроще и попонятнее я и так имею и он был вместе с этим отправлен. То, что там могут быть коллизии ребятам не понравилось.


EmptyLock не используется у вас нигде кроме комментариев. зачем он?
что такое "conflict" error ?

Ваша имплементация нарушает требования тестового задания, что все задачи должны выполняться в порядке прихода. Это на первый взгляд

Alexey Tomin,



будет тратить поток на все ключи без исключения.

То есть подряд идущие
key1
key1
key2

займут 3 потока вместо 2-ух. Но я думаю Вы это понимаете. Первое моё решение как-раз ругали из-за подобной "неоптимальности"

Alexey TominquestionerЭтот комментарий относился к тому, что иногда оценивают коллеги, а иногда и заказчику могут заслать.

Заказчик либо не читает, либо тоже смотрит понятность кода.

questionerпропущено...


EmptyLock не используется у вас нигде кроме комментариев. зачем он?
что такое "conflict" error ?

Ваша имплементация нарушает требования тестового задания, что все задачи должны выполняться в порядке прихода. Это на первый взгляд

Это был пример теста вообще-то, а задания я не читал. Комментарий- это чтобы тест уронить.

В любом случае- не надо использовать методы Map для того, чтобы ставить задания в очередь. Это не то.

Их аргументацию обсуждать мне не интересно, т.к. они здесь не пишут.

Им были заданы вопросы, на которые им некогда отвечать) Так что считаю обсудить тут вполне корректно. К тому же имён я не раскрывал.

А зачем вы скинули пример теста если мы сейчас обсуждаем имплементацию экзекутора?

Ну в общем суть в том, что "для начала сойдёт" - не сошло) Как я уже писал - решение с подобным перформансом было и оно не удовлетворило проверяющих.

BlazkowiczquestionerТолько они этого не нашли)

Надо подумать как это решить... из спортивного интереса



Да, годится. По коду так попроще конечно будет и никаких новых race condition от этого я не вижу.

Blazkowiczquestioner,

Что-то я не понимаю как должен taskMap.remove() вообще работать в приведенном коде? Он же на каждую задачу в цепочке будет вызываться, даже если там есть ещё задачи, мы всю цепочку по ключу удалим?

task.remove удаляет не по ключу, а по ключу и значению.

Если значение(фьюча) поменялась, то ничего удалится

questioner,


questionerЕсли значение(фьюча) поменялась, то ничего удалится
Если значение(фьюча) поменялась, то ничего НЕ удалится

Blazkowicz,

Это на мой взгляд самая хитрая часть этого кода и было потрачено много времени, чтобы придумать эту конструкцию

BlazkowiczquestionerВ jdk ConcurrentHashMap compute не может исполняться Параллельно для ключей из одного бакета.
Этим мы расписываемся в том что решение не устойчиво к атаке на hash collision?

Это же инфраструктурный класс. Кому придёт в голову его атаковать?

К тому же ничего уж сильно плохого не случится. Добавление в мапу и создание парочки фьючей не такая уж и тяжёлая операция по сравнению с самой задачей.
BlazkowiczДа, стоило написать явно на чем именно ключи синхронизируются.

То, что всё это работает на очереди фьючей? комментарии в коде имеете ввиду или что-то типа сопроводительного письма?

BlazkowiczquestionerЭто же инфраструктурный класс. Кому придёт в голову его атаковать?

Мы не знаем источника ключей.

questionerК тому же ничего уж сильно плохого не случится. Добавление в мапу и создание парочки фьючей не такая уж и тяжёлая операция по сравнению с самой задачей.

Ну, тогда бы и решение с synchronized подошло бы?


Вы утрируете.

Synchronized - всё в один поток и многопоточности нет тогда.
допустим у нас большой объём разных ключей, которые валятся в один бакет, но при этом они в основном разные.
Грубо говоря можно представить, что в данной есть один тред, который занимается маршрутизацией, то есть создаёт фьючи только, а сами таски выполняются в экзекуторе в отдельных тредах. Или Вы про Collections.synchronizedMap ? тогда да, то же самое. Но это на мой взгляд не такая уж и большая проблема.

Не очень понял Ваш пассаж. Что Вы имеете ввиду?

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

автор Some attempted update operations on this map by other threads
may be blocked while computation is in progress, so the
computation should be short and simple, and must not attempt to
update any other mappings of this Map.

Согласен, что явно этого не сказано, но намёк очень явен. В принципе да, согласен, если бы написал - они бы уточнили, проверили и не написали бы то, что написали

BlazkowiczquestionerSynchronized - всё в один поток и многопоточности нет тогда.

Ну, при коллизии hash кодов у нас будет compute всегда synchronized. То есть распределение таски по очередям полностью синхронизировано. Разницы вот с этим кодом нет:




Согласен, но распределение это обычно маленькая часть от работы. Во многих случаях это нормально.

А Вы можете предложить более производительный вариант?