1 /** 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 package org.apache.hadoop.hdfs.server.namenode.snapshot; 19 20 import java.io.PrintWriter; 21 import java.util.ArrayList; 22 import java.util.Collections; 23 import java.util.Iterator; 24 import java.util.LinkedList; 25 import java.util.List; 26 27 import org.apache.hadoop.HadoopIllegalArgumentException; 28 import org.apache.hadoop.classification.InterfaceAudience; 29 import org.apache.hadoop.hdfs.DFSUtil; 30 import org.apache.hadoop.hdfs.protocol.QuotaExceededException; 31 import org.apache.hadoop.hdfs.protocol.SnapshotException; 32 import org.apache.hadoop.hdfs.server.blockmanagement.BlockStoragePolicySuite; 33 import org.apache.hadoop.hdfs.server.namenode.Content; 34 import org.apache.hadoop.hdfs.server.namenode.ContentSummaryComputationContext; 35 import org.apache.hadoop.hdfs.server.namenode.INode; 36 import org.apache.hadoop.hdfs.server.namenode.INode.BlocksMapUpdateInfo; 37 import org.apache.hadoop.hdfs.server.namenode.INodeDirectory; 38 import org.apache.hadoop.hdfs.server.namenode.INodeDirectory.SnapshotAndINode; 39 import org.apache.hadoop.hdfs.server.namenode.INodeFile; 40 import org.apache.hadoop.hdfs.server.namenode.INodeReference; 41 import org.apache.hadoop.hdfs.server.namenode.INodeReference.WithCount; 42 import org.apache.hadoop.hdfs.server.namenode.INodeReference.WithName; 43 import org.apache.hadoop.hdfs.server.namenode.QuotaCounts; 44 import org.apache.hadoop.hdfs.util.Diff.ListType; 45 import org.apache.hadoop.hdfs.util.ReadOnlyList; 46 import org.apache.hadoop.util.Time; 47 48 import com.google.common.annotations.VisibleForTesting; 49 import com.google.common.base.Preconditions; 50 import com.google.common.collect.Lists; 51 52 /** 53 * A directory with this feature is a snapshottable directory, where snapshots 54 * can be taken. This feature extends {@link DirectoryWithSnapshotFeature}, and 55 * maintains extra information about all the snapshots taken on this directory. 56 */ 57 @InterfaceAudience.Private 58 public class DirectorySnapshottableFeature extends DirectoryWithSnapshotFeature { 59 /** Limit the number of snapshot per snapshottable directory. */ 60 static final int SNAPSHOT_LIMIT = 1 << 16; 61 62 /** 63 * Snapshots of this directory in ascending order of snapshot names. 64 * Note that snapshots in ascending order of snapshot id are stored in 65 * {@link DirectoryWithSnapshotFeature}.diffs (a private field). 66 */ 67 private final List<Snapshot> snapshotsByNames = new ArrayList<Snapshot>(); 68 /** Number of snapshots allowed. */ 69 private int snapshotQuota = SNAPSHOT_LIMIT; 70 DirectorySnapshottableFeature(DirectoryWithSnapshotFeature feature)71 public DirectorySnapshottableFeature(DirectoryWithSnapshotFeature feature) { 72 super(feature == null ? null : feature.getDiffs()); 73 } 74 75 /** @return the number of existing snapshots. */ getNumSnapshots()76 public int getNumSnapshots() { 77 return snapshotsByNames.size(); 78 } 79 searchSnapshot(byte[] snapshotName)80 private int searchSnapshot(byte[] snapshotName) { 81 return Collections.binarySearch(snapshotsByNames, snapshotName); 82 } 83 84 /** @return the snapshot with the given name. */ getSnapshot(byte[] snapshotName)85 public Snapshot getSnapshot(byte[] snapshotName) { 86 final int i = searchSnapshot(snapshotName); 87 return i < 0? null: snapshotsByNames.get(i); 88 } 89 getSnapshotById(int sid)90 public Snapshot getSnapshotById(int sid) { 91 for (Snapshot s : snapshotsByNames) { 92 if (s.getId() == sid) { 93 return s; 94 } 95 } 96 return null; 97 } 98 99 /** @return {@link #snapshotsByNames} as a {@link ReadOnlyList} */ getSnapshotList()100 public ReadOnlyList<Snapshot> getSnapshotList() { 101 return ReadOnlyList.Util.asReadOnlyList(snapshotsByNames); 102 } 103 104 /** 105 * Rename a snapshot 106 * @param path 107 * The directory path where the snapshot was taken. Used for 108 * generating exception message. 109 * @param oldName 110 * Old name of the snapshot 111 * @param newName 112 * New name the snapshot will be renamed to 113 * @throws SnapshotException 114 * Throw SnapshotException when either the snapshot with the old 115 * name does not exist or a snapshot with the new name already 116 * exists 117 */ renameSnapshot(String path, String oldName, String newName)118 public void renameSnapshot(String path, String oldName, String newName) 119 throws SnapshotException { 120 if (newName.equals(oldName)) { 121 return; 122 } 123 final int indexOfOld = searchSnapshot(DFSUtil.string2Bytes(oldName)); 124 if (indexOfOld < 0) { 125 throw new SnapshotException("The snapshot " + oldName 126 + " does not exist for directory " + path); 127 } else { 128 final byte[] newNameBytes = DFSUtil.string2Bytes(newName); 129 int indexOfNew = searchSnapshot(newNameBytes); 130 if (indexOfNew >= 0) { 131 throw new SnapshotException("The snapshot " + newName 132 + " already exists for directory " + path); 133 } 134 // remove the one with old name from snapshotsByNames 135 Snapshot snapshot = snapshotsByNames.remove(indexOfOld); 136 final INodeDirectory ssRoot = snapshot.getRoot(); 137 ssRoot.setLocalName(newNameBytes); 138 indexOfNew = -indexOfNew - 1; 139 if (indexOfNew <= indexOfOld) { 140 snapshotsByNames.add(indexOfNew, snapshot); 141 } else { // indexOfNew > indexOfOld 142 snapshotsByNames.add(indexOfNew - 1, snapshot); 143 } 144 } 145 } 146 getSnapshotQuota()147 public int getSnapshotQuota() { 148 return snapshotQuota; 149 } 150 setSnapshotQuota(int snapshotQuota)151 public void setSnapshotQuota(int snapshotQuota) { 152 if (snapshotQuota < 0) { 153 throw new HadoopIllegalArgumentException( 154 "Cannot set snapshot quota to " + snapshotQuota + " < 0"); 155 } 156 this.snapshotQuota = snapshotQuota; 157 } 158 159 /** 160 * Simply add a snapshot into the {@link #snapshotsByNames}. Used when loading 161 * fsimage. 162 */ addSnapshot(Snapshot snapshot)163 void addSnapshot(Snapshot snapshot) { 164 this.snapshotsByNames.add(snapshot); 165 } 166 167 /** Add a snapshot. */ addSnapshot(INodeDirectory snapshotRoot, int id, String name)168 public Snapshot addSnapshot(INodeDirectory snapshotRoot, int id, String name) 169 throws SnapshotException, QuotaExceededException { 170 //check snapshot quota 171 final int n = getNumSnapshots(); 172 if (n + 1 > snapshotQuota) { 173 throw new SnapshotException("Failed to add snapshot: there are already " 174 + n + " snapshot(s) and the snapshot quota is " 175 + snapshotQuota); 176 } 177 final Snapshot s = new Snapshot(id, name, snapshotRoot); 178 final byte[] nameBytes = s.getRoot().getLocalNameBytes(); 179 final int i = searchSnapshot(nameBytes); 180 if (i >= 0) { 181 throw new SnapshotException("Failed to add snapshot: there is already a " 182 + "snapshot with the same name \"" + Snapshot.getSnapshotName(s) + "\"."); 183 } 184 185 final DirectoryDiff d = getDiffs().addDiff(id, snapshotRoot); 186 d.setSnapshotRoot(s.getRoot()); 187 snapshotsByNames.add(-i - 1, s); 188 189 // set modification time 190 final long now = Time.now(); 191 snapshotRoot.updateModificationTime(now, Snapshot.CURRENT_STATE_ID); 192 s.getRoot().setModificationTime(now, Snapshot.CURRENT_STATE_ID); 193 return s; 194 } 195 196 /** 197 * Remove the snapshot with the given name from {@link #snapshotsByNames}, 198 * and delete all the corresponding DirectoryDiff. 199 * 200 * @param snapshotRoot The directory where we take snapshots 201 * @param snapshotName The name of the snapshot to be removed 202 * @param collectedBlocks Used to collect information to update blocksMap 203 * @return The removed snapshot. Null if no snapshot with the given name 204 * exists. 205 */ removeSnapshot(BlockStoragePolicySuite bsps, INodeDirectory snapshotRoot, String snapshotName, BlocksMapUpdateInfo collectedBlocks, final List<INode> removedINodes)206 public Snapshot removeSnapshot(BlockStoragePolicySuite bsps, INodeDirectory snapshotRoot, 207 String snapshotName, BlocksMapUpdateInfo collectedBlocks, 208 final List<INode> removedINodes) throws SnapshotException { 209 final int i = searchSnapshot(DFSUtil.string2Bytes(snapshotName)); 210 if (i < 0) { 211 throw new SnapshotException("Cannot delete snapshot " + snapshotName 212 + " from path " + snapshotRoot.getFullPathName() 213 + ": the snapshot does not exist."); 214 } else { 215 final Snapshot snapshot = snapshotsByNames.get(i); 216 int prior = Snapshot.findLatestSnapshot(snapshotRoot, snapshot.getId()); 217 try { 218 QuotaCounts counts = snapshotRoot.cleanSubtree(bsps, snapshot.getId(), 219 prior, collectedBlocks, removedINodes); 220 INodeDirectory parent = snapshotRoot.getParent(); 221 if (parent != null) { 222 // there will not be any WithName node corresponding to the deleted 223 // snapshot, thus only update the quota usage in the current tree 224 parent.addSpaceConsumed(counts.negation(), true); 225 } 226 } catch(QuotaExceededException e) { 227 INode.LOG.error("BUG: removeSnapshot increases namespace usage.", e); 228 } 229 // remove from snapshotsByNames after successfully cleaning the subtree 230 snapshotsByNames.remove(i); 231 return snapshot; 232 } 233 } 234 computeContentSummary( final BlockStoragePolicySuite bsps, final INodeDirectory snapshotRoot, final ContentSummaryComputationContext summary)235 public ContentSummaryComputationContext computeContentSummary( 236 final BlockStoragePolicySuite bsps, 237 final INodeDirectory snapshotRoot, 238 final ContentSummaryComputationContext summary) { 239 snapshotRoot.computeContentSummary(summary); 240 summary.getCounts().addContent(Content.SNAPSHOT, snapshotsByNames.size()); 241 summary.getCounts().addContent(Content.SNAPSHOTTABLE_DIRECTORY, 1); 242 return summary; 243 } 244 245 /** 246 * Compute the difference between two snapshots (or a snapshot and the current 247 * directory) of the directory. 248 * 249 * @param from The name of the start point of the comparison. Null indicating 250 * the current tree. 251 * @param to The name of the end point. Null indicating the current tree. 252 * @return The difference between the start/end points. 253 * @throws SnapshotException If there is no snapshot matching the starting 254 * point, or if endSnapshotName is not null but cannot be identified 255 * as a previous snapshot. 256 */ computeDiff(final INodeDirectory snapshotRoot, final String from, final String to)257 SnapshotDiffInfo computeDiff(final INodeDirectory snapshotRoot, 258 final String from, final String to) throws SnapshotException { 259 Snapshot fromSnapshot = getSnapshotByName(snapshotRoot, from); 260 Snapshot toSnapshot = getSnapshotByName(snapshotRoot, to); 261 // if the start point is equal to the end point, return null 262 if (from.equals(to)) { 263 return null; 264 } 265 SnapshotDiffInfo diffs = new SnapshotDiffInfo(snapshotRoot, fromSnapshot, 266 toSnapshot); 267 computeDiffRecursively(snapshotRoot, snapshotRoot, new ArrayList<byte[]>(), 268 diffs); 269 return diffs; 270 } 271 272 /** 273 * Find the snapshot matching the given name. 274 * 275 * @param snapshotRoot The directory where snapshots were taken. 276 * @param snapshotName The name of the snapshot. 277 * @return The corresponding snapshot. Null if snapshotName is null or empty. 278 * @throws SnapshotException If snapshotName is not null or empty, but there 279 * is no snapshot matching the name. 280 */ getSnapshotByName(INodeDirectory snapshotRoot, String snapshotName)281 private Snapshot getSnapshotByName(INodeDirectory snapshotRoot, 282 String snapshotName) throws SnapshotException { 283 Snapshot s = null; 284 if (snapshotName != null && !snapshotName.isEmpty()) { 285 final int index = searchSnapshot(DFSUtil.string2Bytes(snapshotName)); 286 if (index < 0) { 287 throw new SnapshotException("Cannot find the snapshot of directory " 288 + snapshotRoot.getFullPathName() + " with name " + snapshotName); 289 } 290 s = snapshotsByNames.get(index); 291 } 292 return s; 293 } 294 295 /** 296 * Recursively compute the difference between snapshots under a given 297 * directory/file. 298 * @param snapshotRoot The directory where snapshots were taken. 299 * @param node The directory/file under which the diff is computed. 300 * @param parentPath Relative path (corresponding to the snapshot root) of 301 * the node's parent. 302 * @param diffReport data structure used to store the diff. 303 */ computeDiffRecursively(final INodeDirectory snapshotRoot, INode node, List<byte[]> parentPath, SnapshotDiffInfo diffReport)304 private void computeDiffRecursively(final INodeDirectory snapshotRoot, 305 INode node, List<byte[]> parentPath, SnapshotDiffInfo diffReport) { 306 final Snapshot earlierSnapshot = diffReport.isFromEarlier() ? 307 diffReport.getFrom() : diffReport.getTo(); 308 final Snapshot laterSnapshot = diffReport.isFromEarlier() ? 309 diffReport.getTo() : diffReport.getFrom(); 310 byte[][] relativePath = parentPath.toArray(new byte[parentPath.size()][]); 311 if (node.isDirectory()) { 312 final ChildrenDiff diff = new ChildrenDiff(); 313 INodeDirectory dir = node.asDirectory(); 314 DirectoryWithSnapshotFeature sf = dir.getDirectoryWithSnapshotFeature(); 315 if (sf != null) { 316 boolean change = sf.computeDiffBetweenSnapshots(earlierSnapshot, 317 laterSnapshot, diff, dir); 318 if (change) { 319 diffReport.addDirDiff(dir, relativePath, diff); 320 } 321 } 322 ReadOnlyList<INode> children = dir.getChildrenList(earlierSnapshot 323 .getId()); 324 for (INode child : children) { 325 final byte[] name = child.getLocalNameBytes(); 326 boolean toProcess = diff.searchIndex(ListType.DELETED, name) < 0; 327 if (!toProcess && child instanceof INodeReference.WithName) { 328 byte[][] renameTargetPath = findRenameTargetPath( 329 snapshotRoot, (WithName) child, 330 laterSnapshot == null ? Snapshot.CURRENT_STATE_ID : 331 laterSnapshot.getId()); 332 if (renameTargetPath != null) { 333 toProcess = true; 334 diffReport.setRenameTarget(child.getId(), renameTargetPath); 335 } 336 } 337 if (toProcess) { 338 parentPath.add(name); 339 computeDiffRecursively(snapshotRoot, child, parentPath, diffReport); 340 parentPath.remove(parentPath.size() - 1); 341 } 342 } 343 } else if (node.isFile() && node.asFile().isWithSnapshot()) { 344 INodeFile file = node.asFile(); 345 boolean change = file.getFileWithSnapshotFeature() 346 .changedBetweenSnapshots(file, earlierSnapshot, laterSnapshot); 347 if (change) { 348 diffReport.addFileDiff(file, relativePath); 349 } 350 } 351 } 352 353 /** 354 * We just found a deleted WithName node as the source of a rename operation. 355 * However, we should include it in our snapshot diff report as rename only 356 * if the rename target is also under the same snapshottable directory. 357 */ 358 private byte[][] findRenameTargetPath(final INodeDirectory snapshotRoot, 359 INodeReference.WithName wn, final int snapshotId) { 360 INode inode = wn.getReferredINode(); 361 final LinkedList<byte[]> ancestors = Lists.newLinkedList(); 362 while (inode != null) { 363 if (inode == snapshotRoot) { 364 return ancestors.toArray(new byte[ancestors.size()][]); 365 } 366 if (inode instanceof INodeReference.WithCount) { 367 inode = ((WithCount) inode).getParentRef(snapshotId); 368 } else { 369 INode parent = inode.getParentReference() != null ? inode 370 .getParentReference() : inode.getParent(); 371 if (parent != null && parent instanceof INodeDirectory) { 372 int sid = parent.asDirectory().searchChild(inode); 373 if (sid < snapshotId) { 374 return null; 375 } 376 } 377 if (!(parent instanceof WithCount)) { 378 ancestors.addFirst(inode.getLocalNameBytes()); 379 } 380 inode = parent; 381 } 382 } 383 return null; 384 } 385 386 @Override 387 public String toString() { 388 return "snapshotsByNames=" + snapshotsByNames; 389 } 390 391 @VisibleForTesting 392 public void dumpTreeRecursively(INodeDirectory snapshotRoot, PrintWriter out, 393 StringBuilder prefix, int snapshot) { 394 if (snapshot == Snapshot.CURRENT_STATE_ID) { 395 out.println(); 396 out.print(prefix); 397 398 out.print("Snapshot of "); 399 final String name = snapshotRoot.getLocalName(); 400 out.print(name.isEmpty()? "/": name); 401 out.print(": quota="); 402 out.print(getSnapshotQuota()); 403 404 int n = 0; 405 for(DirectoryDiff diff : getDiffs()) { 406 if (diff.isSnapshotRoot()) { 407 n++; 408 } 409 } 410 Preconditions.checkState(n == snapshotsByNames.size(), "#n=" + n 411 + ", snapshotsByNames.size()=" + snapshotsByNames.size()); 412 out.print(", #snapshot="); 413 out.println(n); 414 415 INodeDirectory.dumpTreeRecursively(out, prefix, 416 new Iterable<SnapshotAndINode>() { 417 @Override 418 public Iterator<SnapshotAndINode> iterator() { 419 return new Iterator<SnapshotAndINode>() { 420 final Iterator<DirectoryDiff> i = getDiffs().iterator(); 421 private DirectoryDiff next = findNext(); 422 423 private DirectoryDiff findNext() { 424 for(; i.hasNext(); ) { 425 final DirectoryDiff diff = i.next(); 426 if (diff.isSnapshotRoot()) { 427 return diff; 428 } 429 } 430 return null; 431 } 432 433 @Override 434 public boolean hasNext() { 435 return next != null; 436 } 437 438 @Override 439 public SnapshotAndINode next() { 440 final SnapshotAndINode pair = new SnapshotAndINode(next 441 .getSnapshotId(), getSnapshotById(next.getSnapshotId()) 442 .getRoot()); 443 next = findNext(); 444 return pair; 445 } 446 447 @Override 448 public void remove() { 449 throw new UnsupportedOperationException(); 450 } 451 }; 452 } 453 }); 454 } 455 } 456 } 457