tree c0b9b52fef0c9af6305ec48ca8add11e1574e117
parent 3a4decdb2a7969cf2d68707675dc96868f197de3
author arnabp <arnab.phani@tugraz.at> 1604338811 +0100
committer arnabp <arnab.phani@tugraz.at> 1604339988 +0100

[SYSTEMDS-2713] DAG height based eviction policy for lineage cache

This patch introduces a new eviction policy, DAGHEIGHT, for lineage cache
eviction. According to this policy, lineage items farthest from the
leaves get evicted first. We store the height of each item on construction.
For inputs having different heights, we find the maximum (linear time) and
increment it by one for the current node.
In addition, this patch updates the Comparator for the eviction queue.
Now, entries with same score are ordered by cost, size ratio in LRU and
DAGHEIGHT policies, and by timestamp in COSTNSIZE policy. For HYBRID,
entries with same score are still ordered by Ids.