hadoop-hdfs-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Tsz Wo (Nicholas), SZE (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HDFS-4103) Support O(1) snapshot creation
Date Mon, 29 Oct 2012 01:19:12 GMT

    [ https://issues.apache.org/jira/browse/HDFS-4103?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13485771#comment-13485771

Tsz Wo (Nicholas), SZE commented on HDFS-4103:

There is a well-known data structure supportting
- O(1) snapshot creation,
- O(1) access slowdown, and
- O(1) modification space and time.

See http://www.cs.cmu.edu/~sleator/papers/Persistence.htm

The data structure collides with the ideas Suresh, Jing and I were discussing.  We probably
will use it in our implementation.
> Support O(1) snapshot creation
> ------------------------------
>                 Key: HDFS-4103
>                 URL: https://issues.apache.org/jira/browse/HDFS-4103
>             Project: Hadoop HDFS
>          Issue Type: Sub-task
>          Components: name-node
>            Reporter: Tsz Wo (Nicholas), SZE
>            Assignee: Tsz Wo (Nicholas), SZE
> In our first snapshot implementation, snapshot creation runs in O(N) and occupies O(N)
memory space, where N = # files + # directories + # symlinks in the snapshot.  The advantages
of the implementation are that there is no additional cost for the modifications after snapshots
are created, and it leads to a simple implementation.
> In this JIRA, we optimize snapshot creation to O(1) although it introduces additional
cost in the modifications after snapshots are created.

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira

View raw message