Optimieren der Cloud-Nutzung mithilfe von Problemen beim Packen von Behältern

Wenn Sie jetzt eine Cloud wie AWS, Azure oder GCP verwenden, fragen Sie sich möglicherweise, welche Anwendung aus Effizienzgründen auf einer virtuellen Maschine mit welcher Größe aufgeführt werden soll. Da die CPU-, Speicher- und Festplattennutzung der Anwendung bekannt ist, in welcher Größe die virtuelle Maschine platziert werden soll, ob sie kolokalisiert, verteilt usw. werden soll. Es gibt. Es scheint, dass Ingenieure mit einer langen Erfahrung in der Nutzung der Cloud aufgrund ihrer Erfahrung wissen, welche Größe sie wählen müssen. Diesmal änderte ich jedoch meinen Ansatz ein wenig und fragte mich, ob ich eine Lösung als Optimierungsproblem finden könnte.

In den folgenden Situationen sollte beispielsweise eine Anwendungsgröße in welcher virtuellen Maschine platziert werden, um effizient zu sein?

１.png

Als allererstes

Das Optimierungsproblem schien interessant zu sein, also dachte ich nach dem Studium über ein Problem nach, das mir vertraut war. Da die Optimierungshistorie eine Woche beträgt, weisen Sie bitte auf Fehler oder Ratschläge hin.

Die folgenden Bücher wurden zum Lernen verwendet. [Optimierung / statistische Analyse / maschinelles Lernen für Business Analytics-Praktiker in Python-Sprache](https://www.amazon.co.jp/Python%E8%A8%80%E8%AA%9E%E3%81] % AB% E3% 82% 88% E3% 82% 8B% E3% 83% 93% E3% 82% B8% E3% 83% 8D% E3% 82% B9% E3% 82% A2% E3% 83% 8A % E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AF% E3% 82% B9-% E5% AE% 9F% E5% 8B% 99% E5% AE% B6% E3% 81% AE% E3% 81% 9F% E3% 82% 81% E3% 81% AE% E6% 9C% 80% E9% 81% A9% E5% 8C% 96% E3% 83% BB% E7% B5% B1% E8% A8% 88% E8% A7% A3% E6% 9E% 90% E3% 83% BB% E6% A9% 9F% E6% A2% B0% E5% AD% A6% E7% BF% 92-% E4% B9% 85% E4% BF% 9D-% E5% B9% B9% E9% 9B% 84 / dp / 4764905167 / ref = sr_1_1? Ie = UTF8 & qid = 1495359888 & sr = 8-1 & keywords = python +% E3% 83% 93% E3% 82% B8% E3% 83% 8D% E3% 82% B9% E3% 83% BB% E3% 82% A2% E3% 83% 8A% E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AF% E3% 82% B9)

Problemstellung

Dieses Mal möchte ich aufgrund der Auflistung der erforderlichen Anzahl von Anwendungen auf der virtuellen Maschine in der Cloud die Konfiguration mit den niedrigsten Kosten als Problem beim Packen von Behältern finden.

Das Problem der Behälterverpackung ist ein Kombinationsoptimierungsproblem, bei dem die Mindestanzahl der erforderlichen Behälter ermittelt wird, wenn ein Behälter (Karton, Flasche, Behälter) mit Gepäck verpackt wird (Gewicht und Anzahl sind festgelegt). Wenn Sie beispielsweise umziehen, packen Sie Ihr Gepäck wahrscheinlich in Pappe, aber Sie müssen die Verpackungsmethode lösen, um die Anzahl der Pappe zu minimieren.

２.png

Wenn Sie Ihr Gepäck in einen Karton packen möchten, berücksichtigen Sie das Volumen und Gewicht des Gepäcks in Bezug auf das Volumen (Breite x Länge x Höhe) und die Ladekapazität des Kartons. Als ich das sah, hatte ich das Gefühl, dass ich die Verwendung virtueller Maschinen in der Cloud optimieren könnte, indem ich Gepäck als Anwendung, Pappe als virtuelle Maschine ersetze und Volumen und Gewicht durch CPU, RAM, Festplatte und Kosten ersetze. Das ist der Anfang.

Umgebung

Ich möchte das Optimierungsproblem mit Python lösen. Python bietet eine Vielzahl nützlicher Bibliotheken zur Lösung von Optimierungsproblemen, die hier ausführlich erläutert werden. Python in Optimierung

Diesmal habe ich openopt mit Python 3.5 (Anaconda) verwendet. Das Betriebssystem ist CentOS 7.3. Openopt ist eine Bibliothek, die Modelle für die mathematische Optimierung erstellt.

So installieren Sie openopt in dieser Umgebung:

conda install --channel https://conda.anaconda.org/cachemeorg funcdesigner openopt
pip install cvxopt
pip install glpk

Dinge die zu tun sind

Dieses Mal werden wir die Anwendung in drei Typen unterteilen. Kleine Anwendungen, mittlere Anwendungen, große Anwendungen. Die Verwendung jeder Ressource ist wie folgt.

Kleine Anwendung	Mittlere Anwendung	Große Anwendung
CPU: 0.2	CPU: 0.5	CPU: 2.4
RAM: 256MB	RAM: 512MB	RAM: 2048MB
DISK: 1GB	DISK: 10GB	DISK: 40GB

Verwenden Sie das Problem beim Verpacken von Behältern, um herauszufinden, welche der folgenden EC2-Instanzgrößen zum günstigsten Preis verpackt werden sollten.

M4.4xlarge	R3.2xlarge	C4.2xlarge
CPU: 16vCPU	CPU: 8vCPU	CPU: 8vCPU
RAM: 64GB	RAM: 61GB	RAM: 15GB
Disk: 100GB	Disk: 100GB	Disk: 100GB
$1.032 / hour	$0.798 / hour	$0.504 / hour

Der Stückpreis ist der Preis bei Verwendung einer Linux-On-Demand-Instanz in der Region Tokio ab heute (21. Mai 2017). Referenz Auch die Disc-Kosten (EBS) sind nicht enthalten.

Programm

Das vollständige Programm finden Sie hier.

# import openopt
from openopt import *

#Legen Sie die Anzahl der kleinen, mittleren und großen Anwendungen fest.
small_num = 20
med_num = 12
large_num = 9

apps = []

#Stellen Sie die Ressourcennutzung für jede Anwendung diktieren und fügen Sie sie der Liste hinzu.
for i in range(small_num):
    small_app = {
        'name': 'small%d' % i,
        'cpu': 0.2,
        'mem': 256,
        'disk': 1
        }
    apps.append(small_app)

for i in range(med_num):
    med_app = {
        'name': 'medium%d' % i,
        'cpu': 0.5,
        'mem': 512,
        'disk': 10
        }
    apps.append(med_app)
    
for i in range(large_num):
    large_app = {
        'name': 'large%d' % i,
        'cpu': 2.4,
        'mem': 2048,
        'disk': 40
        }
    apps.append(large_app)


#Legt die Größe der AWS EC2-Instanz fest.
#Jede Ressource wird mit 9 multipliziert, da das Betriebssystem 10 der Ressourcen ist%Dies liegt daran, dass davon ausgegangen wird, dass
instance_sizes = [
    {
        'name': 'm4.x4large',
        'cost': 1.032 * 24 * 30,
        'size': {
            'cpu': 16 * 0.9,
            'mem': 64 * 1024 * 0.9, 
            'disk': 1000 * 0.9
        }
    },
    {
        'name': 'r3.2xlarge',
        'cost': 0.798 * 24 * 30,
        'size': {
            'cpu': 8 * 0.9,
            'mem': 61 * 1024 * 0.9, 
            'disk': 1000 * 0.9
        }
    },
    {
        'name': 'c4.2xlarge',
        'cost': 0.504 * 24 * 30,
        'size': {
            'cpu': 8 * 0.9,
            'mem': 15 * 1024 * 0.9, 
            'disk': 1000 * 0.9
        }
    }
]

#Es ist Müllverpackung.
#Wir verwenden eine Funktion namens BPP von openopt.
def bin_pack_instance(apps, instance_size):
    cost = instance_size['cost']    
    p = BPP(apps, instance_size['size'], goal = 'min')
    r = p.solve('glpk', iprint = 0)
    instances = len(r.xf)
    total_cost = instances * cost
    return r, instances, total_cost

#Ich werde das machen.
#Behälterverpackung für jede Instanzgröße und finden Sie die billigste.
if __name__ == '__main__':
    list_cost = []
    for instance in instance_sizes:
        r, instances, total_cost = bin_pack_instance(apps, instance)
        list_cost.append({'instance': instance['name'], 'total_cost': total_cost})

        print("\r") 
        print("Bin packing for : {0}".format(instance['name']))
        print("Total number of apps is " + str(len(apps)))
        print("Total {0} instance used is {1}".format(instance['name'], instances))
        print("Total cost is {0}".format(total_cost))

        for i,s in enumerate(r.xf):
            print ("Instance {0} contains {1} apps".format(i, len(s)))
            print("\t CPU: {0}vCPU\t RAM: {1}MB\t Disk: {2}GB"
                  .format(r.values['cpu'][i], r.values['mem'][i], r.values['disk'][i]))
            print("\t Contains: {0}".format(r.xf[i]))

        print("\r")  
    
    print("Result: {0}".format(list_cost))

Das Ergebnis ist wie folgt.

------------------------- OpenOpt 0.5625 -------------------------
problem: unnamed   type: MILP    goal: min
solver: glpk
  iter  objFunVal  log10(maxResidual)  
    0  0.000e+00               0.00 
    1  0.000e+00            -100.00 
istop: 1000 (optimal)
Solver:   Time Elapsed = 0.12 	CPU Time Elapsed = 0.12
objFuncValue: 3 (feasible, MaxResidual = 0)

Bin packing for : m4.x4large
Total number of apps is 41
Total m4.x4large instance used is 3
Total cost is 2229.12
Instance 0 contains 18 apps
	 CPU: 14.200000000000001vCPU	 RAM: 13312.0MB	 Disk: 228.0GB
	 Contains: ('small0', 'small3', 'small4', 'small5', 'small6', 'small7', 'small8', 'small13', 'medium0', 'medium1', 'medium2', 'medium3', 'medium4', 'medium5', 'large3', 'large4', 'large6', 'large7')
Instance 1 contains 17 apps
	 CPU: 14.4vCPU	 RAM: 13312.0MB	 Disk: 212.0GB
	 Contains: ('small1', 'small2', 'small9', 'small10', 'small11', 'small12', 'small14', 'small15', 'small16', 'small17', 'small18', 'small19', 'large0', 'large1', 'large2', 'large5', 'large8')
Instance 2 contains 6 apps
	 CPU: 3.0vCPU	 RAM: 3072.0MB	 Disk: 60.0GB
	 Contains: ('medium6', 'medium7', 'medium8', 'medium9', 'medium10', 'medium11')


------------------------- OpenOpt 0.5625 -------------------------
problem: unnamed   type: MILP    goal: min
solver: glpk
  iter  objFunVal  log10(maxResidual)  
    0  0.000e+00               0.00 
    1  0.000e+00            -100.00 
istop: 1000 (optimal)
Solver:   Time Elapsed = 0.24 	CPU Time Elapsed = 0.23
objFuncValue: 5 (feasible, MaxResidual = 0)

Bin packing for : r3.2xlarge
Total number of apps is 41
Total r3.2xlarge instance used is 5
Total cost is 2872.8
Instance 0 contains 3 apps
	 CPU: 7.199999999999999vCPU	 RAM: 6144.0MB	 Disk: 120.0GB
	 Contains: ('large0', 'large4', 'large7')
Instance 1 contains 11 apps
	 CPU: 7.199999999999999vCPU	 RAM: 6912.0MB	 Disk: 107.0GB
	 Contains: ('small5', 'small6', 'small7', 'small8', 'small9', 'small18', 'small19', 'medium0', 'medium1', 'large1', 'large2')
Instance 2 contains 13 apps
	 CPU: 7.0vCPU	 RAM: 6912.0MB	 Disk: 91.0GB
	 Contains: ('small0', 'small1', 'small2', 'small10', 'small11', 'small12', 'small13', 'small14', 'small15', 'small16', 'small17', 'large5', 'large6')
Instance 3 contains 8 apps
	 CPU: 7.199999999999999vCPU	 RAM: 6656.0MB	 Disk: 122.0GB
	 Contains: ('small3', 'small4', 'medium2', 'medium3', 'medium4', 'medium5', 'large3', 'large8')
Instance 4 contains 6 apps
	 CPU: 3.0vCPU	 RAM: 3072.0MB	 Disk: 60.0GB
	 Contains: ('medium6', 'medium7', 'medium8', 'medium9', 'medium10', 'medium11')


------------------------- OpenOpt 0.5625 -------------------------
problem: unnamed   type: MILP    goal: min
solver: glpk
  iter  objFunVal  log10(maxResidual)  
    0  0.000e+00               0.00 
    1  0.000e+00            -100.00 
istop: 1000 (optimal)
Solver:   Time Elapsed = 0.14 	CPU Time Elapsed = 0.14
objFuncValue: 5 (feasible, MaxResidual = 0)

Bin packing for : c4.2xlarge
Total number of apps is 41
Total c4.2xlarge instance used is 5
Total cost is 1814.4
Instance 0 contains 7 apps
	 CPU: 5.4vCPU	 RAM: 5120.0MB	 Disk: 100.0GB
	 Contains: ('medium0', 'medium1', 'medium2', 'medium3', 'medium4', 'medium5', 'large6')
Instance 1 contains 15 apps
	 CPU: 7.0vCPU	 RAM: 7168.0MB	 Disk: 108.0GB
	 Contains: ('small8', 'small9', 'small10', 'small14', 'small16', 'small17', 'small18', 'small19', 'medium6', 'medium7', 'medium8', 'medium9', 'medium10', 'medium11', 'large0')
Instance 2 contains 14 apps
	 CPU: 7.199999999999999vCPU	 RAM: 7168.0MB	 Disk: 92.0GB
	 Contains: ('small0', 'small1', 'small2', 'small3', 'small4', 'small5', 'small6', 'small7', 'small11', 'small12', 'small13', 'small15', 'large3', 'large4')
Instance 3 contains 3 apps
	 CPU: 7.199999999999999vCPU	 RAM: 6144.0MB	 Disk: 120.0GB
	 Contains: ('large1', 'large2', 'large5')
Instance 4 contains 2 apps
	 CPU: 4.8vCPU	 RAM: 4096.0MB	 Disk: 80.0GB
	 Contains: ('large7', 'large8')

Result: [{'instance': 'm4.x4large', 'total_cost': 2229.12}, {'instance': 'r3.2xlarge', 'total_cost': 2872.8}, {'instance': 'c4.2xlarge', 'total_cost': 1814.4}]

Es wird länger dauern, aber infolgedessen scheint es am effizientesten zu sein, c4.2xlarge in 4 Einheiten zu verpacken, was 1814,4 USD pro Monat kostet.

Impressionen

Dieses Mal betrachtete ich die Platzierung von Anwendungen als Optimierungsproblem. Natürlich gibt es nur wenige Fälle, in denen alle Anwendungen in einer Instanz derselben Größe gepackt sind, und es gibt viele Punkte, die bei der Betrachtung der Architektur zu berücksichtigen sind, z. B. die Subnetztrennung. Eigentlich wollte ich eine Konfiguration berechnen, die mehrere Instanzgrößen (c4.2xlarge 3-Einheiten, t2.micro 4-Einheiten usw.) mischt, aber ich weiß nicht, wie man mehrere Bins unterschiedlicher Größe verpackt, also diese Form wurde. Dies wird ein Thema für die Zukunft sein. Wenn Sie Details haben, lassen Sie es mich bitte wissen.

Referenz

Kombinationsoptimierung verwenden Kombinationsoptimierungsstandardproblem und Ausführungsmethode Python in Optimierung So lösen Sie das Problem beim Verpacken von Behältern [Optimierung / statistische Analyse / maschinelles Lernen für Business Analytics-Praktiker in Python-Sprache](https://www.amazon.co.jp/Python%E8%A8%80%E8%AA%9E%E3%81] % AB% E3% 82% 88% E3% 82% 8B% E3% 83% 93% E3% 82% B8% E3% 83% 8D% E3% 82% B9% E3% 82% A2% E3% 83% 8A % E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AF% E3% 82% B9-% E5% AE% 9F% E5% 8B% 99% E5% AE% B6% E3% 81% AE% E3% 81% 9F% E3% 82% 81% E3% 81% AE% E6% 9C% 80% E9% 81% A9% E5% 8C% 96% E3% 83% BB% E7% B5% B1% E8% A8% 88% E8% A7% A3% E6% 9E% 90% E3% 83% BB% E6% A9% 9F% E6% A2% B0% E5% AD% A6% E7% BF% 92-% E4% B9% 85% E4% BF% 9D-% E5% B9% B9% E9% 9B% 84 / dp / 4764905167 / ref = sr_1_1? Ie = UTF8 & qid = 1495359888 & sr = 8-1 & keywords = python +% E3% 83% 93% E3% 82% B8% E3% 83% 8D% E3% 82% B9% E3% 83% BB% E3% 82% A2% E3% 83% 8A% E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AF% E3% 82% B9) https://github.com/PythonCharmers/OOSuite/blob/master/OpenOpt/openopt/examples/bpp_2.py

[PYTHON] Verwenden Sie das Problem beim Packen von Behältern, um die Cloud-Nutzungsgebühren zu senken