Comments 22
И не забыть прогнать тесты на сложение, потому как после " Поэтому он берется за копипаст, меняет все + на * - и справляется за полтора часа." большая вероятность, что memcached разучится складывать.
Вот не знаю, функция сложения уже протестирована и надежна из коробки, я бы не стал сбрасывать это решение со счетов, но окончательное решение принял бы исходя из а) анализа исходного кода и б) временных ресурсов и обстоятельств, насколько быстро, надежно и когда это должно работать.
Imho это просто неверное понимание задачи: будто у нас на руках не исходный код (который можно модифицировать), а готовая программа (которую можно использовать, как есть).
Напоминает древний анекдот:
Рассказывают, что однажды математик спросил у физика:"Перед вами пустой чайник и не зажженная газовая плита; как вскипятить воду?"
— "Наполнить чайник водой, зажечь газ и поставить чайник на плиту",- отвечает физик.
— "Правильно",- сказал математик.
— "А теперь решите вторую задачу: перед зажженной плитой стоит наполненный чайник.Как вскипятить воду?"
— "Это еще проще - надо поставить чайник на плиту".
— "Ничего подобного!"- воскликнул математик. "Надо погасить плиту, вылить воду из чайника, и мы придем к первой задаче, которую мы уже умеем решать!".
Эх, а я уже набросал решение, как с помощью операций set, append, inc реализовать атомарный mult (хватит только set и append). А задача оказалась на копипаст
Ждем ваше решение в студию!
Решение
По сути, нужно эмулировать операцию compare_and_swap
В начале задачи пишем нужное число например
4
(здесь предполагается, что это сделано до старта всех тредов, тоесть здесь гонки не будет)
Теперь, когда мы хотим умножить результат на 10, мы
1) Читаем все значение поля. В данном случае это "4"
2) Вычисляем от всего этого значения хэш
3) С помощью метода append добавляем значение
hash_1 40
4) Читаем все значение снова целиком. Ищем нашу запись (тоесть "hash_1 40") берем хэш от всего до нашей записи. Если хэш совпадает, то мы атомарно умножили. Завершаем работу
5) Если хэш не совпадает, мы должны восстановить текущее число. Для этого читаем весь файл сверху вниз и для каждой строчки проверяем условие из 4). Если условие 4) выполнено, то "последнее" записанное число найдено.
6) Считаем хэш от всего содержимого, умножаем найденное число на 10, вызываем append и идем на шаг 4)
Тоесть если у нас записи
4
hash_1 40
hash_2 36
hash_3 440
то мы сначала вычисляем "текущее" значение
Для этого идем сверху вниз
hash_1 40
hash_1 совпадает с хэшем всех строк до этой? Да. Это текущее значение. Идем дальше
hash_2 36 совпадает с хэшем всех строк до этой? Нет. Пропускаем. Идем дальше
hash_3 440 совпадает с хэшем всех строк до этой? Да. Это текущее значение.
Значит текущее значение 440
Домножаем на 10, пишем
hash_4 4400
читаем файл, видим
4
hash_1 40
hash_2 36
hash_3 440
hash_5 2200
hash_4 4400
Здесь hash_4 не совпадает с хэшем предыдущих строк. Значит не получилось, делаем еще одну попытку
А меня одного смутило, что, на этапе «код правда готов», ручной тест с умножением age на -1 выдал ошибку?
Вероятно, так как сложение/вычитание не принимали отрицательный аргумент, было логично сохранить такое поведение для новой операции. Но вообще это выглядит как архитектурный косяк самого memcached, либо как фичу в рамках того, что с данными в кэше умножение выполнять не_надо, а чтобы не париться с парсингом знака минус на входе, спрототипировать две операции (там bool на входе неспроста образовался) выходило проще, чем одну, но с парсингом строки. Ну и два опкода выходят быстрее одного за счет исключения одного if на операцию.
в свое время придумал вопрос для собеседования "как изменится размер базы данных, если удалить строку в таблице?" применял два раза, вскрывает много чего и про бд, и про связь с железом (но очень специфично всё, вопрос чисто похоливарить).
Тут важно уточнять, про какую конкретно СУБД речь, могут так же влиять настройки, и что размер может изменится через секунду после удаления, а может и через час.
Слишком много факторов на это влияет.
Предположу, что никак или незначительно увеличится. Если мне не изменяет память, то удаляя что-то из базы мы не удаляем это, а сбрасываем в лог (для возможности отмены транзакции в том числе). Или вопрос не настолько общий?
А если бы там в кишках сидел fetch_add атомарный (который как раз в C++11 появился), то задача могла бы оказаться нерешаемой без глубочайшего ухода в кроличью нору и потери эффективности, ибо fetch_mul в природе нет.
эм, я ничего что
Атомарность относительно тредов и атомарность относительно базы данных это разные вещи
Что мешает сделать compare exchange weak в цикле, который меняет не на X + N а на X * N?)
У меня в голове был совершенно надуманный сценарий: может, они поддерживают отдельный кэш для выделенных числовых значений, где incr на атомиках сделан. Мало ли что в чужом коде может быть. Понятно, что атомарность в БД и атомарность относительно потоков - это совсем не одно и то же
Ну да, насчет эффективности я неправ, CAS спасет. Но вот просто копи-пастом с заменой + на *, как в посте, все равно не решить - я на вот это среагировал в первую очередь. Все равно надо разобрать код, хоть как-то понять, как что устроено, чтобы не было "чик-чик и в продакшн".
Мне кажется, более дельный комментарий, чем мой, - ниже, про то, что атомарность для некоммутирующих операций - это вообще не такая очевидная вещь. Возможно, показатель класса собеседуемого - это как раз обратить на это внимание.
Мне кажется изначально задача про атомарность была на другое. В клиент серверном приложении есть смысл атомарно складывать или умножать, но не все вместе.
Тк в случае однородных операций от перестановки слагаемых ничего не меняется, а вот если они разные, то например,
Сложить 1 и 3 а потом умножить на 5 не равно 1 умножить на 5 плюс 3
Те для атомарности операции должны быть идемпонентны
Таким образом, я думаю, что правильный ответ реализацию атомарного умножения реализовать нельзя.
Простите мое невежество, но откуда берет свое начало модель поведения "не рассказывать о том, какие вопросы спрашивали на собеседовании", если, конечно, не брали на себя обязательства, закрепленные письменно? Наоборот, любопытно поразбирать вопросы, пораскинуть мозгами на досуге.
Помню однажды собеседовали студентов для отбора на стажировку. И понятное дело вышедшие делились с ожидающими информацией о чем спрашивали и как отвечать. Запомнился один, которые в заключении спросил: "А почему вы мне не задали вопрос про X, я знаю как на него правильно ответить!" На это он получил слегка измененное условие над которым пришлось подумать. К его чести, он справился.
Резюмируя - собеседующим тоже быть непросто, если не шпарить по заученному опроснику с умным лицом.
Мне кажется, тут дело в том, что количество хороших вопросов (в рамках определенного уровня) условно конечно, а количество претендентов условно бесконечно, и в определенный момент все хорошие вопросы будут исчерпаны.
по опыту собеседований: я собесил людей в вк, и мы часто давали на live-coding стадии одну и ту же задачу, которую считали хорошей. и в дополнение давали совсем простые и неинтересные, но каждый раз разные.
В последний год стали замечать тренд, что кандидаты хорошо решают "интересную" задачу, и плохо решают простые. Было стойкое ощущение, где-то уже собрали пул наших задач, и самую популярную люди просто зазубривают.
так что Вы правы в своей логике на все 100%.
Лучший технический вопрос, который мне задавали на собеседовании