Отслеживание прогресса между очередями на карте - программирование
Подтвердить что ты не робот

Отслеживание прогресса между очередями на карте

В настоящее время у меня есть две очереди и предметы, перемещающиеся между ними. Первоначально элемент попадает в firstQueue, затем один из трех выделенных потоков перемещает его в secondQueue и, наконец, другой выделенный поток удаляет его. Эти шаги, очевидно, включают в себя некоторую обработку. Мне нужно получить статус любого элемента (IN_FIRST, AFTER_FIRST, IN_SECOND, AFTER_SECOND или ABSENT), и я внедрил его вручную, выполнив обновление statusMap где очередь изменяется, как

while (true) {
    Item i = firstQueue.take();
    statusMap.put(i, AFTER_FIRST);
    process(i);
    secondQueue.add(i);
    statusMap.put(i, IN_SECOND);
}

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

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

Интересно, есть ли хорошее решение, обобщаемое для нескольких очередей?

4b9b3361

ОТВЕТЫ

Ответ 1

Имеет ли смысл обертывать очереди логикой для управления статусом Item?

public class QueueWrapper<E> implements BlockingQueue<E> {
    private Queue<E> myQueue = new LinkedBlockingQueue<>();
    private Map<E, Status> statusMap;

    public QueueWrapper(Map<E, Status> statusMap) {
        this.statusMap = statusMap;
    }

    [...]
    @Override
    public E take() throws InterruptedException {
        E result = myQueue.take();
        statusMap.put(result, Status.AFTER_FIRST);
        return result;
    }

Таким образом, управление статусом всегда связано с операциями очереди (и содержит)...

Очевидно, что statusMap необходимо синхронизировать, но это все равно будет проблемой.

Ответ 2

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

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

Мое предложение можно увидеть на рисунке ниже:

enter image description here

Согласно этой модели и вашему примеру, мы можем сделать:

package stackoverflow;

import java.util.concurrent.LinkedBlockingQueue;

import stackoverflow.item.ItemState;
import stackoverflow.task.CreatingTask;
import stackoverflow.task.FirstMovingTask;
import stackoverflow.task.SecondMovingTask;

public class Main {

    private static void startTask(String name, Runnable r){
        Thread t = new Thread(r, name);
        t.start();
    }

    public static void main(String[] args) {
        //create queues
        LinkedBlockingQueue<ItemState> firstQueue = new LinkedBlockingQueue<ItemState>();
        LinkedBlockingQueue<ItemState> secondQueue = new LinkedBlockingQueue<ItemState>();
        //start three threads
        startTask("Thread#1", new CreatingTask(firstQueue));
        startTask("Thread#2", new FirstMovingTask(firstQueue, secondQueue));
        startTask("Thread#3", new SecondMovingTask(secondQueue));
    }
}

Каждая задача выполняет операции op() согласно нижеприведенному утверждению на ItemState:

один из трех выделенных потоков перемещает его на secondQueue, и, наконец, другой выделенный поток удаляет его.

ItemState - неизменяемый объект, содержащий Item и ваше State. Это обеспечивает согласованность между значениями Item и State.

ItemState имеет подтверждение о следующем состоянии, создающем механизм самоконтролируемого состояния:

public class FirstMovingTask {
    //others codes
    protected void op() {
            try {
                //dequeue
                ItemState is0 = new ItemState(firstQueue.take());
                System.out.println("Item " + is0.getItem().getValue() + ": " + is0.getState().getValue());
                //process here
                //enqueue
                ItemState is1 = new ItemState(is0);
                secondQueue.add(is1);
                System.out.println("Item " + is1.getItem().getValue() + ": " + is1.getState().getValue());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    //others codes
}

При выполнении ItemState:

public class ItemStateImpl implements ItemState {
    private final Item item;
    private final State state;

    public ItemStateImpl(Item i){
        this.item = i;
        this.state = new State();
    }

    public ItemStateImpl(ItemState is) {
        this.item = is.getItem();
        this.state = is.getState().next();
    }

    // gets attrs
}

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

Результаты:

Item 0: AFTER_FIRST
Item 0: IN_FIRST
Item 0: IN_SECOND
Item 0: AFTER_SECOND
Item 1: IN_FIRST
Item 1: AFTER_FIRST
Item 1: IN_SECOND
Item 1: AFTER_SECOND
Item 2: IN_FIRST
Item 2: AFTER_FIRST
Item 2: IN_SECOND
... others

UPDATE (06/07/2018): анализ использования карты для поиска Поиск на карте с использованием значений равных, таких как компаратор, может не работать, потому что обычное отображение между значениями и идентификатором (ключ/хэш) не является взаимно однозначным (см. Рисунок пыльник). Таким образом, необходимо создать отсортированный список для значений поиска, который приводит к O (n) (худший случай).

enter image description here

с Item.getValuesHashCode():

private int getValuesHashCode(){
  return new HashCodeBuilder().append(value).hashCode();
}

В этом случае вы должны сохранить Vector<ItemState> вместо Item и использовать ключ, как результат getValuesHashCode. Измените механизм управления состоянием для сохранения первой ссылки на Item и state current. Смотрите ниже:

//Main.class
public static void main(String[] args) {
    ... others code ...

    //references repository
    ConcurrentHashMap<Integer, Vector<ItemState>> statesMap = new ConcurrentHashMap<Integer, Vector<ItemState>>();
    //start three threads
    startTask("Thread#1", new CreatingTask(firstQueue, statesMap));

    ... others code ...
}

//CreateTask.class
protected void op() throws InterruptedException {
    //create item
    ItemState is = new ItemStateImpl(new Item(i++, NameGenerator.name()));
    //put in monitor and enqueue
    int key = is.getHashValue();
    Vector<ItemState> items = map.get(key);
    if (items == null){
        items = new Vector<>();
        map.put(key, items);
    }
    items.add(is);
    //enqueue
    queue.put(is);
}

//FirstMovingTask.class
protected void op() throws InterruptedException{
    //dequeue
    ItemState is0 = firstQueue.take();
    //process
    ItemState is1 = process(is0.next());
    //enqueue 
    secondQueue.put(is1.next());
}

//ItemState.class
public ItemState next() {
    //required for consistent change state
    synchronized (state) {
        state = state.next();
        return this;
    }
}

Для поиска вы должны использовать concurrentMapRef.get (ключ). Результатом будет ссылка обновленного ItemState.

Результаты моих тестов для:

# key = hash("a")
# concurrentMapRef.get(key)
...
Item#7#0    : a - IN_FIRST 
... many others lines
Item#7#0    : a - AFTER_FIRST 
Item#12#1   : a - IN_FIRST 
... many others lines
Item#7#0    : a - IN_SECOND 
Item#12#1   : a - IN_FIRST 
... many others lines
Item#7#0    : a - AFTER_SECOND 
Item#12#1   : a - IN_FIRST

Подробнее в коде: https://github.com/ag-studies/stackoverflow-queue

ОБНОВЛЕНО В 06/09/2018: редизайн

Обобщая этот проект, я могу понять, что государственная машина - это что-то вроде:

enter image description here

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

Это сохраняет прежнюю идею и создает более четкую концепцию. Видеть это:

enter image description here

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

Итак, отвечая на ваш вопрос:

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

  • Выполнение выполняется, за исключением запуска следующего()

  • Государство всегда согласовано (для вашей проблемы)

  • В этой модели можно использовать любой тип очереди, любое количество заданий/очередей и любое количество состояний.

  • Кроме того, это красиво!

Ответ 3

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

public class ItemWrapper<E> {
   E item;
   Status status;
   public ItemWrapper(Item i, Status s){ ... }
   public setStatus(Status s){ ... }
   // not necessary if you use a queue wrapper (see queue wrapper)
   public boolean equals(Object obj) {
     if ( obj instanceof ItemWrapper)
       return item.equals(((ItemWrapper) obj).item) 
     return false;
   }
   public int hashCode(){
     return item;
   }
}
...
process(item) // process update status in the item
...

Вероятно, лучший ответ, уже ответивший, должен иметь QueueWrapper, который обновляет статус очереди. Для развлечения я не использую карту состояния, но я использую элемент itemblrapper, который кажется более чистым (также отображается карта состояния).

public class QueueWrapper<E> implements Queue<E> {
  private Queue<ItemWrapper<E>> myQueue;
  static private Status inStatus; // FIRST
  static private Status outStatus; // AFTER_FIRST
  public QueueWrapper(Queue<E> myQueue, Status inStatus, Status outStatus) {...}
  @Override
  public boolean add(E e) {
    return myQueue.add(new ItemWrapper(e, inStatus));
  }
  @Override
  public E remove(){
    ItemWrapper<E> result = myQueue.remove();
    result.setStatus(outStatus)
    return result.item;
  }
  ...  
  }

Вы также можете использовать AOP для обновления статуса в своих очередях без изменения очередей (карта состояния должна быть более подходящей, чем itemwrapper).

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

Ответ 4

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

Я расскажу, как это будет работать с высокого уровня, и если вам нужно, я могу добавить код.

По сути, у вас будет Set будет идти с каждой из ваших очередей. Вы обернете свои очереди в объект, чтобы при удалении элемента произошли некоторые вещи

  1. Элемент удален из очереди
  2. Элемент добавляется к соответствующему набору
  3. Запланирована задача (лямбда, содержащая атомное логическое значение (по умолчанию false)). При запуске он удалит элемент из набора, и если логическое значение false, верните его в очередь
  4. Элемент и обертка вокруг логического значения возвращаются вызывающему

После process(i); завершается, ваш код укажет подтверждение квитанции на обертку, а оболочка удалит элемент из набора и сделает логическое значение false.

Метод возврата статуса будет просто проверять, в какой очереди или установить элемент.

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