hadoop-hdfs-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From s..@apache.org
Subject svn commit: r961966 - in /hadoop/hdfs/trunk: ./ src/java/org/apache/hadoop/hdfs/ src/java/org/apache/hadoop/hdfs/server/namenode/ src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/
Date Thu, 08 Jul 2010 22:35:10 GMT
Author: shv
Date: Thu Jul  8 22:35:10 2010
New Revision: 961966

URL: http://svn.apache.org/viewvc?rev=961966&view=rev
Log:
HDFS-1140. Speedup INode.getPathComponents. Contributed by Dmytro Molkov.

Added:
    hadoop/hdfs/trunk/src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/TestPathComponents.java
  (with props)
Modified:
    hadoop/hdfs/trunk/CHANGES.txt
    hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/DFSUtil.java
    hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSDirectory.java
    hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSImage.java
    hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java

Modified: hadoop/hdfs/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/hdfs/trunk/CHANGES.txt?rev=961966&r1=961965&r2=961966&view=diff
==============================================================================
--- hadoop/hdfs/trunk/CHANGES.txt (original)
+++ hadoop/hdfs/trunk/CHANGES.txt Thu Jul  8 22:35:10 2010
@@ -64,6 +64,10 @@ Trunk (unreleased changes)
     HDFS-947. An Hftp read request is redirected to a datanode that has 
     the most replicas of the blocks in the file. (Dmytro Molkov via dhruba)
 
+  OPTIMIZATIONS
+
+    HDFS-1140. Speedup INode.getPathComponents. (Dmytro Molkov via shv)
+
   BUG FIXES
 
     HDFS-1039. Adding test for  JspHelper.getUGI(jnp via boryas)

Modified: hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/DFSUtil.java
URL: http://svn.apache.org/viewvc/hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/DFSUtil.java?rev=961966&r1=961965&r2=961966&view=diff
==============================================================================
--- hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/DFSUtil.java (original)
+++ hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/DFSUtil.java Thu Jul  8 22:35:10 2010
@@ -124,5 +124,87 @@ public class DFSUtil {
     }
     return null;
   }
+
+  /**
+   * Given a list of path components returns a path as a UTF8 String
+   */
+  public static String byteArray2String(byte[][] pathComponents) {
+    if (pathComponents.length == 0)
+      return "";
+    if (pathComponents.length == 1 && pathComponents[0].length == 0) {
+      return Path.SEPARATOR;
+    }
+    try {
+      StringBuilder result = new StringBuilder();
+      for (int i = 0; i < pathComponents.length; i++) {
+        result.append(new String(pathComponents[i], "UTF-8"));
+        if (i < pathComponents.length - 1) {
+          result.append(Path.SEPARATOR_CHAR);
+        }
+      }
+      return result.toString();
+    } catch (UnsupportedEncodingException ex) {
+      assert false : "UTF8 encoding is not supported ";
+    }
+    return null;
+  }
+
+  /**
+   * Splits the array of bytes into array of arrays of bytes
+   * on byte separator
+   * @param bytes the array of bytes to split
+   * @param separator the delimiting byte
+   */
+  public static byte[][] bytes2byteArray(byte[] bytes, byte separator) {
+    return bytes2byteArray(bytes, bytes.length, separator);
+  }
+
+  /**
+   * Splits first len bytes in bytes to array of arrays of bytes
+   * on byte separator
+   * @param bytes the byte array to split
+   * @param len the number of bytes to split
+   * @param separator the delimiting byte
+   */
+  public static byte[][] bytes2byteArray(byte[] bytes,
+                                         int len,
+                                         byte separator) {
+    assert len <= bytes.length;
+    int splits = 0;
+    if (len == 0) {
+      return new byte[][]{null};
+    }
+    // Count the splits. Omit multiple separators and the last one
+    for (int i = 0; i < len; i++) {
+      if (bytes[i] == separator) {
+        splits++;
+      }
+    }
+    int last = len - 1;
+    while (last > -1 && bytes[last--] == separator) {
+      splits--;
+    }
+    if (splits == 0 && bytes[0] == separator) {
+      return new byte[][]{null};
+    }
+    splits++;
+    byte[][] result = new byte[splits][];
+    int startIndex = 0;
+    int nextIndex = 0;
+    int index = 0;
+    // Build the splits
+    while (index < splits) {
+      while (nextIndex < len && bytes[nextIndex] != separator) {
+        nextIndex++;
+      }
+      result[index] = new byte[nextIndex - startIndex];
+      System.arraycopy(bytes, startIndex, result[index], 0, nextIndex
+              - startIndex);
+      index++;
+      startIndex = nextIndex + 1;
+      nextIndex = startIndex;
+    }
+    return result;
+  }
 }
 

Modified: hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSDirectory.java
URL: http://svn.apache.org/viewvc/hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSDirectory.java?rev=961966&r1=961965&r2=961966&view=diff
==============================================================================
--- hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSDirectory.java (original)
+++ hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSDirectory.java Thu
Jul  8 22:35:10 2010
@@ -248,7 +248,7 @@ class FSDirectory implements Closeable {
     }
   }
 
-  INodeDirectory addToParent( String src,
+  INodeDirectory addToParent( byte[][] src,
                               INodeDirectory parentINode,
                               PermissionStatus permissions,
                               Block[] blocks, 

Modified: hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSImage.java
URL: http://svn.apache.org/viewvc/hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSImage.java?rev=961966&r1=961965&r2=961966&view=diff
==============================================================================
--- hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSImage.java (original)
+++ hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/FSImage.java Thu Jul
 8 22:35:10 2010
@@ -32,6 +32,7 @@ import java.net.URI;
 import java.nio.ByteBuffer;
 import java.text.SimpleDateFormat;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.Date;
 import java.util.HashMap;
@@ -1080,14 +1081,14 @@ public class FSImage extends Storage {
 
       LOG.info("Number of files = " + numFiles);
 
-      String path;
-      String parentPath = "";
+      byte[][] pathComponents;
+      byte[][] parentPath = {{}};
       INodeDirectory parentINode = fsDir.rootDir;
       for (long i = 0; i < numFiles; i++) {
         long modificationTime = 0;
         long atime = 0;
         long blockSize = 0;
-        path = readString(in);
+        pathComponents = readPathComponents(in);
         replication = in.readShort();
         replication = editLog.adjustReplication(replication);
         modificationTime = in.readLong();
@@ -1149,7 +1150,7 @@ public class FSImage extends Storage {
           permissions = PermissionStatus.read(in);
         }
         
-        if (path.length() == 0) { // it is the root
+        if (isRoot(pathComponents)) { // it is the root
           // update the root's attributes
           if (nsQuota != -1 || dsQuota != -1) {
             fsDir.rootDir.setQuota(nsQuota, dsQuota);
@@ -1159,13 +1160,13 @@ public class FSImage extends Storage {
           continue;
         }
         // check if the new inode belongs to the same parent
-        if(!isParent(path, parentPath)) {
+        if(!isParent(pathComponents, parentPath)) {
           parentINode = null;
-          parentPath = getParent(path);
+          parentPath = getParent(pathComponents);
         }
         // add new inode
         // without propagating modification time to parent
-        parentINode = fsDir.addToParent(path, parentINode, permissions,
+        parentINode = fsDir.addToParent(pathComponents, parentINode, permissions,
                                         blocks, symlink, replication, modificationTime, 
                                         atime, nsQuota, dsQuota, blockSize, false);
       }
@@ -1191,13 +1192,34 @@ public class FSImage extends Storage {
   String getParent(String path) {
     return path.substring(0, path.lastIndexOf(Path.SEPARATOR));
   }
+  
+  byte[][] getParent(byte[][] path) {
+    byte[][] result = new byte[path.length - 1][];
+    for (int i = 0; i < result.length; i++) {
+      result[i] = new byte[path[i].length];
+      System.arraycopy(path[i], 0, result[i], 0, path[i].length);
+    }
+    return result;
+  }
+
+  private boolean isRoot(byte[][] path) {
+    return path.length == 1 &&
+      path[0] == null;    
+  }
 
-  private boolean isParent(String path, String parent) {
-    return parent != null && path != null
-          && path.indexOf(parent) == 0
-          && path.lastIndexOf(Path.SEPARATOR) == parent.length();
+  private boolean isParent(byte[][] path, byte[][] parent) {
+    if (path == null || parent == null)
+      return false;
+    if (parent.length == 0 || path.length != parent.length + 1)
+      return false;
+    boolean isParent = true;
+    for (int i = 0; i < parent.length; i++) {
+      isParent = isParent && Arrays.equals(path[i], parent[i]); 
+    }
+    return isParent;
   }
 
+
   /**
    * Load and merge edits from two edits files
    * 
@@ -2104,6 +2126,22 @@ public class FSImage extends Storage {
     final String s = readString(in);
     return s.isEmpty()? null: s;
   }
+  
+  /**
+   * Reading the path from the image and converting it to byte[][] directly
+   * this saves us an array copy and conversions to and from String
+   * @param in
+   * @return the array each element of which is a byte[] representation 
+   *            of a path component
+   * @throws IOException
+   */
+  public static byte[][] readPathComponents(DataInputStream in)
+      throws IOException {
+      U_STR.readFields(in);
+      return DFSUtil.bytes2byteArray(U_STR.getBytes(),
+        U_STR.getLength(), (byte) Path.SEPARATOR_CHAR);
+    
+  }
 
   // Same comments apply for this method as for readString()
   public static byte[] readBytes(DataInputStream in) throws IOException {

Modified: hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
URL: http://svn.apache.org/viewvc/hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java?rev=961966&r1=961965&r2=961966&view=diff
==============================================================================
--- hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
(original)
+++ hadoop/hdfs/trunk/src/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
Thu Jul  8 22:35:10 2010
@@ -317,7 +317,9 @@ class INodeDirectory extends INode {
    */
   <T extends INode> T addNode(String path, T newNode, boolean inheritPermission
       ) throws FileNotFoundException, UnresolvedLinkException  {
-    if(addToParent(path, newNode, null, inheritPermission, true) == null)
+    byte[][] pathComponents = getPathComponents(path);        
+    if(addToParent(pathComponents, newNode, null,
+                    inheritPermission, true) == null)
       return null;
     return newNode;
   }
@@ -332,24 +334,14 @@ class INodeDirectory extends INode {
    *          is not a directory.
    */
   <T extends INode> INodeDirectory addToParent(
-                                      String path,
-                                      T newNode,
-                                      INodeDirectory parent,
-                                      boolean inheritPermission
-                                    ) throws FileNotFoundException, 
-                                             UnresolvedLinkException {
-    return addToParent(path, newNode, parent, inheritPermission, true);
-  }
-  <T extends INode> INodeDirectory addToParent(
-                                      String path,
+                                      byte[][] pathComponents,
                                       T newNode,
                                       INodeDirectory parent,
                                       boolean inheritPermission,
                                       boolean propagateModTime
                                     ) throws FileNotFoundException, 
                                              UnresolvedLinkException {
-    byte[][] pathComponents = getPathComponents(path);
-    assert pathComponents != null : "Incorrect path " + path;
+              
     int pathLen = pathComponents.length;
     if (pathLen < 2)  // add root
       return null;
@@ -359,10 +351,12 @@ class INodeDirectory extends INode {
       getExistingPathINodes(pathComponents, inodes, false);
       INode inode = inodes[0];
       if (inode == null) {
-        throw new FileNotFoundException("Parent path does not exist: "+path);
+        throw new FileNotFoundException("Parent path does not exist: "+
+            DFSUtil.byteArray2String(pathComponents));
       }
       if (!inode.isDirectory()) {
-        throw new FileNotFoundException("Parent path is not a directory: "+path);
+        throw new FileNotFoundException("Parent path is not a directory: "+
+            DFSUtil.byteArray2String(pathComponents));
       }
       parent = (INodeDirectory)inode;
     }

Added: hadoop/hdfs/trunk/src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/TestPathComponents.java
URL: http://svn.apache.org/viewvc/hadoop/hdfs/trunk/src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/TestPathComponents.java?rev=961966&view=auto
==============================================================================
--- hadoop/hdfs/trunk/src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/TestPathComponents.java
(added)
+++ hadoop/hdfs/trunk/src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/TestPathComponents.java
Thu Jul  8 22:35:10 2010
@@ -0,0 +1,59 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hdfs.server.namenode;
+
+import org.apache.hadoop.hdfs.server.namenode.INode;
+import org.apache.hadoop.hdfs.DFSUtil;
+import org.apache.hadoop.fs.Path;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * 
+ */
+public class TestPathComponents {
+
+  @Test
+  public void testBytes2ByteArray() throws Exception {
+    testString("/");
+    testString("/file");
+    testString("/directory/");
+    testString("//");
+    testString("/dir//file");
+    testString("/dir/dir1//");
+  }
+
+  public void testString(String str) throws Exception {
+    String pathString = str;
+    byte[][] oldPathComponents = INode.getPathComponents(pathString);
+    byte[][] newPathComponents = 
+                DFSUtil.bytes2byteArray(pathString.getBytes("UTF-8"),
+                                        (byte) Path.SEPARATOR_CHAR);
+    if (oldPathComponents[0] == null) {
+      assertTrue(oldPathComponents[0] == newPathComponents[0]);
+    } else {
+      assertTrue("Path components do not match for " + pathString,
+                  Arrays.deepEquals(oldPathComponents, newPathComponents));
+    }
+  }
+}

Propchange: hadoop/hdfs/trunk/src/test/hdfs/org/apache/hadoop/hdfs/server/namenode/TestPathComponents.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message