Hispanopedia Wiki
Articulo de referencia

equidad en los recursos dominantes

La equidad de recursos dominantes ( DRF , por sus siglas en inglés) es una regla para la división equitativa . Es particularmente útil para dividir los recursos informáticos ent...

Hispanopedia WikiContenido en espanolLectura gratuita

La equidad de recursos dominantes ( DRF , por sus siglas en inglés) es una regla para la división equitativa . Es particularmente útil para dividir los recursos informáticos entre los usuarios en entornos de computación en la nube , donde cada usuario puede requerir una combinación diferente de recursos. La DRF fue presentada por Ali Ghodsi , Matei Zaharia , Benjamin Hindman, Andy Konwinski , Scott Shenker e Ion Stoica en 2011. [ 1 ]

Motivación

En un entorno con un único recurso, un criterio ampliamente utilizado es la equidad max-min , que busca maximizar la cantidad mínima de recursos asignados a un usuario. Sin embargo, en la computación en la nube, es necesario compartir diferentes tipos de recursos, como memoria, CPU, ancho de banda y espacio en disco. Los planificadores equitativos anteriores, como los de Apache Hadoop , reducían la configuración de múltiples recursos a una de un solo recurso definiendo nodos con una cantidad fija de cada recurso (por ejemplo, 4 CPU, 32 MB de memoria, etc.) y dividiendo las ranuras en fracciones de nodos. Pero este método es ineficiente, ya que no todos los usuarios necesitan la misma proporción de recursos. Por ejemplo, algunos usuarios necesitan más CPU, mientras que otros necesitan más memoria. Como resultado, la mayoría de las tareas subutilizan o sobreutilizan sus recursos.

El algoritmo DRF resuelve el problema maximizando la cantidad mínima del recurso dominante asignado a un usuario (luego la segunda cantidad mínima, etc., en orden leximin ). El recurso dominante puede ser diferente para cada usuario. Por ejemplo, si el usuario A ejecuta tareas que consumen muchos recursos de CPU y el usuario B ejecuta tareas que consumen muchos recursos de memoria, DRF intentará igualar la proporción de CPU asignada al usuario A y la proporción de memoria asignada al usuario B.

Definición

Hay m recursos. Las capacidades totales de los recursos son r 1 ,..., r m .

Hay n usuarios. Cada usuario ejecuta tareas individuales . Cada tarea tiene un vector de demanda ( d1 , ..., dm ) , que representa la cantidad que necesita de cada recurso. Se asume implícitamente que la utilidad de un usuario es igual al número de tareas que puede realizar. Por ejemplo, si el usuario A ejecuta tareas con el vector de demanda [1 CPU, 4 GB de RAM] y recibe 3 CPU y 8 GB de RAM, entonces su utilidad es 2, ya que solo puede realizar 2 tareas. De manera más general, la utilidad de un usuario que recibe x1 , ... , xm recursos es min j ( xj / dj ) , es decir, los usuarios tienen utilidades de Leontief .

Los vectores de demanda se normalizan a fracciones de las capacidades. Por ejemplo, si el sistema tiene 9 CPU y 18 GB de RAM, el vector de demanda anterior se normaliza a [1/9 CPU, 2/9 GB]. Para cada usuario, el recurso con la mayor fracción de demanda se denomina recurso dominante . En el ejemplo anterior, el recurso dominante es la memoria, ya que 2/9 es la fracción más grande. Si el usuario B ejecuta una tarea con un vector de demanda [3 CPU, 1 GB], que se normaliza a [1/3 CPU, 1/18 GB], entonces su recurso dominante es la CPU.

El DRF busca encontrar el máximo x tal que todos los agentes puedan recibir al menos x de su recurso dominante. En el ejemplo anterior, este máximo x es 2/3:

  • El usuario A recibe 3 tareas, que requieren 3/9 de CPU y 2/3 de GB.
  • El usuario B recibe 2 tareas, que requieren 2/3 de la CPU y 1/9 de GB.

El valor máximo de x se puede encontrar resolviendo un programa lineal; véase Optimización lexicográfica max-min . Alternativamente, el DRF se puede calcular secuencialmente. [ 1 ] : Algoritmo 1 El algoritmo rastrea la cantidad de recurso dominante utilizado por cada usuario. En cada ronda, encuentra un usuario con el menor recurso dominante asignado hasta el momento y le asigna la siguiente tarea. Nótese que este procedimiento permite que el mismo usuario ejecute tareas con diferentes vectores de demanda.

Propiedades

El DRF presenta varias ventajas sobre otras políticas de asignación de recursos.

  1. Proporcionalidad : cada usuario recibe al menos la misma cantidad de recursos que podría obtener en un sistema en el que todos los recursos se reparten equitativamente entre los usuarios (los autores denominan a esta condición "incentivo para compartir").
  2. Resistencia a la manipulación : un usuario no puede obtener una mayor asignación mintiendo sobre sus necesidades. La resistencia a la manipulación es importante, ya que la experiencia de los operadores de la nube demuestra que los usuarios intentan manipular los servidores para obtener mejores asignaciones.
  3. Ausencia de envidia : ningún usuario preferiría la asignación de otro usuario.
  4. Eficiencia de Pareto : ninguna otra asignación es mejor para algunos usuarios y no peor para nadie.
  5. Monotonicidad de la población : cuando un usuario abandona el sistema, las asignaciones de los usuarios restantes no disminuyen.

Cuando hay un único recurso que es un recurso cuello de botella (muy demandado por todos los usuarios), DRF se reduce a equidad max-min .

Sin embargo, DRF viola la monotonicidad de los recursos : cuando se agregan recursos al sistema, algunas asignaciones pueden disminuir.

Extensiones

El DRF ponderado es una extensión del DRF a entornos en los que diferentes usuarios tienen diferentes ponderaciones (que representan sus diferentes derechos ). [ 1 ] : 4.3

Parkes, Procaccia y Shah [ 2 ] extienden formalmente el DRF ponderado a un escenario en el que algunos usuarios no necesitan todos los recursos (es decir, pueden tener una demanda de 0 para algún recurso). Demuestran que la versión extendida aún satisface la proporcionalidad, la eficiencia de Pareto, la ausencia de envidia, la resistencia a la estrategia e incluso la resistencia a la estrategia grupal . Por otro lado, muestran que el DRF puede generar un bienestar social utilitario deficiente, es decir, la suma de utilidades puede ser solo 1/ m del óptimo. Sin embargo, demuestran que cualquier mecanismo que satisfaga una de las propiedades de proporcionalidad, ausencia de envidia o resistencia a la estrategia puede sufrir del mismo bajo bienestar utilitario. También extienden el DRF al escenario en el que las demandas de los usuarios son indivisibles (como en la asignación justa de ítems ). Para el escenario indivisible, relajan la ausencia de envidia a EF1. Demuestran que la resistencia a la estrategia es incompatible con PO+EF1 o con PO+proporcionalidad. Sin embargo, un mecanismo llamado SequentialMinMax satisface la eficiencia, la proporcionalidad y EF1.

Wang, Li y Liang [ 3 ] presentan DRFH, una extensión de DRF a un sistema con varios servidores heterogéneos.

Implementación

DRF se implementó por primera vez en Apache Mesos , un gestor de recursos de clúster, y dio como resultado un mejor rendimiento y una mayor equidad que los esquemas de reparto equitativo utilizados anteriormente.

Véase también

Referencias

  1. 1 2 3 "Equidad de los recursos dominantes: Asignación justa de múltiples tipos de recursos" . 2011.
  2. ↑ Parkes, David C.; Procaccia, Ariel D.; Shah, Nisarg (27 de marzo de 2015). "Más allá de la equidad de recursos dominantes: extensiones, limitaciones e indivisibilidades" . ACM Transactions on Economics and Computation . 3 (1): 3:1–3:22. doi : 10.1145/2739040 . ISSN 2167-8375 . 
  3. ↑ Wang, Wei; Li, Baochun; Liang, Ben (2014). Equidad en la asignación de recursos dominantes en sistemas de computación en la nube con servidores heterogéneos . pp. 583–591 . arXiv : 1308.0083 . doi : 10.1109/INFOCOM.2014.6847983 . ISBN  978-1-4799-3360-0.