BlocksMap.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:13k
源码类别:

网格计算

开发平台:

Java

  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;
  19. import java.util.*;
  20. import org.apache.hadoop.hdfs.protocol.Block;
  21. /**
  22.  * This class maintains the map from a block to its metadata.
  23.  * block's metadata currently includes INode it belongs to and
  24.  * the datanodes that store the block.
  25.  */
  26. class BlocksMap {
  27.         
  28.   /**
  29.    * Internal class for block metadata.
  30.    */
  31.   static class BlockInfo extends Block {
  32.     private INodeFile          inode;
  33.     /**
  34.      * This array contains triplets of references.
  35.      * For each i-th data-node the block belongs to
  36.      * triplets[3*i] is the reference to the DatanodeDescriptor
  37.      * and triplets[3*i+1] and triplets[3*i+2] are references 
  38.      * to the previous and the next blocks, respectively, in the 
  39.      * list of blocks belonging to this data-node.
  40.      */
  41.     private Object[] triplets;
  42.     BlockInfo(Block blk, int replication) {
  43.       super(blk);
  44.       this.triplets = new Object[3*replication];
  45.       this.inode = null;
  46.     }
  47.     INodeFile getINode() {
  48.       return inode;
  49.     }
  50.     DatanodeDescriptor getDatanode(int index) {
  51.       assert this.triplets != null : "BlockInfo is not initialized";
  52.       assert index >= 0 && index*3 < triplets.length : "Index is out of bound";
  53.       DatanodeDescriptor node = (DatanodeDescriptor)triplets[index*3];
  54.       assert node == null || 
  55.           DatanodeDescriptor.class.getName().equals(node.getClass().getName()) : 
  56.                 "DatanodeDescriptor is expected at " + index*3;
  57.       return node;
  58.     }
  59.     BlockInfo getPrevious(int index) {
  60.       assert this.triplets != null : "BlockInfo is not initialized";
  61.       assert index >= 0 && index*3+1 < triplets.length : "Index is out of bound";
  62.       BlockInfo info = (BlockInfo)triplets[index*3+1];
  63.       assert info == null || 
  64.           BlockInfo.class.getName().equals(info.getClass().getName()) : 
  65.                 "BlockInfo is expected at " + index*3;
  66.       return info;
  67.     }
  68.     BlockInfo getNext(int index) {
  69.       assert this.triplets != null : "BlockInfo is not initialized";
  70.       assert index >= 0 && index*3+2 < triplets.length : "Index is out of bound";
  71.       BlockInfo info = (BlockInfo)triplets[index*3+2];
  72.       assert info == null || 
  73.           BlockInfo.class.getName().equals(info.getClass().getName()) : 
  74.                 "BlockInfo is expected at " + index*3;
  75.       return info;
  76.     }
  77.     void setDatanode(int index, DatanodeDescriptor node) {
  78.       assert this.triplets != null : "BlockInfo is not initialized";
  79.       assert index >= 0 && index*3 < triplets.length : "Index is out of bound";
  80.       triplets[index*3] = node;
  81.     }
  82.     void setPrevious(int index, BlockInfo to) {
  83.       assert this.triplets != null : "BlockInfo is not initialized";
  84.       assert index >= 0 && index*3+1 < triplets.length : "Index is out of bound";
  85.       triplets[index*3+1] = to;
  86.     }
  87.     void setNext(int index, BlockInfo to) {
  88.       assert this.triplets != null : "BlockInfo is not initialized";
  89.       assert index >= 0 && index*3+2 < triplets.length : "Index is out of bound";
  90.       triplets[index*3+2] = to;
  91.     }
  92.     private int getCapacity() {
  93.       assert this.triplets != null : "BlockInfo is not initialized";
  94.       assert triplets.length % 3 == 0 : "Malformed BlockInfo";
  95.       return triplets.length / 3;
  96.     }
  97.     /**
  98.      * Ensure that there is enough  space to include num more triplets.
  99.      *      * @return first free triplet index.
  100.      */
  101.     private int ensureCapacity(int num) {
  102.       assert this.triplets != null : "BlockInfo is not initialized";
  103.       int last = numNodes();
  104.       if(triplets.length >= (last+num)*3)
  105.         return last;
  106.       /* Not enough space left. Create a new array. Should normally 
  107.        * happen only when replication is manually increased by the user. */
  108.       Object[] old = triplets;
  109.       triplets = new Object[(last+num)*3];
  110.       for(int i=0; i < last*3; i++) {
  111.         triplets[i] = old[i];
  112.       }
  113.       return last;
  114.     }
  115.     /**
  116.      * Count the number of data-nodes the block belongs to.
  117.      */
  118.     int numNodes() {
  119.       assert this.triplets != null : "BlockInfo is not initialized";
  120.       assert triplets.length % 3 == 0 : "Malformed BlockInfo";
  121.       for(int idx = getCapacity()-1; idx >= 0; idx--) {
  122.         if(getDatanode(idx) != null)
  123.           return idx+1;
  124.       }
  125.       return 0;
  126.     }
  127.     /**
  128.      * Add data-node this block belongs to.
  129.      */
  130.     boolean addNode(DatanodeDescriptor node) {
  131.       if(findDatanode(node) >= 0) // the node is already there
  132.         return false;
  133.       // find the last null node
  134.       int lastNode = ensureCapacity(1);
  135.       setDatanode(lastNode, node);
  136.       setNext(lastNode, null);
  137.       setPrevious(lastNode, null);
  138.       return true;
  139.     }
  140.     /**
  141.      * Remove data-node from the block.
  142.      */
  143.     boolean removeNode(DatanodeDescriptor node) {
  144.       int dnIndex = findDatanode(node);
  145.       if(dnIndex < 0) // the node is not found
  146.         return false;
  147.       assert getPrevious(dnIndex) == null && getNext(dnIndex) == null : 
  148.         "Block is still in the list and must be removed first.";
  149.       // find the last not null node
  150.       int lastNode = numNodes()-1; 
  151.       // replace current node triplet by the lastNode one 
  152.       setDatanode(dnIndex, getDatanode(lastNode));
  153.       setNext(dnIndex, getNext(lastNode)); 
  154.       setPrevious(dnIndex, getPrevious(lastNode)); 
  155.       // set the last triplet to null
  156.       setDatanode(lastNode, null);
  157.       setNext(lastNode, null); 
  158.       setPrevious(lastNode, null); 
  159.       return true;
  160.     }
  161.     /**
  162.      * Find specified DatanodeDescriptor.
  163.      * @param dn
  164.      * @return index or -1 if not found.
  165.      */
  166.     int findDatanode(DatanodeDescriptor dn) {
  167.       int len = getCapacity();
  168.       for(int idx = 0; idx < len; idx++) {
  169.         DatanodeDescriptor cur = getDatanode(idx);
  170.         if(cur == dn)
  171.           return idx;
  172.         if(cur == null)
  173.           break;
  174.       }
  175.       return -1;
  176.     }
  177.     /**
  178.      * Insert this block into the head of the list of blocks 
  179.      * related to the specified DatanodeDescriptor.
  180.      * If the head is null then form a new list.
  181.      * @return current block as the new head of the list.
  182.      */
  183.     BlockInfo listInsert(BlockInfo head, DatanodeDescriptor dn) {
  184.       int dnIndex = this.findDatanode(dn);
  185.       assert dnIndex >= 0 : "Data node is not found: current";
  186.       assert getPrevious(dnIndex) == null && getNext(dnIndex) == null : 
  187.               "Block is already in the list and cannot be inserted.";
  188.       this.setPrevious(dnIndex, null);
  189.       this.setNext(dnIndex, head);
  190.       if(head != null)
  191.         head.setPrevious(head.findDatanode(dn), this);
  192.       return this;
  193.     }
  194.     /**
  195.      * Remove this block from the list of blocks 
  196.      * related to the specified DatanodeDescriptor.
  197.      * If this block is the head of the list then return the next block as 
  198.      * the new head.
  199.      * @return the new head of the list or null if the list becomes
  200.      * empy after deletion.
  201.      */
  202.     BlockInfo listRemove(BlockInfo head, DatanodeDescriptor dn) {
  203.       if(head == null)
  204.         return null;
  205.       int dnIndex = this.findDatanode(dn);
  206.       if(dnIndex < 0) // this block is not on the data-node list
  207.         return head;
  208.       BlockInfo next = this.getNext(dnIndex);
  209.       BlockInfo prev = this.getPrevious(dnIndex);
  210.       this.setNext(dnIndex, null);
  211.       this.setPrevious(dnIndex, null);
  212.       if(prev != null)
  213.         prev.setNext(prev.findDatanode(dn), next);
  214.       if(next != null)
  215.         next.setPrevious(next.findDatanode(dn), prev);
  216.       if(this == head)  // removing the head
  217.         head = next;
  218.       return head;
  219.     }
  220.     int listCount(DatanodeDescriptor dn) {
  221.       int count = 0;
  222.       for(BlockInfo cur = this; cur != null;
  223.             cur = cur.getNext(cur.findDatanode(dn)))
  224.         count++;
  225.       return count;
  226.     }
  227.     boolean listIsConsistent(DatanodeDescriptor dn) {
  228.       // going forward
  229.       int count = 0;
  230.       BlockInfo next, nextPrev;
  231.       BlockInfo cur = this;
  232.       while(cur != null) {
  233.         next = cur.getNext(cur.findDatanode(dn));
  234.         if(next != null) {
  235.           nextPrev = next.getPrevious(next.findDatanode(dn));
  236.           if(cur != nextPrev) {
  237.             System.out.println("Inconsistent list: cur->next->prev != cur");
  238.             return false;
  239.           }
  240.         }
  241.         cur = next;
  242.         count++;
  243.       }
  244.       return true;
  245.     }
  246.   }
  247.   private static class NodeIterator implements Iterator<DatanodeDescriptor> {
  248.     private BlockInfo blockInfo;
  249.     private int nextIdx = 0;
  250.       
  251.     NodeIterator(BlockInfo blkInfo) {
  252.       this.blockInfo = blkInfo;
  253.     }
  254.     public boolean hasNext() {
  255.       return blockInfo != null && nextIdx < blockInfo.getCapacity()
  256.               && blockInfo.getDatanode(nextIdx) != null;
  257.     }
  258.     public DatanodeDescriptor next() {
  259.       return blockInfo.getDatanode(nextIdx++);
  260.     }
  261.     public void remove()  {
  262.       throw new UnsupportedOperationException("Sorry. can't remove.");
  263.     }
  264.   }
  265.   private Map<Block, BlockInfo> map = new HashMap<Block, BlockInfo>();
  266.   /**
  267.    * Add BlockInfo if mapping does not exist.
  268.    */
  269.   private BlockInfo checkBlockInfo(Block b, int replication) {
  270.     BlockInfo info = map.get(b);
  271.     if (info == null) {
  272.       info = new BlockInfo(b, replication);
  273.       map.put(info, info);
  274.     }
  275.     return info;
  276.   }
  277.   INodeFile getINode(Block b) {
  278.     BlockInfo info = map.get(b);
  279.     return (info != null) ? info.inode : null;
  280.   }
  281.   /**
  282.    * Add block b belonging to the specified file inode to the map.
  283.    */
  284.   BlockInfo addINode(Block b, INodeFile iNode) {
  285.     BlockInfo info = checkBlockInfo(b, iNode.getReplication());
  286.     info.inode = iNode;
  287.     return info;
  288.   }
  289.   /**
  290.    * Remove INode reference from block b.
  291.    * If it does not belong to any file and data-nodes,
  292.    * then remove the block from the block map.
  293.    */
  294.   void removeINode(Block b) {
  295.     BlockInfo info = map.get(b);
  296.     if (info != null) {
  297.       info.inode = null;
  298.       if (info.getDatanode(0) == null) {  // no datanodes left
  299.         map.remove(b);  // remove block from the map
  300.       }
  301.     }
  302.   }
  303.   /**
  304.    * Remove the block from the block map;
  305.    * remove it from all data-node lists it belongs to;
  306.    * and remove all data-node locations associated with the block.
  307.    */
  308.   void removeBlock(BlockInfo blockInfo) {
  309.     if (blockInfo == null)
  310.       return;
  311.     blockInfo.inode = null;
  312.     for(int idx = blockInfo.numNodes()-1; idx >= 0; idx--) {
  313.       DatanodeDescriptor dn = blockInfo.getDatanode(idx);
  314.       dn.removeBlock(blockInfo); // remove from the list and wipe the location
  315.     }
  316.     map.remove(blockInfo);  // remove block from the map
  317.   }
  318.   /** Returns the block object it it exists in the map. */
  319.   BlockInfo getStoredBlock(Block b) {
  320.     return map.get(b);
  321.   }
  322.   /** Returned Iterator does not support. */
  323.   Iterator<DatanodeDescriptor> nodeIterator(Block b) {
  324.     return new NodeIterator(map.get(b));
  325.   }
  326.   /** counts number of containing nodes. Better than using iterator. */
  327.   int numNodes(Block b) {
  328.     BlockInfo info = map.get(b);
  329.     return info == null ? 0 : info.numNodes();
  330.   }
  331.   /** returns true if the node does not already exists and is added.
  332.    * false if the node already exists.*/
  333.   boolean addNode(Block b, DatanodeDescriptor node, int replication) {
  334.     // insert into the map if not there yet
  335.     BlockInfo info = checkBlockInfo(b, replication);
  336.     // add block to the data-node list and the node to the block info
  337.     return node.addBlock(info);
  338.   }
  339.   /**
  340.    * Remove data-node reference from the block.
  341.    * Remove the block from the block map
  342.    * only if it does not belong to any file and data-nodes.
  343.    */
  344.   boolean removeNode(Block b, DatanodeDescriptor node) {
  345.     BlockInfo info = map.get(b);
  346.     if (info == null)
  347.       return false;
  348.     // remove block from the data-node list and the node from the block info
  349.     boolean removed = node.removeBlock(info);
  350.     if (info.getDatanode(0) == null     // no datanodes left
  351.               && info.inode == null) {  // does not belong to a file
  352.       map.remove(b);  // remove block from the map
  353.     }
  354.     return removed;
  355.   }
  356.   int size() {
  357.     return map.size();
  358.   }
  359.   Collection<BlockInfo> getBlocks() {
  360.     return map.values();
  361.   }
  362.   /**
  363.    * Check if the block exists in map
  364.    */
  365.   boolean contains(Block block) {
  366.     return map.containsKey(block);
  367.   }
  368.   
  369.   /**
  370.    * Check if the replica at the given datanode exists in map
  371.    */
  372.   boolean contains(Block block, DatanodeDescriptor datanode) {
  373.     BlockInfo info = map.get(block);
  374.     if (info == null)
  375.       return false;
  376.     
  377.     if (-1 == info.findDatanode(datanode))
  378.       return false;
  379.     
  380.     return true;
  381.   }
  382. }