¿Una cola de prioridad que permite una actualización de prioridad eficiente?

Question

ACTUALIZACIÓN: Aquí está my implementation of Hashed Timing Wheels. Por favor, avíseme si tiene una idea para mejorar el rendimiento y la concurrencia. (20-ene-2009)

// Sample usage: 
public static void main(String[] args) throws Exception { 
    Timer timer = new HashedWheelTimer(); 
    for (int i = 0; i < 100000; i ++) { 
     timer.newTimeout(new TimerTask() { 
      public void run(Timeout timeout) throws Exception { 
       // Extend another second. 
       timeout.extend(); 
      } 
     }, 1000, TimeUnit.MILLISECONDS); 
    } 
} 

ACTUALIZACIÓN: He resuelto este problema mediante el uso de Hierarchical and Hashed Timing Wheels. (19-ene-2009)

Estoy tratando de implementar un temporizador de propósito especial en Java que está optimizado para el manejo del tiempo de espera. Por ejemplo, un usuario puede registrar una tarea con una línea muerta y el temporizador podría notificar el método de devolución de llamada de un usuario cuando se acabe la línea muerta. En la mayoría de los casos, una tarea registrada se realizará en un período de tiempo muy corto, por lo que la mayoría de las tareas se cancelarán (por ejemplo, task.cancel()) o reprogramadas para el futuro (por ejemplo, task.rescheduleToLater (1, TimeUnit.SECOND)) .

Quiero utilizar este temporizador para detectar una conexión de socket inactiva (por ejemplo, cerrar la conexión cuando no se recibe un mensaje en 10 segundos) y escribir tiempo de espera (por ejemplo, levantar una excepción cuando la operación de escritura no termina en 30 segundos). En la mayoría de los casos, el tiempo de espera no ocurrirá, el cliente enviará un mensaje y la respuesta se enviará a menos que haya un problema de red extraño.

No puedo usar java.util.Timer o java.util.concurrent. ScheduledThreadPoolExecutor porque suponen que se supone que la mayoría de las tareas han expirado. Si se cancela una tarea, la tarea cancelada se almacena en su pila interna hasta que se llame a ScheduledThreadPoolExecutor.purge(), y es una operación muy costosa. (O (NlogN) tal vez?)

En montones tradicionales o colas de prioridad que he aprendido en mis clases de CS, la actualización de la prioridad de un elemento era una operación costosa (O (logN) en muchos casos porque solo puede ser Esto se logra eliminando el elemento y volviéndolo a insertar con un nuevo valor de prioridad. Algunos montones como el montón Fibonacci tienen O (1) tiempo de operación decreaseKey() y min(), pero lo que necesito al menos es fast increaseKey() y min() (o decreaseKey() y max()).

¿Conoces alguna estructura de datos que esté altamente optimizada para este caso de uso particular? Una estrategia en la que estoy pensando es simplemente almacenar todas las tareas en una tabla hash y iterar todas las tareas cada segundo más o menos, pero no es tan hermoso.

Answer 1

¿Qué hay de tratar de separar la entrega del caso normal donde las cosas se completan rápidamente desde los casos de error?

Utilice una tabla hash y una cola de prioridad. Cuando se inicia una tarea, se coloca en la tabla hash y, si finaliza rápidamente, se elimina en O (1) vez.

Cada segundo explora la tabla hash y todas las tareas que llevan mucho tiempo, digamos .75 segundos, se mueven a la cola de prioridad. La cola de prioridad siempre debe ser pequeña y fácil de manejar. Esto supone que un segundo es mucho menos que los tiempos de espera que está buscando.

Si el escaneo de la tabla hash es demasiado lento, puede usar dos tablas hash, esencialmente una para los segundos pares y otra para los segundos impares. Cuando se inicia una tarea, se coloca en la tabla hash actual. Cada segundo mueve todas las tareas de la tabla hash no actual a la cola de prioridad y cambia las tablas hash para que la tabla hash actual esté ahora vacía y la tabla no actual contenga las tareas iniciadas hace uno o dos segundos.

Las opciones son mucho más complicadas que el simple uso de una cola de prioridad, pero se implementan bastante fácilmente y deben ser estables.

Answer 2

Tiene un límite estricto para la cantidad de elementos en la cola; existe un límite para los sockets TCP.

Por lo tanto, el problema está limitado. Sospecho que cualquier estructura de datos inteligente será más lenta que el uso de tipos incorporados.

Answer 3

¿Hay alguna buena razón para no usar java.lang.PriorityQueue? ¿No elimina() maneja sus operaciones de cancelación en tiempo de registro (N)? Luego, implemente su propia espera en función del tiempo hasta el elemento en la parte frontal de la cola.

Answer 4

Creo que almacenar todas las tareas en una lista y iterar a través de ellas sería lo mejor.

¿Debe ejecutar el servidor en una máquina bastante robusta para llegar a los límites donde este costo será importante?

Answer 5

Alguna combinación de estructuras hash y O (logN) debe hacer lo que usted solicite.

Estoy tentado a objetar la forma en que está analizando el problema. En su comentario anterior, usted dice

Porque la actualización ocurrirá muy frecuentemente. Digamos que estamos enviando M mensajes por conexión, entonces el tiempo total se convierte en O (MNlogN), que es bastante grande. - Trustin Lee (hace 6 horas)

que es absolutamente correcto hasta donde llega. Pero la mayoría de las personas que conozco se concentrarán en el costo por mensaje, en la teoría de que a medida que su aplicación tenga más y más trabajo por hacer, obviamente requerirá más recursos.

Así que si su aplicación tiene mil millones de sockets abiertos simultáneamente (¿es eso realmente posible?) El costo de inserción es de solo 60 comparaciones por mensaje.

Apuesto a que esta es una optimización prematura: en realidad no ha medido los cuellos de botella en su sistema con una herramienta de análisis de rendimiento como CodeAnalyst o VTune.

De todos modos, es probable que exista un número infinito de formas de hacer lo que pide, una vez que decide que ninguna estructura hará lo que quiere, y quiere una combinación de las fortalezas y debilidades de los diferentes algoritmos.

Una posibilidad es dividir el dominio de socket N en un número de cubos de tamaño B, y luego ajustar cada socket en uno de esos cubos (N/B). En ese cubo hay un montón (o lo que sea) con el tiempo de actualización O (log B). Si un límite superior en N no se fija por adelantado, pero puede variar, entonces puede crear más segmentos de forma dinámica, lo que agrega una pequeña complicación, pero es ciertamente factible.

En el peor de los casos, el temporizador de vigilancia tiene que buscar colas (N/B) para vencimientos, pero asumo ¡el temporizador de vigilancia no es necesario para matar tomas inactivas en cualquier orden en particular! Es decir, si 10 sockets permanecieron inactivos en el último segmento de tiempo, no tiene que buscar primero ese dominio para el tiempo de espera, tratarlo, encontrar el que agotó el tiempo de espera, etc. Solo tiene que escanear el conjunto de cubos (N/B) y enumerar todos los tiempos muertos.

Si no está satisfecho con una matriz lineal de depósitos, puede usar una cola de colas de prioridad, pero desea evitar actualizar esa cola en cada mensaje, o bien está de vuelta donde comenzó. En su lugar, defina un tiempo que sea menor que el tiempo de espera real.(Digamos, 3/4 o 7/8 de eso) y usted solo pone la cola de bajo nivel en la cola de alto nivel si es el tiempo más largo que excede eso.

Y a riesgo de afirmar lo obvio, no desea que sus colas ingresadas en hayan transcurrido vez. Las claves deben ser start time. Para cada registro en las colas, el tiempo transcurrido debería actualizarse constantemente, pero la hora de inicio de cada registro no cambia.

Answer 6

Su escenario específico sugiere un búfer circular para mí. Si el máximo el tiempo de espera es de 30 segundos y queremos obtener tomas al menos cada décima de segundo, luego use un buffer de 300 listas doblemente enlazadas, una por cada décima de segundo en ese período. Para 'increaseTime' en una entrada, elimínela de la lista y agréguela a la de su nuevo período de décimo segundo (ambas operaciones de tiempo constante). Cuando finaliza un período, coseche lo que quede en la lista actual (tal vez alimentándolo con un hilo de reaper) y avance el puntero de la lista actual.

Answer 7

Usa Hashed Timing Wheel - Google 'Hashed Hierarchical Timing Wheels' para obtener más información. Es una generalización de las respuestas hechas por la gente aquí. Prefiero una rueda de tiempo hash con un tamaño de rueda grande para las ruedas de distribución jerárquica.

Answer 8

Según mi mejor conocimiento (escribí un artículo sobre una nueva cola de prioridad, que también revisó los resultados anteriores), ninguna implementación de cola de prioridad obtiene los límites de los montones de Fibonacci, así como la clave de aumento de tiempo constante.

Hay un pequeño problema para obtener eso literalmente. Si pudieras obtener la tecla aumentar en O (1), entonces podrías obtener eliminar en O (1) - simplemente aumenta la tecla a + infinito (puedes manejar la cola llena de muchos + infinitos usando algunos trucos de amortización estándar)) Pero si find-min también es O (1), eso significa que delete-min = find-min + delete se convierte en O (1). Eso es imposible en una cola de prioridad basado en la comparación debido a la cota de clasificación implica (inserte todo, a continuación, quitar uno por uno) que

n * insert + n * delete-min > n log n.

El punto aquí es que si quieres una prioridad en colas para apoyar aumento de clave en O (1), entonces debe aceptar una de las siguientes sanciones:

• no haber comparación basado. En realidad, esta es una muy buena forma de evitar cosas, p. vEB trees.
• Acepte O (log n) para inserciones y también O (n log n) para make-heap (dado n valores iniciales). Esto apesta.
• Acepte O (log n) para find-min. Esto es totalmente aceptable si en realidad nunca hace find-min (sin una eliminación adjunta).

Pero, de nuevo, según mi leal saber y entender, nadie ha hecho la última opción. Siempre lo he visto como una oportunidad para obtener nuevos resultados en un área bastante básica de estructuras de datos.

Answer 9

Hay una manera muy simple de hacer todas las inserciones y elimina en O (1), aprovechando el hecho de que 1) prioridad se basa en el tiempo y 2) es probable que tenga un número pequeño y fijo de tiempos de espera.

1. Crea una cola FIFO regular para contener todas las tareas que exceden el tiempo en 10 segundos.Debido a que todas las tareas tienen duraciones de tiempo de espera idénticas, puede simplemente insertarlas hasta el final y eliminarlas desde el principio para mantener ordenada la cola.
2. Crea otra cola FIFO para tareas con una duración de tiempo de espera de 30 segundos. Crea más colas para otras duraciones de tiempo de espera.
3. Para cancelar, quite el elemento de la cola. Esto es O (1) si la cola se implementa como una lista vinculada.
4. La reprogramación se puede realizar como cancelar-insertar, ya que ambas operaciones son O (1). Tenga en cuenta que las tareas pueden reprogramarse en diferentes colas.
5. Finalmente, para combinar todas las colas FIFO en una única cola de prioridad general, haga que el encabezado de cada cola FIFO participe de forma regular. El jefe de este montón será la tarea con el tiempo de expiración más próximo de TODAS las tareas.

Si tiene un número m de duraciones diferentes de tiempo de espera, la complejidad de cada operación de la estructura general es O (log m). La inserción es O (log m) debido a la necesidad de buscar en qué cola insertar. Remove-min es O (log m) para restaurar el montón. La cancelación es O (1) pero el caso más desfavorable O (log m) si cancela el encabezado de una cola. Como m es un número pequeño y fijo, O (log m) es esencialmente O (1). No escala con el número de tareas.