[
https://issues.apache.org/jira/browse/HDFS-15704?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17244041#comment-17244041
]
Ahmed Hussein edited comment on HDFS-15704 at 12/4/20, 3:44 PM:
----------------------------------------------------------------
Thanks [~weichiu] ! I haven't seen HDFS-14498 because it did not show on the
history of {{LeaseManager}}.
Probably, I can change the Jira title and description to reflect the
optimizations done in {{LeaseManager}}.
These are my concerns with {{LeaseManager.java}}:
There are three data structures (3x Memory complexity). The TreeMap has an
average {{O(log ( n ))}} for every operation.
For each operation the lease has to be removed from sortedLeases then
re-inserted back which results in an overhead
of 2x time complexity.
- It does not seem that there is a point of keeping map of {{leases}} sorted
by the key.
Therefore the complexity of the TreeMap is not justified.
{code:java}
// Used for handling lock-leases
// Mapping: leaseHolder -> Lease
private final SortedMap<String, Lease> leases = new TreeMap<>();
// Set of: Lease
private final NavigableSet<Lease> sortedLeases = new TreeSet<>(
new Comparator<Lease>() {
@Override
public int compare(Lease o1, Lease o2) {
if (o1.getLastUpdate() != o2.getLastUpdate()) {
return Long.signum(o1.getLastUpdate() - o2.getLastUpdate());
} else {
return o1.holder.compareTo(o2.holder);
}
}
});
// INodeID -> Lease
private final TreeMap<Long, Lease> leasesById = new TreeMap<>();
{code}
The [code changes in
PR-2511|https://github.com/apache/hadoop/pull/2511/files#diff-f18ff729aafade0aa36ac782b623c1943f48e936f8a3594423be94f3e88e2a5dR97]
get rid of the {{sortedLeases}}, and replaces the {{TreeMap}} with {{HashMap}}.
[~sodonnell], since you have experience with this part of the implementation.
WDYT about the suggested optimizations?
was (Author: ahussein):
Thanks [~weichiu] ! I haven't seen HDFS-14498 because it did not show on the
history of {{LeaseManager}}.
Probably, I can change the Jira title and description to reflect the
optimizations done in {{LeaseManager}}.
These are my concerns with {{LeaseManager.java}}:
There are three data structures (3x Memory complexity). The TreeMap has an
average {{O(log(n))}} for every operation.
For each operation the lease has to be removed from sortedLeases then
re-inserted back which results in an overhead
of 2x time complexity.
- It does not seem that there is a point of keeping map of {{leases}} sorted
by the key.
Therefore the complexity of the TreeMap is not justified.
{code:java}
// Used for handling lock-leases
// Mapping: leaseHolder -> Lease
private final SortedMap<String, Lease> leases = new TreeMap<>();
// Set of: Lease
private final NavigableSet<Lease> sortedLeases = new TreeSet<>(
new Comparator<Lease>() {
@Override
public int compare(Lease o1, Lease o2) {
if (o1.getLastUpdate() != o2.getLastUpdate()) {
return Long.signum(o1.getLastUpdate() - o2.getLastUpdate());
} else {
return o1.holder.compareTo(o2.holder);
}
}
});
// INodeID -> Lease
private final TreeMap<Long, Lease> leasesById = new TreeMap<>();
{code}
The [code changes in
PR-2511|https://github.com/apache/hadoop/pull/2511/files#diff-f18ff729aafade0aa36ac782b623c1943f48e936f8a3594423be94f3e88e2a5dR97]
get rid of the {{sortedLeases}}, and replaces the {{TreeMap}} with {{HashMap}}.
[~sodonnell], since you have experience with this part of the implementation.
WDYT about the suggested optimizations?
> Mitigate lease monitor's rapid infinite loop
> --------------------------------------------
>
> Key: HDFS-15704
> URL: https://issues.apache.org/jira/browse/HDFS-15704
> Project: Hadoop HDFS
> Issue Type: Improvement
> Components: namenode
> Reporter: Ahmed Hussein
> Assignee: Ahmed Hussein
> Priority: Major
> Labels: pull-request-available
> Time Spent: 40m
> Remaining Estimate: 0h
>
> [~daryn] reported that the lease monitor goes into a rapid infinite loop if
> an exception occurs during a lease recovery. The two main issues are:
> # lease monitor thread does not sleep if an exception occurs before looping
> again
> # the loop peeks at the first element of a sorted tree set so when an
> exception occurs, the "bad" lease remains as the first element preventing
> recovery of other leases.
> This jira is not intended to fix the underlying issues causing the exception
> during recovery but merely to mitigate the cited issues.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
