Ответ 1

Одним простым решением для умеренно больших наборов данных является использование базы данных SQL. Каждая запись todo должна иметь поля "state_id" , "current_at" и "late_at". Вероятно, вы можете опустить "future_at", если у вас действительно нет четырех состояний.

Это позволяет три состояния:

• Будущее: когда сейчас < current_at
• Current: when current_at <= now < late_at
• Поздно: когда late_at <= теперь

Сохранение состояния как state_id (необязательно сделать внешний ключ в таблице поиска с именем "состояния", где 1: Future, 2: Current, 3: Late) в основном хранит де-нормированные данные, что позволяет избежать повторного вычисления состояние, поскольку оно редко изменяется.

Если вы на самом деле не запрашиваете записи todo в соответствии с состоянием (например, ... WHERE state_id = 1) или инициируете некоторый побочный эффект (например, отправление электронной почты) при изменении состояния, возможно, вам не нужно управлять состоянием. Если вы просто показываете пользователю список todo и указываете, какие из них опаздывают, самой дешевой реализацией может быть даже рассчитать ее клиентскую сторону. В целях ответа я предполагаю, что вам нужно управлять состоянием.

У вас есть несколько вариантов обновления state_id. Я предполагаю, что вы применяете ограничение current_at < late_at.

• Простейшим является обновление каждой записи: UPDATE todos SET state_id = CASE WHEN late_at <= NOW() THEN 3 WHEN current_at <= NOW() THEN 2 ELSE 1 END;.

• Вероятно, вы получите лучшую производительность с чем-то вроде (в одной транзакции) UPDATE todos SET state_id = 3 WHERE state_id <> 3 AND late_at <= NOW(), UPDATE todos SET state_id = 2 WHERE state_id <> 2 AND NOW() < late_at AND current_at <= NOW(), UPDATE todos SET state_id = 1 WHERE state_id <> 1 AND NOW() < current_at. Это позволяет избежать извлечения строк, которые не нуждаются в обновлении, но вам понадобятся индексы на "late_at" и "future_at" (вы можете попробовать индексировать "state_id" , см. Примечание ниже). Вы можете запускать эти три обновления так часто, как вам нужно.

• Незначительное изменение приведенного выше состоит в том, чтобы сначала получить идентификаторы записей, поэтому вы можете сделать что-то с todos, которые изменили состояния. Это выглядит как SELECT id FROM todos WHERE state_id <> 3 AND late_at <= NOW() FOR UPDATE. Затем вы должны выполнить обновление, например UPDATE todos SET state_id = 3 WHERE id IN (:ids). Теперь у вас все еще есть идентификаторы, чтобы что-то делать с ними позже (например, по электронной почте уведомление "20 заданий просрочены" ).

• Запланирование или задание обновления очередей для каждого todo (например, обновление этого значения до "текущего" в 10 утра и "позднего" в 11 вечера) приведет к множеству запланированных заданий, по крайней мере, в два раза больше числа todos, и низкая производительность - каждое запланированное задание обновляет только одну запись.

• Вы можете запланировать пакетные обновления, такие как UPDATE state_id = 2 WHERE ID IN (1,2,3,4,5,...), где вы предварительно рассчитали список идентификаторов todo, которые станут текущими в определенное время. Это, вероятно, не так хорошо получается на практике по нескольким причинам. Один из них - некоторые поля todo current_at и late_at могут измениться после запланированных обновлений.

Примечание. Возможно, вы не сможете добиться большего, указав "state_id" , поскольку он делит ваш набор данных на три набора. Вероятно, это недостаточно для того, чтобы планировщик запросов мог использовать его в запросе типа SELECT * FROM todos WHERE state_id = 1.

Ключ к этой проблеме, о которой вы не говорили, что происходит с завершенными todos? Если вы оставите их в таблице todos, таблица будет расти бесконечно, и ваша производительность со временем ухудшится. Решение разбивает данные на две отдельные таблицы (например, "finished_todos" и "pending_todos" ). Затем вы можете использовать UNION, чтобы объединить обе таблицы, когда вам действительно нужно.

Ответ 2

Я разработал и поддерживал несколько систем, которые управляют огромным количеством этих небольших государственных машин. (Некоторые системы, до 100K/день, около 100K/мин)

Я обнаружил, что чем больше состояний вы явно играете, тем более вероятно, что это где-то сломается. Или, говоря иначе, чем больше вы утверждаете, тем более надежным является решение.

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

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

Предпочтительное решение. (Простые снимки лучше всего).

Для вашего примера у меня будет очень простая таблица:

task_id, current_at, current_duration, is_done, is_deleted, description...

и выведите состояние, основанное на now по отношению к current_at и current_duration. Это работает на удивление хорошо. Убедитесь, что вы указали/разделили таблицу на current_at.

Обработка логики при изменении перехода

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

Измените таблицу так, чтобы она выглядела следующим образом:

task_id, current_at, current_duration, state, locked_by, locked_until, description...

Держите свой индекс на current_at и добавьте его на state, если хотите. Вы теперь управляете состоянием, так что вещи немного хрупкие из-за concurrency или неудачи, поэтому нам придется немного его немного с помощью locked_by и locked_until для оптимистической блокировки, которую я опишу ниже.

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

Вам нужен механизм для перехода задачи из одного состояния в другое. Чтобы упростить обсуждение, я буду заниматься переходом от БУДУЩЕГО к ТЕКУЩЕМ, но логика такая же, независимо от перехода.

Если ваш набор данных достаточно велик, вы постоянно проводите опрос базы данных, чтобы открыть для себя задачи, требующие перехода (конечно, с линейным или экспоненциальным отступлением, когда нечего делать); в противном случае вы используете или ваш любимый планировщик, будь то cron или на основе ruby ​​ или Quartz, если вы подписаны на Java/ Scala/С#.

Выберите все записи, которые необходимо перенести с FUTURE на CURRENT и в настоящее время не заблокированы.

( обновление:)

-- move from pending to current
select task_id
  from tasks
 where now >= current_at
   and (locked_until is null OR locked_until < now)
   and state == 'PENDING'
   and current_at >= (now - 3 days)         -- optimization
 limit :LIMIT                               -- optimization

Бросьте все эти task_id в свою надежную очередь. Или, если нужно, просто обработайте их в своем script.

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

update tasks
   set locked_by = :worker_id     -- unique identifier for host + process + thread
     , locked_until = now + 5 minutes -- however this looks in your SQL langage
 where task_id = :task_id         -- you can lock multiple tasks here if necessary
   and (locked_until is null OR locked_until < now) -- only if it not locked!

Теперь, если вы действительно обновили запись, вам принадлежит блокировка. Теперь вы можете запустить свою специальную логику перехода. (Аплодисменты. Это отличает вас от всех других менеджеров задач?)

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

update tasks
   set state = :new_state
     , locked_until = null -- explicitly release the lock (an optimization, really)
 where task_id = :task_id
   and locked_by = :worker_id -- make sure we still own the lock
                              -- no-one really cares if we overstep our time-bounds

Оптимизация нескольких потоков/процессов

Делайте это только тогда, когда у вас есть несколько потоков или процессов, которые обновляют задачи в пакетном режиме (например, в задании cron или опросе базы данных)! Проблема в том, что каждый из них получит аналогичные результаты из базы данных и затем будет бороться за блокировку каждой строки. Это неэффективно, так как это замедляет работу базы данных, и потому что у вас есть потоки, в основном ничего не делающие, кроме замедления других.

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

results = database.tasks_to_move_to_current_state :limit => BATCH_SIZE
while !results.empty
    results.shuffle! # make sure we're not in lock step with another worker
    contention_count = 0
    results.each do |task_id|
        if database.lock_task :task_id => task_id
           on_transition_to_current task_id
        else
           contention_count += 1
        end
        break if contention_count > MAX_CONTENTION_COUNT # too much contention!
    done
    results = database.tasks_to_move_to_current_state :limit => BATCH_SIZE
end

Скручивайте BATCH_SIZE и MAX_CONTENTION_COUNT до тех пор, пока программа не будет супер-быстрой.

Update:

Оптимистическая блокировка позволяет параллельно нескольким процессорам.

По истечении таймаута блокировки (через поле locked_until) он допускает отказ при обработке перехода. Если процессор выходит из строя, другой процессор может забрать задачу после таймаута (5 минут в приведенном выше коде). Поэтому важно: а) только заблокировать задачу, когда вы собираетесь работать над ней; и b) заблокировать задачу в течение долгого времени, чтобы выполнить задачу плюс щедрую свободу действий.

Поле locked_by в основном предназначено для целей отладки (какой процесс/машина был включен?) Достаточно иметь поле locked_until, если ваш драйвер базы данных возвращает количество обновленных строк, но только если вы обновите по одной строке за раз.

Ответ 3

Управление всеми этими переходами в определенное время кажется сложным. Возможно, вы могли бы использовать что-то вроде DelayedJob для планирования переходов, чтобы не требовалось задание cron каждую минуту, и восстановление после сбоя было бы более автоматизированным?

В противном случае - если это Ruby, используется Enumerable опция?

Так же (в непроверенном псевдокоде, с упрощенными методами)

Класс ToDo

def state
  if to_do.future?
    return "Future"
  elsif to_do.current?
    return "Current"
  elsif to_do.late?
    return "Late"
  else 
    return "must not have been important"
  end
end

def future?
    Time.now.hour <= 8
end

def current?
    Time.now.hour == 9
end

def late?
    Time.now.hour >= 10
end

def self.find_current_to_dos
    self.find(:all, :conditions => " 1=1 /* or whatever */ ").select(&:state == 'Current')
end

Ответ 4

Государственные машины управляются чем-то. пользовательское взаимодействие или последний вход от потока, правильно? В этом случае время управляет конечным автоматом. Я думаю, что работа cron - правильная игра. это будут часы, ведущие машину.

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

now > current && & теперь < поздно сложно будет представлять в базе данных в качестве атрибута задачи

ID | название | future_time | current_time | late_time

1 | hello | 8: 00am | 9: 00am | 10: 00am

Ответ 5

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

Вот идея: (для чего я понял твою)

Используйте постоянные оповещения и один контролируемый процесс, чтобы "потреблять" их. Во-вторых, запросите их.

Это позволит вам:

• сохранить его простым.
• Держите его дешевым для поддержания. Во-вторых, это также будет держать вас умственно больше чтобы сделать что-то еще.
• сохранить всю логику только в коде (как и должно быть).

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

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

• сделать/поддерживать работоспособность вашей системы (более отказоустойчив) и
• позволяет вам запрашивать будущие и текущие элементы (играя с запросом диапазона времени оповещений, наилучшим образом отвечающим вашим потребностям).

Ответ 6

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

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

Сделать таблицу todo_states:

todo_id  todo_state_id    datetime  notified
1        1 (future)       8:00      0
1        2 (current)      9:00      0
1        3 (late)         10:00     0

Ваш SQL-запрос, где происходит вся реальная работа:

SELECT todo_id, MAX(todo_state_id) AS todo_state_id 
FROM todo_states
WHERE time < NOW()
GROUP BY todo_id

Текущее активное состояние всегда совпадает с выбранным вами. Если вы хотите уведомить пользователя только один раз, вставьте исходное состояние с уведомлением = 0 и набросьте его на первый выбор.

Как только задача будет выполнена, вы можете либо вставить другое состояние в таблицу todo_states, либо просто удалить все состояния, связанные с заданием, и поднять флаг "done" в элементе todo или что-то наиболее полезное в ваш случай.

Не забудьте очистить устаревшие состояния.