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
