Today we continue our discussion of the  paper titled "Pelican: a  building block for exascale cold data storage". Pelican treats a group of disks as a single schedulable unit. Resource restrictions such as power consumption, vibrations and failure domains are expressed as constraints over these units.

With the help of resource constraints and scheduling units, Pelican aims to be better than its over provisioned counterpart racks using computations in software stacks

Pelican uses resources from a set of resource domains which is a subset of disks. Pelican proposes a data layout and IO scheduling algorithms by expressing these resource domains as constraints over the disks. 

We were reading about the IO scheduler which does request ordering and rate limiting. The former is done to batch sets of operation for the same group to amortize the group spin up latency over the set of operations. The latter makes the rebuild operations complete within an upper time bound.

The scheduler maintains two queues - one for rebuild and another for regular operations and performs weighted fair queuing.
If the blob size is uniform, the upper bound on the tolerated reordering is expressed in terms of the number of operations. If the blob size is non-uniform, it is expressed in terms of wall clock time.  For each queued request, this process is greedily repeated. The batching is maximized unless it violates fairness for some requests. And the reordering bound is enforced for each request. These two guarantees using the upper bound which controls the reordering. The process expresses the tradeoff between throughput and fairness using this upper bound. If the value of the upper bound is close to zero, the queues provide fairness. On the other hand, if the value of the upper bound is close to infinity, it minimizes the number of spin-ups which increases the throughput.

#codingexercise

Print all possible strings that can be made by placing spaces

Void Permute (List<String> a, List<string> b, bool[] used) 

{ 

  If ( b.distinct().Count() >= a.Length)  { Console.Write(b.ToString()); return;} 

  For (int I = 0; I < a.Length ; i++) 

  { 

    If (used[i]) continue; 

     used[i] = true; 

     B.Add(A[i]); 

     Permute(a, b, used); 
     if (i < a.Length - 1){
         B.Add(" ");
         Permute(a,b,used);
         B.RemoveLast();
     }

     B.RemoveLast();

     used[i] = false; 

  } 

} 

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Recall that the topological sort helps list vertices in an order such that if u is before v in the list, then there is no edge from u to v.  The same criteria can be used to represent letters in a dictionary where the listing follows an order. All we have to do is add edges to support the topological sort.

topological sorting DFS ( V, E)

For each vertex v in V

       V.color=white

       V.d = nil

  Time = 0

 For each vertex v in V:

       If v.color == white:

              DFS-Visit (V, E)

     

 DFS-VISIT (V,E, u)

  time = time + 1

   u.d = time

   u.color = gray

   foreach  vertex v adjacent to u

        If v.color == white

           DFS-VISIT(V,E,v)

         Else

               If v.d  <= u.d < u.f <= v.f  throw back edge exception.

 u.color = black

time = time + 1

 u.f = time

void GetDictOrder(List<string> words, int V)

{

Graph g(V);

for (int i =0; i < words.Count-1; i++)

{

   var first = words[i]; 

   var second = words[i+1];

   for (int j = 0; j < min(first.length, second..length); j++)

   {

       if ( first.Length != second.Length)

       {

         g.AddE(first[j] - 'a', second[j] - 'a');

        break;

      }

   }

}

DFS-VISIT(g.V, g.E, words[0][0]);

}

Given a number n and k(no of swaps allowed), make the biggest number from n by making at most k swaps. If its already the biggest return the number itself

Int getnum(int num, int k)

{

Var digits = num.toDigits();

Int swaps = 0;
Var desc = digits.sort().reverse();

For( int i = 0; i < digits.count; i++)
    If (digits[i] != desc[j]){
           Swaps++;
           If (swaps > k)
                 Var part = desc.getRange(0,i+1)
                  Return part.union(digits.except(part)).toNumber();
           }

}

Return desc.toNumber();

}