Object Storage unlike file-systems is an ideal destination for logs and improve production support drastically with their access over S3 APIs. The Cache service can directly re-use the object storage as its log store. The store is limitless and has no maintenance. The time-series databases make progressive buckets as they fill events in each bucket and this can be done easily with object storage too. The namespace-bucket-object hierarchy is well suited for time-series data. There is no limit to the number of objects within a bucket and we can rollover buckets in the same hot-warm-cold manner that time series databases do. Moreover, with the data available in the object storage, it is easily accessible to all users for read over the http.  The only caveat is that some production support request may be made to accommodate separate object–storage for the persistence of objects in the cache from the object-storage for the persistence of logs. This is quite reasonable and may be accommodated on-premise or in the cloud depending on the worth of the data and the cost incurred. The log stores can be periodically trimmed as well. In addition, the entire querying stack for reading these entries, can be built on copies or selections of buckets and objects. More about saving logs and their indexes in object storage is available at : https://1drv.ms/w/s!Ashlm-Nw-wnWt3eeNpsNk1f3BZVM 

We were discussing object cache in production systems. The production system, as opposed to other environments, needs to be closely monitored. This means that we have alerting infrastructure for exceeding thresholds on various metrics that will be relevant to the operation of the cache. In addition, whenever the system needs to be diagnosed for troubleshooting, some supportability features will be required from the system. These include running counters so that the logs need not be the only source of information. The level of alerts and monitors on a production system will far exceed those in any other environment because it represents the operations of a company or organization. In addition to these safeguards, a production system is also the longest standing environment and needs to be running smooth. Consequently, all activities on the production system must be well understood, rehearsed and orchestrated.
The list of features for production support include many more items other than logging. While logs are authoritative on all aspects of the operation of the services, they grow quickly and roll over into several files even when archived. Most organizations are not able to retain more than few months history of logs in their file-system. Even if the logs can be persisted in file system remote from the production systems, they will require a lot of storage. Moreover, the trouble with searching files directly with the file-system is that we are limited to command line tools. This is not necessarily the case with log indexes which can grow arbitrarily large and support impressive analytical capabilities by way of search and query operators.
The logs of the cache can directly into object storage in addition to other destinations via the log4j utility. The log4j is an asynchronous logging utility that supports writing and publishing of logs to multiple destinations at the same time. Much like the Enterprise Application Block for logging in the web application world, this utility allows any number of loggers to log to files. It is fast, flexible, reliable, extensible and supports filters and levels. It has three components- the loggers, the appenders and the layouts. The appenders emit the logs to files, console, socket, syslog, smtp, memory mapped files, NoSQL and ZeroMQ. Although object storage is not directly listed as destination and in fact object storage works very well as a time-series store, there doesn’t seem to be a direct s3 appender. However, since queues and webhooks are supported, it should be straightforward to setup object storage as a sink for the logs.

If the cache is distributed, the performance analysis may need to find if any of the distributed hashing leads to nodes that are overloaded. These nodes can further be expanded by the addition of new nodes. Performance analysis in a distributed framework is slightly more involved than on a single server because there is a level of indirection. Such study must not only make sure that the objects are cached satisfactorily at the local level but also that they participate in the global statistics.
Statistics cannot be at the object level alone. We need running counters of hits and misses across objects. These may be aggregated from all the nodes in a distributed hash table. Some like to view this independent of the network between the nodes. For example, they take a global view regardless of the distribution of the actual objects. As long as we can cumulate the hits and misses on per object level and across objects in a global view, the networking does not matter at this level. Although, nodes are expected to have uniform distribution of objects, they may get improperly balanced at which point the network level statistics become helpful.
The performance measurements of a cache can be done in a test lab by simulating the workload from a production system. This requires just the signature of the workload in terms of the object accesses and everything else can be isolated from the production system. The capture of the workload is not at all hard because we only want the distribution, duration, type and size of accesses. The content itself does not matter as much as it does to applications and users. If we know the kind of object accesses done by the workloads, we know what the cache is subjected to in production. Then we can artificially generate as many objects and their access as necessary and it would not matter to the test because it would not change the duress on the cache. We can also maintain different t-shirt size artificial workloads to study the impact on the cache. Some people raise the concern that a system in theory may not work as well in practice but in this case, when we keep all the parameters the same, there is very little that can deviate the results from the theory. The difference between the lab and the production can be tightened so thin that we can assert that the production will meet the need of the workloads after they have been studied in the lab. Many organizations take this approach even for off-the shelf software because they don’t want to exercises anything in production. Moreover, access to the production system is very restricted because it involves many perspectives and not just performance. Compliance, regulations, auditing and other such concerns require that the production system is hardened beyond development and test access.  Imagine if you were gain to access to all the documents of the users using the production cache as a development or test representative of the organization. Even the pipelines feeding into the production are maintained with multiple stages of vetting so that we minimize the pollution to the production where it becomes necessary to revert to a previous version. Productions systems are also the assets of a company that represent the cumulative efforts of the entire organization if not the company itself. It becomes necessary to guard it more than others. Moreover, there is only one production system as opposed to multiple test and development environments.
#codingexercise
We were discussing subset sum yesterday. If we treat every element of the array as candidate for subset evaluation as above, we can find all this elements that satisfy the subset property. Since each iteration has overlaps with the previous iteration we can maintain a dp table of whether an element has a subset sum or product property. If the current element  has subset each of which has a value in the integer dp table corresponding to the number of ways of forming the subset, we can aggregate it for the current element.

The memoization merely helps to not redo the same calculations again.

We were discussing the design of cache yesterday. At this point, we can also separate the concerns between the cache and the storage for consistency. We can leverage the object storage for the consistency model of the objects. As long as there is a cache miss, we can translate the calls to the storage. In some cases, we can designate the cache as read through or write through. Therefore, as long as the architecture allows, our cache can be repurposed in more than one manner according to the workload and the provisioning of the policies. If the policies are determined by the layer above the cache, then the cache can become more robust. In the absence of policies, the cache can leverage the consistency model of the storage. It is for this reason that the caches that work with relational databases have been read-throughs or write-throughs.
There can definitely be a feedback cycle that can help tune the cache for a given setup. For example, the statistics that we collect from the cache in terms of hits and misses over time can help determine the minor adjustments to be made so that the applications see consistent performance. Most caches need to be warmed up before they can participate in the feedback cycle. This refers to the initial bringing of objects into the cache so that subsequent accesses may directly be made from the cache. This is true for both the application workloads as well as the cache. After the warm-up period, a workload may attain a regular rate of access. It is such patterns of access that we can hope to make improvements in the cache. Random accesses that do not have any pattern, are generally ignored from tuning.

#codingexercise
The dp technique of including or excluding an element in the subset problem also applies to subset product determination 

Now that we have looked at marking the object collection in the cache for eviction, let us look at a few techniques to improve the information passed from the garbage collection to the cache. We maintained that the cache need not implement any strategy such as the least-recently-used, time-to-live and such others. The garbage collection already maintains a distinct set of generations and it is grading down the objects and the information passed to the cache need not be a mark to delete. It can be transparent to the cache with all the statistics it gathers during the collection run. Therefore, the cache may be able to determine the next steps even if the garbage collector suddenly disappeared. This means it includes everything from counts of accesses to the object, initialization time, the last modified time and such others. Although we use the term garbage collector, it is really a metadata collector on the object because a traditional garbage collector relied extensively on the root object hierarchy and the scopes introduced by a predetermined set of instructions. Here, we are utilizing the metadata for the policy which the cache need not implement. Therefore, all information from the layer above may be saved so that the cache can use it just the same in the absence of any direct information of which objects to evict. Finally, the service for the cache may be able to bring the policy into the cache layer itself.
Let us now look at the topology of the cache. Initially we suggested that a set of servers can participate in the cache if the objects are distributed among the servers. In such a case, the cache was distributed among n servers as hash(o) modulo n. This had the nasty side-effect that when one or more servers went down or were added into the pool, all the objects in the cache would lose their hash because the variable n changed. Instead consistent hashing came up with the scheme of accommodating new servers and taking old servers offline by arranging the hashes around a circle with cache points.  When a cache is removed or added, the objects with hashes along the circle are moved clockwise to the next cache point. It also introduced “virtual nodes” which are replicas of cache points in the circle. Since the caches may have non-uniform distribution of objects across caches, the virtual nodes have replicas of objects from a number of cache points.
#codingexercise
Find the minimum number of subset elements of an integer array that sum to a given number
This follows the dynamic programming :
return min(1+ recursion_with_the_candidate_and_sum_minus_candidate, recursion_without_candidate_and_same_sum)
We add the validations for the terminal conditions.

We were discussing cache policy for aging. While there can be other mechanisms that directly translate to a table and query for the cache, grading and shifting objects is sufficient to achieve aging and compaction. This then translates to an effective cache policy.
Another strategy for the interaction between garbage collection and the cache is for the cache to merely hold a table of objects and their status. The status is always progressive from initialized->active->marked-for-eviction->deleted. The state of the objects is determined by the garbage collector. Therefore, the net result of garbage collection is a set of new entries in the list of objects for the cache.
Also, items marked for eviction or deleted from the cache may increase over time. These may then be put archived on a periodic rolling basis into the object storage so that the cache merely focuses on the un-evicted items. The cache therefore sees only a window of objects over time and this is quite manageable for the cache because objects are guaranteed to expire. The garbage collector publishes the result to the cache as a list without requiring any object movement.
def reaper (objects, graveyard):
       for dead in expired(objects):
               If dead not in graveyard:
                             graveyard += [dead]
                             objects = list(set(objects) - set(dead))
                else:
objects = list(set(objects) - set(dead))
 def setup_periodic_reaping(sender, **kwargs):
        sender.add_periodic_task(10.0, reaper(kwargs[‘objects’], kwargs[‘graveyard’]) , name=’reaping’)

#codingexercise

 Find the length of the largest dividing subsequence of a number array. An dividing subsequence is one where the elements appearing prior to an element in the subsequence are proper divisor of that element. 2, 4, 8 has a largest dividing subsequence of 3 and that of 2,4,6 is 2.
public static void printLDS(List <int> a) {
if  (a == null || a.size () ==0) {System.out.println (“0”);}
if (a.size () == 1) { System.out.println (“1”);}
int lds = new int [a.size ()+1];
lds [0]  = 1;
for (int I = 1; I  < a.size (); I++){
     for (int j = 0; j < I; j++){
            if (lds [j] != 0 && a [j] != 0 && a [i] > a [j] && a [i] % a [j] == 0) {
                 lds [i] = Math.max (lds [i], lds [j] +1);
            }
     }
List b = Arrays.asList(ArrayUtils.toObject(lds));
System.out.println (Collections.max (b));
}
The above method can be modified for for any longest increasing subsequence


The subsequence of divisors also from an increasing subsequence  

We were discussing garbage collection and compaction.With objects, we don't have to create the graph. Instead we have to find ways to classify them by generation. Any classification of the objects is considered temporary until the next usage. At that point, the same objects may need reclassification. Since the classification is temporal, we run the risk of mislabeling generations and consequently reclaiming an object when it wasn't supposed to be.
We can also consider a markdown approach where after labeling the objects, we progressively mark them down so that we take actions only on the labels that are older than the oldest classification. This will help with keeping the classification and the reaping separate. The above approach will enable no actions to be taken if just the classification is needed. And also helping with taking different actions on the different tiers. For example, evict and delete may be considered separate actions. 
The unit of moving operation is an object here only because applications use objects. However, the cache may choose to stash swaths of objects at a time for shifting or ignoring. For example, we could use heap to keep track of the biggest available swath to roll for objects of arbitrary size. 
We may also have a compact version for keeping a running track of all the swaths. For example, if they are consecutive, we could coalesce them. If there is a set of active objects that can be margined into a swath, it can be marked as busy and ignored. If there are too many alternating swaths of free and busy object swaths, they can be retained as such and ignored from coalescing.
Busy swaths may need to be updated as candidate for conversion to free whenever objects are moved out of it.
Busy swaths can also be coalesced if they permit. This is usually not necessary because it is too aggressive and only a tiny fraction of the overall collection.
Movements of free and busy swaths are always opposite to each other. The free swaths move towards the younger generation where they can be utilized for gen 0.
The movement operation itself can be optimized by efficient bookkeeping so that it translates only to updates in the book-keeping