Equidad dominante en los recursos

La equidad de recursos dominante (DRF, por sus siglas en inglés) es una regla para la división justa . 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 máxima-mínima , que tiene como objetivo maximizar la cantidad mínima de recursos que se le da a un usuario. Pero en la computación en la nube, se requiere compartir diferentes tipos de recursos, como: memoria, CPU, ancho de banda y espacio en disco. Los programadores justos anteriores, como en Apache Hadoop , redujeron la configuración de múltiples recursos a una configuración de un solo recurso al definir nodos con una cantidad fija de cada recurso (por ejemplo, 4 CPU, 32 MB de memoria, etc.) y dividir las ranuras que son 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.

DRF resuelve el problema maximizando la cantidad mínima del recurso dominante otorgado a un usuario (luego el segundo mínimo, etc., en orden leximin ). El recurso dominante puede ser diferente para distintos usuarios. Por ejemplo, si el usuario A ejecuta tareas que consumen mucha CPU y el usuario B ejecuta tareas que consumen mucha memoria, DRF intentará igualar la porción de CPU otorgada al usuario A y la porción de memoria otorgada al usuario B.

Definición

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

Hay n usuarios. Cada usuario ejecuta tareas individuales . Cada tarea tiene un vector de demanda ( d ₁ ,.., d _m ), que representa la cantidad que necesita de cada recurso. Se supone 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 vector de demanda [1 CPU, 4 GB RAM] y recibe 3 CPU y 8 GB 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 x ₁ ,..., x _m recursos es min _j ( x _j / d _j ), 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, entonces el vector de demanda anterior se normaliza a [1/9 CPU, 2/9 GB]. Para cada usuario, el recurso con la fracción de demanda más alta 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 está normalizado a [1/3 CPU, 1/18 GB], entonces su recurso dominante es la CPU.

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

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

El máximo x se puede encontrar resolviendo un programa lineal; consulte Optimización máxima-mínima lexicográfica . 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 recurso dominante asignado más pequeño hasta el momento y asigna la siguiente tarea de este usuario. Tenga en cuenta que este procedimiento permite que el mismo usuario ejecute tareas con diferentes vectores de demanda.

Propiedades

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

Proporcionalidad : cada usuario recibe al menos tantos recursos como podría obtener en un sistema en el que todos los recursos se reparten equitativamente entre los usuarios (los autores llaman a esta condición "incentivo de reparto").
A prueba de estrategias : un usuario no puede obtener una asignación mayor mintiendo sobre sus necesidades. La a prueba de estrategias es importante, ya que la evidencia de los operadores de la nube muestra que los usuarios intentan manipular los servidores para obtener mejores asignaciones.
Sin envidia : ningún usuario preferiría la asignación de otro usuario.
Eficiencia de Pareto : ninguna otra asignación es mejor para algunos usuarios ni peor para ninguno.
Monotonía de la población : cuando un usuario abandona el sistema, las asignaciones de los usuarios restantes no disminuyen.

Cuando hay un solo recurso que es un recurso de cuello de botella (altamente demandado por todos los usuarios), DRF se reduce a la equidad máxima-mínima .

Sin embargo, DRF viola la monotonía de los recursos : cuando se agregan recursos al sistema, algunas asignaciones podrían disminuir.

Extensiones

El DRF ponderado es una extensión del DRF para configuraciones en las que los distintos usuarios tienen distintos pesos (que representan sus diferentes derechos ). ^[1]^{: 4.3}

Parkes, Procaccia y Shah ^[2] extienden formalmente el DRF ponderado a un entorno en el que algunos usuarios no necesitan todos los recursos (es decir, pueden tener una demanda 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 imposibilidad de estrategia e incluso la imposibilidad de estrategia de grupo . Por otro lado, muestran que el DRF puede producir un bajo bienestar social utilitario, es decir, la suma de utilidades puede ser solo 1/ m del óptimo. Sin embargo, demuestran que cualquier mecanismo que satisfaga una de las siguientes condiciones: proporcionalidad, ausencia de envidia o imposibilidad de estrategia puede sufrir el mismo bajo bienestar utilitario. También extienden el DRF al entorno en el que las demandas de los usuarios son indivisibles (como en la asignación justa de ítems ). Para el entorno indivisible, relajan la ausencia de envidia a EF1. Muestran que la imposibilidad de 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 administrador de recursos de clúster, y generó un mejor rendimiento y equidad que los esquemas de distribución justa utilizados anteriormente.

Véase también

Referencias

^ abc "Equidad de recursos dominantes: asignación justa de múltiples tipos de recursos". 2011.
^ Parkes, David C.; Procaccia, Ariel D.; Shah, Nisarg (27 de marzo de 2015). "Más allá de la equidad de los 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.
^ Wang, Wei; Li, Baochun; Liang, Ben (2014). Equidad de recursos dominante 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. Consultado el 20 de diciembre de 2023 .

[:0-1] "Equidad de 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 los 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 de recursos dominante 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. Consultado el 20 de diciembre de 2023 .