Exponential backoff, Circuit breaker – ანუ ცადეთ მოგვიანებით

ჩვენი პროგრამები არასრულყოფილ სამყაროში ცხოვრობენ, არასტაბილური ქსელით ლაპარაკობენ და არაგარანტირებულ რესურსებს ეძახიან. ბოლო დროს განსაკუთრებით კიდევ უფრო მეტი ჩავარდნის შესაძლებლობა გაჩნდა, როცა ყველაფერი სერვისებად იქცა.
კოდში ზოგჯერ ძირითად ლოგიკაზე მეტი ადგილი ამ ჩავარდნებისგან დაზღვევას უჭირავს.
ერთ-ერთ ასეთ მათგანზე მინდა დავწერო, როცა სერვისის გამოძახება წარუმატებლად სრულდება.

პრობლემური შედეგი შეიძლება სხვადასხვა ხასიათის იყოს:
გარდამავალი – მაგალითად,
– 503 Service unavailable – როდესაც სერვისი გადატვირთულია ან დროებით გათიშულია;
– 504 Gateway Timeout – როდესაც ბექ სერვერიდან პასუხი დროულად არ მოდის პროქსისთან;
– ასევე ნებისმიერი timeout, როდესაც სერვერიდან საერთოდ არ მოდის პასუხი.
ეს გარდამავალი შეცდომებია და შეიძლება გამოსწორდეს რაღაც დროის შემდეგ

მუდმივი – არასწორი პაროლის შეცდომა თავისით არასოდეს გამოსწორდება, რამდენჯერაც არ უნდა გაიგზავნოს.

როდესაც დავადგენთ, რომ გარდამავალ შეცდომასთან გვაქვს საქმე, შეგვიძლია ავდგეთ და რამდენიმე წამში ერთხელ კვლავ გავიმეოროთ მოთხოვნა. ოღონდ ერთი მომენტია კიდევ: თუ სერვისი დიდი დატვირთვის გამო ვერ აბრუნებს პასუხს, მაშინ ჩვენი ასეთი მიმართვები კიდევ უფრო გაზრდის მოთხოვნების რიგს და ხელს შეუშლის სერვისს აღდგენაში. მდგომარეობის გამოსასწორებლად რამდენიმე დიზაინ პატერნია გავრცელებული:

 

Exponential backoff

ალბათ შეგიმჩნევიათ, როცა GMail არის გახსნილი და ინტერნეტი ითიშება, თავზე ეწერება შეტყობინება Connecting in 1s… ჯერ ერთ წამში ცდის, მერე 2 წამში, მერე 4 წამში, მერე 8-ში და ასე ექსპონენციალურად ზრდის დროს მცდელობებს შორის. საათებზეც კი ადის.
საუბარი არ არის მხოლოდ ბრაუზერს და სერვერს შორის ურთიერთობაზე. შეიძლება ასეთი პრობლემური კავშირები მთელიანად სერვერის მხარეს არსებულ სხვადასხვა კომპონენტს შორის იყოს. ზოგჯერ უკეთესი შედეგის მისაღებად ‘შემთხვევითობაც’ შემოაქვთ, მაგალითად Amazon AWS არქიტექტურაში ორივე ერთად გამოიყენება: Exponential Backoff and Jitter.
ანუ მეორე მცდელობა 4 წამის შემდეგ კი არა იყოს, არამედ 1-4 ფარგლებში შემთხვევითად შერჩეულ X წამის შემდეგ.

ეს რიცხვები ახსნის ხათრით შემოვიტანე. ცხადია, რამდენიმე კონსტანტა იქნება საჭირო:
საბაზო დაყოვნების დრო, ცდების მაქსიმალური რაოდენობა და დაყოვნების მაქსიმალური დრო.

ანალოგიურად, ჩვენც შეგვიძლია სერვისის წარუმატებელი გამოძახების შემდეგ ყოველ წამს კი არ გავიმეოროთ მოთხოვნა, არამედ უფრო და უფრო მეტი დაყოვნება გავაკეთოთ და სერვისს აღდგენის საშუალება მივცეთ.

Exponential backoff ალგორითმი Ethernet პროტოკოლშიც გამოიყენება. როცა ქსელში ორი მანქანა ერთდროულად ცდილობს პაკეტის გაგზავნას, კოლიზია ხდება. ზუსტად იგივე დაყოვნების შემდეგ რომ გაგზავნოს ორივემ, ისევ ისე დაემთხვევა და ასე უსასრულოდ. ამიტომ დაყოვნების ფორმულა ასეთია
0 ≤ r < 2^k სადაც k = min (n, 10)
n არის კოლიზიების რაოდენობა და r შემთხვევითად ირჩევა. ანუ რაც უფრო მეტი კოლიზია ხდება, ექსპონენციალურად იზრდება საზღვარი, და მერე ამ საზღვრიდან ხდება დაყოვნების დროის ამორჩევა შემთხვევითად.

 

Circuit breaker

ეს ალგორითმი ჰგავს ელექტრო ქსელის ავტომატურ ამომრთველს, რომელიც ყველას გვიყენია სახლში.
სერვისს და კლიენტს შორის დამატებით დგება ერთი შუალედური ობიექტი, რომელიც სერვისის მცველის როლს ასრულებს. როცა ხედავს რომ დროის გარკვეულ მონაკვეთში სერვერისგან ცუდი პასუხები მოდის ან საერთოდ არ მოდის, გადადის “Open” რეჟიმში, აღარ უშვებს მასთან კლიენტის მოთხოვნებს და თვითონვე პასუხობს ჩავარდნით.

როცა ელექტრო ამომრთველს მოსდის ასე, ხელით ვრთავთ უკან, მაგრამ აქ ხელით ვერ ჩავრთავთ, ამიტომ რაღაც ინტერვალის შემდეგ ეს მცველი ობიექტი გადაგვყავს “Half-Open” რეჟიმში და ის ერთ მოთხოვნას სერვისამდე გაატარებს საცდელად. პასუხის მიხედვით ან ისევ “Open” რეჟიმში დაბრუნდება, ან “Closed” გახდება და ყველა მომდევნო მოთხოვნას სერვერთან გაუშვებს ჩვეულებრივ.

რამდენიმე ტაიმაუტის შემდეგ მცველი ჩაირთვება და ის დაიწყებს პასუხის დაბრუნებას

სურათი აღებულია მარტინ ფოულერის ბლოგიდან

ზოგიერთ ფრეიმვორკში (განსაკუთრებით ბაზასთან ურთიერთობისას) უკვე იმპლემენტირებულია მსგავსი ალგორითმები.

თუ თქვენ public API გაქვთ და გსურთ რომ უცხო კლიენტებმა retry-ის სწორი მექანიზმი გამოიყენონ – სულ მთლად არ მოკლან თქვენი სერვისი გაჭირვების ჟამს, მაშინ შეგიძლიათ თქვენ თვითონ დაწეროთ რამდენიმე კლიენტი-ბიბლიოთეკა სხვადასხვა ენისთვის და მომხმარებლებიც მათ გამოიყენებენ.

მრავალგანზომილებიანი მასივი Java-ში

გუშინ ერთ-ერთ ამოცანაში მეხსიერების ლიმიტს ვაჭარბებდი იმის გამო, რომ არასწორად მქონდა აღწერილი მრავალგანზომილებიანი მასივი. c-ში და c++-ში ამის პრობლემა არ იქნებოდა, თუმცა, იმის გამო, რომ ჯავაში ყველაფერი ობიექტია (პრიმიტიული ტიპების გარდა), მრავალგანზომილებიანი მასივების შექმნისას მეხსიერება განსხვავებული გზით უნდა დავითვალოთ.

მაგალითად ასეთი მასივის ზომა c++-ში 96 ბაიტია (32 ბიტიან სისტემაში):
int arr[2][3][4];
2 * 3 * 4 = 24. თითოეული კიდევ 4 ბაიტიანია int ტიპის გამო და ჯამში 24 * 4 = 96 ბაიტი გამოდის.
int arr[4][3][2] ასეთი აღწერის დროს შედეგი იგივეა.

შევადაროთ Java-ში ეს ორი აღწერა:
int arr[][][] = new int[40000][200][2];
int arr[][][] = new int[2][200][40000];

აზრობრივად განსხვავება არ არის, თუმცა პირველი გზა გაცილებით მეტ მეხსიერებას მოიხმარს. აი, რატომ:
1. ჯავას მასივი თავისთავად ობიექტია. თითოეულ ობიექტში (არა reference-თან, არამედ heap-ში) დამატებით რამდენიმე ბაიტს იკავებს სპეციალური object header ინფორმაცია. object header-ში ინახება ვირტუალური მანქანისთვის საჭირო მონაცემები, რასაც garbage collector-ისთვის და სხვადასხვა მიზნებისთვის იყენებს. როგორც ვიცი, ჩვეულებრივ ეს 8 ბაიტია ხოლმე 32-ბიტიან მანქანაზე და 16 ბაიტი 64-იანზე. ამის გარდა, მასივის ობიექტში ინახება მასივის ზომაც, ანუ დამატებით 4 ბაიტი. კიდევ შეიძება მეხსიერებაში padding-ს დასჭირდეს რამდენიმე ბაიტი. ამიტომ ზუსტად არ დავთვლი და ვთქვათ, ერთი მასივის ობიექტისთვის (ელემენტების გარდა) საჭიროა X ბაიტი.

2. int[a][b] – ჯავაში ეს არის a ცალი b ელემენტიანი მასივის მასივი, ანუ სინამდვილეში ერთის მაგივრად a+1 ობიექტი გვაქვს.
int[a][b][k]სამგანზომილებიანის შემთხვევაში a * b + a + 1 ცალი ობიექტი და ა.შ.

ახლა გამოვთვალოთ და შევადაროთ ზევით ნახსენები ორი მასივის ზომა:
(40,000 * 200 + 40,000 + 1) * X + (40,000 * 200 * 2 * 4)
(2 * 200 + 2 + 1) * X + (40,000 * 200 * 2 * 4)

მეორე ნაწილი რაც int ტიპის ელემენტების ზომას ითვლის, ცხადია, ორივესთვის ერთი და იგივე იქნება.
პირველი ნაწილის მიხედვით კი 8,039,598 ცალი ზედმეტი ობიექტი იქმნება პირველ შემთხვევაში, მეხსიერებაც შესაბამისად გაცილებით მეტი სჭირდება.

ისე, პროფაილერით ვერ ვხედავ სინამდვილეში მართლაც ამდენი ობიექტია თუ არა და იდეა ხომ არ გაქვთ როგორ შეიძლება შევამოწმო?

დინამიური მასივი

პროგრამირებაში დინამიური მასივი ისეთი მონაცემთა სტრუქტურაა, რომელსაც ცვლადი სიგრძე აქვს, მასში ელემენტების ჩამატება / წაშლა და random access შეიძლება – ანუ მის ნებისმიერ ელემენტზე წვდომას ფიქსირებული დრო სჭირდება და მასივის მთლიან ზომაზე არ არის დამოკიდებული.

ასეთ სტრუქტურას სხვადასხვა დასახელებით შეხვდებით – dynamic array, growable array, resizable array, dynamic table, mutable array, array list.

random access-ის უზრუნველსაყოფად მასივისთვის მეხსიერების უწყვეტი ნაწილი გამოიყოფა, ანუ, მისი ელემენტები მეხსიერებაში ერთმანეთის მიყოლებით ინახება.
სტატიკური მასივის შემთხვევაში ეს პრობლემას არ წარმოადგენს, რადგან ჩვენ თავიდანვე ვეუბნებით სიგრძეს. დინამიურ მასივს კი სწორედ მაშინ ვიყენებთ, როდესაც წინასწარ არ შეგვიძლია ზომის განსაზღვრა. მაშინ რამხელა მეხსიერება უნდა გამოიყოს, რომ ელემენტები კვლავ მიყოლებით არსებულ ბაიტებში იქნას შენახული?

ცხადია, თავის დაზღვევის მიზნით დიდი მეხსიერების გამოყოფას აზრი არ აქვს. 20 ელემენტის შენახვისთვის მილიონი ბაიტი წინასწარ არ უნდა დარეზერვდეს ასეთი მასივისთვის, რომელიც შემდეგ ცარიელი დარჩება.

ბევრ პროგრამირების ენაში ეს პრობლემა შემდეგნაირად არის გადაწყვეტილი:
დინამიური მასივის უკან სტატიკური მასივი დგას, რომელიც დასაწყისში მცირე სიგრძის მითითებით იქმნება. როდესაც მასივი გაივსება და შემდეგ კვლავ შეეცდებიან მასში ელემენტის ჩამატებას, შეიქმნება უფრო დიდი ზომის სტატიკური მასივი, მასში გადაიწერება არსებული მასივის ელემენტები და ძველი წაიშლება. შესაბამისად, დინამიურ მასივში ზოგიერთი ელემენტის ჩამატებას შედარებით მეტი დრო მიაქვს.

ასეთ გადაწყვეტაში მნიშვნელოვანია შეკითხვაზე პასუხი: რამდენჯერ უნდა გაიზარდოს მასივი გადაწერის წინ?

აღვნიშნოთ, რომ ისევ კომპრომისს ვეძებთ დროის და მეხსიერების ხარჯვას შორის. თუ თითო-თითოდ გავზრდით მასივს, ყოველ ახალ ელემენტზე მთელი მასივის გადაწერა დროს წაიღებს, ხოლო თუ რამდენჯერმე დავაგრძელებთ, შეიძლება დიდი ზომის მეხსიერება ცარიელი დაგვრჩეს.

ოპტიმალურ ვარიანტად რიცხვი 2 არის მიღებული. ამ რიცხვს ზრდიან ამ ამცირებენ იმის მიხედვით მეტი მეხსიერების ხარჯი ურჩევნიათ თუ დროის.

სხვადასხვა პროგრამირების ენაში ან რეალიზაციაში ის ზოგჯერ განსხვავებულია – მაგალითად, ვექტორი c++-ში 2-ჯერ იზრდება, Java-ს ვექტორისთვისაც default მნიშვნელობა ეს რიცხვია, თუმცა პარამეტრის სახით არის და შეცვლა შეიძლება. Java-ს ArrayList-ის სტატიკური მასივი 3/2-ჯერ იზრდება. HashMap-ის მასივი 2-ჯერ. პითონის C-ის იმპლემენტაციაში რაღაც უცნაურად არის, 9/8 გამოდის საშუალოდ. ამ ბმულზეა კოდი. აქ კი მისი გარჩევა

თუ პროგრამისტისთვის წინასწარ არის ცნობილი მინიმუმ რამხელა მასივი დასჭირდება, შეუძლია ეს გაითვალისწინოს და დინამიური მასივი თავიდანვე იმხელა შეიქმნას.
მაგალითად c++-ის vector-ს აქვს ფუნქცია reserve რომლითაც წინასწარ შეიძლება მეხსიერების რეზერვირება.

Java-ში ArrayList და HashMap ობიექტებს კონსტრუქტორში გადაეცემა initialCapacity პარამეტრი. HashMap-ში არა მხოლოდ მასივის გადაწერა, არამედ ჰეშების თავიდან გენერაცია ხდება.

წარმადობისთვის ამ პარამეტრის წინასწარ მითითება უმჯობესია. რამდენიმე ექსპერიმენტი ჩავატარე და მართლაც მივიღე დროში სხვაობა, თუმცა ჩემს ჩვეულებრივ ამოცანებში ასეთი სხვაობა უმნიშვნელოა. ბოლო ბოლო ლოგარითმული რაოდენობით ხდება მასივის გადაწერა და მილიონის შემთხვევაშიც კი ეს სულ რაღაც 20-ია. თუ მილიწამები მნიშვნელოვანია, იქ ღირებული იქნება ასეთი ოპტიმიზაცია.

ზევით ვახსენეთ, რომ დინამიურ მასივში ამ გადაწერის საჭიროების შედეგად ზოგიერთი ელემენტის ჩამატების დროს O(1)-დან იზრდება O(n)-მდე, სადაც n მასივში არსებული ელემენტების რაოდენობაა. ამის მიუხედავად, ამორტიზებული ანალიზის შედეგად, დინამიურ მასივში ელემენტის ჩამატების დრო O(1)-ად არის მიჩნეული.

თვითონ ამორტიზებული ანალიზის არსი იმაში მდგომარეობს, რომ ალგორითმის მუშაობის შეფასებისას გათვალისწინებული იქნას ის სწრაფი ოპერაციებიც, რომელიც ყველაზე ცუდი შემთხვევების მუშაობის დროს აბათილებენ. ალგორითმის შესრულების დროის შეფასებისას worst-case სცენარს ვიღებთ ხოლმე, თუმცა შეიძლება რომ დასამუშავებელ ინფორმაციაში მხოლოდ რაღაც პროპორციით იყოს მძიმე ოპერაციები. შესაბამისად, თუ ჩვენ ყველა ოპერაციას გავითვალისწინებთ შეფასების დროს, შესაძლოა მუშაობის დრო გაცილებით ნაკლები გამოვიდეს, ვიდრე რაოდენობა გამრავლებული ყველაზე დიდ დროზე.

მოდი გამოვთვალოთ n ელემენტიანი დინამიური მასივის შევსების დრო:
თუ ჩავთვლით რომ ყოველ ჯერზე (როდესაც ორის ხარისხს მივაღწევთ) სტატიკური მასივი ორმაგდება, შეგვიძლია ელემენტების გადაწერის რაოდენობა ასე შევაფასოთ:
ბოლოდან მოვყვეთ. ბოლოს ყველას გადაწერა მოუწევს, იმის წინ მხოლოდ ნახევრის, იმის წინ მეოთხედის და ა.შ.
n + n/2 + n/4 + n/8 + … = n (1 + 1/2 + 1/4 + 1/8 + …) = 2n

ამ გადაწერებს მივუმატოთ თვითონ ელემენტების ჩასმაც და გამოვა 3n. შესაბამისად საშუალოს თუ ავიღებთ, თითოეული ელემენტის ჩასმისთვის გამოგვივა O(3) = O(1) დრო.

რჩევები საიტის ოპტიმიზაციისთვის (Front end)

დაახლოებით ერთი თვის წინ GeOlymp-ის საიტის გარეგნული მხარე განვაახლეთ თუმცა ბრაუზერის მხარეს სწრაფად ჩატვირთვისთვის საჭირო ოპტიმიზაცია არ გამიკეთებია. ამ პოსტში შევეცდები იმ თემებზე ვისაუბრო, რასაც ამ პროცესზე აქვს გავლენა; ამასთან, რეალურად შევასრულო ისინი საიტზე და ჩატვირთვის დროები შევადარო.

ახლა ქრომი მაჩვენებს, რომ ჯეოლიმპის ერთ-ერთი მთავარი გვერდის გახსნის დროს სერვერზე 42 მოთხოვნა იგზავნება, 307.9 კილობაიტი იტვირთება და 1.2 – 2.3 წამს ანდომებს გვერდის ჩატვირთვას. შევეცდები ამის გაუმჯობესებას..

1. ნაკლები რაოდენობის HTTP მოთხოვნის გაგზავნა სერვერზე
ერთ-ერთი ყველაზე მნიშვნელოვანი წესი, რომელსაც შესამჩნევი შედეგი აქვს, სერვერზე გასაგზავნი HTTP მოთხოვნების შემცირებაა. ეს მოთხოვნები იგზავნება თვითონ html ფაილის და ასევე თითოეული კომპონენტის წამოსაღებად, რასაც საიტი შეიცავს (სურათები, css და javascript ფაილები, ა.შ.).

http მოთხოვნა საკმაოდ მძიმე ოპერაციაა, რადგან მის შესასრულებლად საჭიროა DNS სერვერთან მისვლა, დომენის შესაბამისი ip მისამართის მიღება, მიღებული მისამართის საშუალებით ჰოსტ სერვერის მიგნება და ბოლო ბოლო ვებსერვერიდან რესურსის წამოღება. თუ ეს პუნქტები გეოგრაფიულადაც დაშორებულია (მაგალითად სხვადასხვა ქვეყნებში), მოთხოვნას უფრო მეტი სერვერის და ქსელის გავლა უწევს და დრო შესაბამისად იზრდება (ილუსტრაცია: როგორ მუშაობს ინტერნეტი).

Read more

RAID მასივები

ამ საკითხზე სემინარი მქონდა მოსამზადებელი და ბარემ პოსტსაც მივუძღვნი 🙂

რა არის ეს RAID (Redundant Array of Independent Disks) და რისთვის გამოიყენება? : )

როგორ შევინახოთ ინფორმაცია სისტემის აგების დროს დამოკიდებულია თვითონ ამოცანაზე. რა გვჭირდება: დიდი რაოდენობით ჩაწერა, წაკითხვა, სისწრაფე, საიმედოობა?

მაგალითად, არსებობს ამოცანები, სადაც კრიტიკული მნიშვნელობა აქვს ინფორმაციის საიმედოდ შენახვას და მასზე წვდომის შესაძლებლობას დროის ნებისმიერ მომენტში. ანუ, დისკის დაზიანების დროს უნდა არსებობდეს მისი შემცვლელი იგივე ინფორმაციით და თანაც რაც შეიძლება სწრაფად.

არის ამოცანები, სადაც წარმადობა უფრო პრიორიტეტულია. მაგალითად, როდესაც სერვერიდან დიდი რაოდენობით ვიდეო ნაკადები მოდის.

თავდაპირველად RAID-ის ძირითადი იდეა იყო, რომ რამდენიმე მყარი დისკი გაეერთიანებინა დისკების მასივში და ამით გაეუმჯობესებინა წარმადობა, რომელიც ერთ დიდი ზომის დისკს ჰქონდა.

ახლა RAID-ის არქიტექტურული დიზაინებიდან ყველაზე გავრცელებულია 5 ვარიანტი:  RAID 0, RAID 1, RAID 5, RAID 6, RAID 10.

ისინი ძირითადად ორ მიზანს ემსახურებიან: მონაცემთა შენახვის საიმედოობის გაზრდას, შეტანა/გამოტანის (დისკზე ჩაწერა/წაკითხვის) წარმადობის გაზრდას.

განვიხილოთ თითოეული მათგანი:

RAID 0

ჩაწერის დროს მონაცემები იყოფა ფრაგმენტებად და ეს ფრაგმენტები სათითაოდ ნაწილდება მასივში შემავალ დისკებზე. წაკითხვის დროს კი ყველა დისკიდან ერთდროულად ხდება წაკითხვა.

raid0

up_iconრაც უფრო მეტი დისკია, უფრო მეტად იზრდება სისწრაფე. უხეშად რომ შევადარო, ეს იგივეა, წყლის არხიდან ერთის მაგივრად რამდენიმე მილი გამოვიყვანოთ. იგივე რაოდენობის წყალს უფრო მალე მივიღებთ.

up_iconარ ვკარგავთ ადგილს. მთლიანად ვიყენებთ დისკების მოცულობას ჩვენი ინფორმაციისთვის.

down_iconასეთი სტრუქტურის სისუსტე დისკის დაზიანების დროს ჩანს. საკმარისია ერთ-ერთი მათგანის ამოვარდნა, რომ მთელი მასივი გადასაგდებია. წარმოიდგინეთ, წიგნში ყოველ სიტყვას მისი მესამედი რომ ჩამოვაჭრათ. წიგნი გამოუსადეგარი გახდება. თანაც მისი აღდგენა შეუძლებელია.

Read more