BlocksMap构造
BlocksMap结构
之前看了HDFS代码，做了一些整理，陆续贴上来，Namenode中最重要的结构是Namespace和BlocksMap，先把BlocksMap写一下。
BlocksMap里面最重要的一个结构是BlocksInfo，先来看一下BlocksInfo
1. Class BlocksInfo extends Block
Block类有三个变量，分别是long blockId; 每个block的id值，唯一的
long numBytes; block的大小
long generationStamp; 时间戳，在修改和append有用
BlockInfo在Block的基础上加入了INodeFile inode; 代表此block对应文件INodeFile
Object[] triplets; 三元组结构，其结构如下
其中，对于副本个数为replica的三元组，其i*replica对应的是该block对应的Datanode对象，保存了其Datanode位置的信息，i*replica+1和i*replica+2为该block对应的Datanode对象上面其他block对象，即形成了一个链表结构。三元组是为了减少内存消耗。
下面是BlockInfo中的重要方法：
1) BlockInfo(Block blk, int replication)
构造函数，设定该blockInfo对象的block属性，同时根据设定的replication对三元组初始化。
2) DatanodeDescriptor getDatanode(int index)
获得三元组中对应副本的Datanode对象，使用的方法是
DatanodeDescriptor node = (DatanodeDescriptor)triplets[index*3];
3) BlockInfo getPrevious(int index)
获得该副本所在Datanode上面前一块BlockInfo对象(链表结构)
方法是：
BlockInfo info = (BlockInfo)triplets[index*3+1];
4) BlockInfo getNext(int index)
获得该副本所在Datanode上面后一块BlockInfo对象(链表结构)
方法是:
BlockInfo info = (BlockInfo)triplets[index*3+2];
5) int numNodes()
获得已经保存到datanode上面的副本个数，如设定副本为3目前保存了2，还有一个没有保存，则返回2
6) int ensureCapacity(int num)
返回最后一个还没有保存datanode信息的三元组中位置，方法是：
int last = numNodes();
if(triplets.length >= (last+num)*3)
return last;
7) boolean addNode(DatanodeDescriptor node)
保存该block对应的Datanode对象，首先找到最后一个没有保存datanode信息的三元组位置，在set即可（一个block对应多个副本，存储在不同的datanode上面，以后再说存储策略）,主要方法为：
setDatanode(lastNode, node);
setNext(lastNode, null);
setPrevious(lastNode, null);
8) int findDatanode(DatanodeDescriptor dn)
查看Datanode对象是否在三元组中，如果在则返回其所在位置，否则返回-1。
9) boolean removeNode(DatanodeDescriptor node)
将Datanode对象从三元组中删除，步骤为：首先上面通过findDatanode()方法获得该Datanode在三元组中位置，再找到最后一个已经赋值的Datanode对象，将最后一个已赋值对象放置在要删除的对象位置，并将所有属性修改，最后将最后一个已赋值对象置为null。代码为：
int lastNode = numNodes()-1;
// replace current node triplet by the lastNode one
setDatanode(dnIndex, getDatanode(lastNode));
setNext(dnIndex, getNext(lastNode));
setPrevious(dnIndex, getPrevious(lastNode));
// set the last triplet to null
setDatanode(lastNode, null);
setNext(lastNode, null);
setPrevious(lastNode, null);
return true;
10) BlockInfo listInsert(BlockInfo head, DatanodeDescriptor dn)
参数中head为头结点，在DatanodeDesciptor中维护着一个头结点变量。本函数涉及三元组结构中i*replica+1和i*replica+2结构，功能是向该Datanode对象添加一个block，方法是将三元组中对应的Datanode对象对应的其他block对象修改为前一个节点为null，后一个节点为head。即将链表的头结点置为head。代码为：
int dnIndex = this.findDatanode(dn);
this.setPrevious(dnIndex, null);
this.setNext(dnIndex, head);
11) BlockInfo listRemove(BlockInfo head, DatanodeDescriptor dn)
参数中head为头结点，此函数功能是datanode中不在保存该block对象，从三元组的i*replica+1和i*replica+2结构中删除。代码为：
int dnIndex = this.findDatanode(dn);
BlockInfo next = this.getNext(dnIndex);
BlockInfo prev = this.getPrevious(dnIndex);
this.setNext(dnIndex, null);
this.setPrevious(dnIndex, null);
if(prev != null)
prev.setNext(prev.findDatanode(dn), next);
if(next != null)
next.setPrevious(next.findDatanode(dn), prev);
if(this == head) // removing the head
head = next;
return head;
是一个典型的链表删除操作。
12) int listCount(DatanodeDescriptor dn)
一个链表遍历操作，将特定datanode上面的所有block遍历，代码是
for(BlockInfo cur = this; cur != null;
cur = cur.getNext(cur.findDatanode(dn)))
count++;
13) boolean listIsConsistent(DatanodeDescriptor dn)
检查一致性，即检查链表中next->prev==cur,代码为
while(cur != null) {
next = cur.getNext(cur.findDatanode(dn));
if(next != null) {
nextPrev = next.getPrevious(next.findDatanode(dn));
if(cur != nextPrev) {
System.out.println("Inconsistent list: cur->next->prev != cur");
return false;
}
}
cur = next;
count++;
}
以上是blocksInfo中的所有方法和结构，总的来说blockInfo维护了一个三元组，并对三元组进行一个操作，设计了所有副本对应的datanode对象以及datanode对象上面保存的其他block对象的信息。
2. BlocksMap中的第二个结构是NodeIterator,下面说明
private static class NodeIterator implements Iterator<DatanodeDescriptor>
这里，NodeIterator是一个迭代器模式，迭代某个blockInfo对象对应的所有datanode对象。在此类中，维护了一个nextIdx,是游标，初始为0，然后根据next()方法不断增加，获得所有的datanode对象。
3. BlocksMap中最重要的结构出现了，为private Map<BlockInfo, BlockInfo> map;
其中key为Block对象，前面说了Block对象之保存了基本信息，该信息是存储在FSImage中的，value为BlockInfo对象，BlockInfo对象是要通过blockReport从datanode上面获得的。如果知道一个Block对象，通过HashMap即可得到该Block的其它信息，维护了一个映射关系。
下面是围绕着该映射关系的一些重要方法。
4. private BlockInfo checkBlockInfo(Block b, int replication)
检查该Block是否在map中，如果不在，生成一个BlockInfo对象，放入map中。
5. INodeFile getINode(Block b)
根据Block对象在map中找到BlockInfo，如果BlockInfo对象存在，获得其对应的INodeFile对象。
6. BlockInfo addINode(Block b, INodeFile iNode)
将Block对象存储在BlocksMap结构中，并且该Block对应的INodeFile指定。
7. void removeINode(Block b)
将该Block对象对应的INodeFile对象删除，同时检查该Block对象如果不属于任何Datanode，则从BlocksMap中删除。
8. removeBlock(BlockInfo blockInfo)
从BlocksMap结构中删除Block对象，同时为了删除Block对象，首先将其对应的INodeFile对象置为null，然后将所有其对应的Datanode对象将该块移除。
9. BlockInfo getStoredBlock(Block b)
从BlocksMap中检索出Block对象对应的BlockInfo对象。
10. Iterator<DatanodeDescriptor> nodeIterator(Block b)
返回迭代器，该迭代器迭代某个Block对象对应的所有Datanode对象。
11. int numNodes(Block b)
返回某个Block对象对应的所有Datanode对象个数，比迭代器快。
12. addNode(Block b, DatanodeDescriptor node, int replication)
removeNode(Block b, DatanodeDescriptor node)
都涉及了DatanodeDescriptor的方法，在DatanodeDescriptor类中在解释。
之前看了HDFS代码，做了一些整理，陆续贴上来，Namenode中最重要的结构是Namespace和BlocksMap，先把BlocksMap写一下。
BlocksMap里面最重要的一个结构是BlocksInfo，先来看一下BlocksInfo
1. Class BlocksInfo extends Block
Block类有三个变量，分别是long blockId; 每个block的id值，唯一的
long numBytes; block的大小
long generationStamp; 时间戳，在修改和append有用
BlockInfo在Block的基础上加入了INodeFile inode; 代表此block对应文件INodeFile
Object[] triplets; 三元组结构，其结构如下
其中，对于副本个数为replica的三元组，其i*replica对应的是该block对应的Datanode对象，保存了其Datanode位置的信息，i*replica+1和i*replica+2为该block对应的Datanode对象上面其他block对象，即形成了一个链表结构。三元组是为了减少内存消耗。
下面是BlockInfo中的重要方法：
1) BlockInfo(Block blk, int replication)
构造函数，设定该blockInfo对象的block属性，同时根据设定的replication对三元组初始化。
2) DatanodeDescriptor getDatanode(int index)
获得三元组中对应副本的Datanode对象，使用的方法是
DatanodeDescriptor node = (DatanodeDescriptor)triplets[index*3];
3) BlockInfo getPrevious(int index)
获得该副本所在Datanode上面前一块BlockInfo对象(链表结构)
方法是：
BlockInfo info = (BlockInfo)triplets[index*3+1];
4) BlockInfo getNext(int index)
获得该副本所在Datanode上面后一块BlockInfo对象(链表结构)
方法是:
BlockInfo info = (BlockInfo)triplets[index*3+2];
5) int numNodes()
获得已经保存到datanode上面的副本个数，如设定副本为3目前保存了2，还有一个没有保存，则返回2
6) int ensureCapacity(int num)
返回最后一个还没有保存datanode信息的三元组中位置，方法是：
int last = numNodes();
if(triplets.length >= (last+num)*3)
return last;
7) boolean addNode(DatanodeDescriptor node)
保存该block对应的Datanode对象，首先找到最后一个没有保存datanode信息的三元组位置，在set即可（一个block对应多个副本，存储在不同的datanode上面，以后再说存储策略）,主要方法为：
setDatanode(lastNode, node);
setNext(lastNode, null);
setPrevious(lastNode, null);
8) int findDatanode(DatanodeDescriptor dn)
查看Datanode对象是否在三元组中，如果在则返回其所在位置，否则返回-1。
9) boolean removeNode(DatanodeDescriptor node)
将Datanode对象从三元组中删除，步骤为：首先上面通过findDatanode()方法获得该Datanode在三元组中位置，再找到最后一个已经赋值的Datanode对象，将最后一个已赋值对象放置在要删除的对象位置，并将所有属性修改，最后将最后一个已赋值对象置为null。代码为：
int lastNode = numNodes()-1;
// replace current node triplet by the lastNode one
setDatanode(dnIndex, getDatanode(lastNode));
setNext(dnIndex, getNext(lastNode));
setPrevious(dnIndex, getPrevious(lastNode));
// set the last triplet to null
setDatanode(lastNode, null);
setNext(lastNode, null);
setPrevious(lastNode, null);
return true;
10) BlockInfo listInsert(BlockInfo head, DatanodeDescriptor dn)
参数中head为头结点，在DatanodeDesciptor中维护着一个头结点变量。本函数涉及三元组结构中i*replica+1和i*replica+2结构，功能是向该Datanode对象添加一个block，方法是将三元组中对应的Datanode对象对应的其他block对象修改为前一个节点为null，后一个节点为head。即将链表的头结点置为head。代码为：
int dnIndex = this.findDatanode(dn);
this.setPrevious(dnIndex, null);
this.setNext(dnIndex, head);
11) BlockInfo listRemove(BlockInfo head, DatanodeDescriptor dn)
参数中head为头结点，此函数功能是datanode中不在保存该block对象，从三元组的i*replica+1和i*replica+2结构中删除。代码为：
int dnIndex = this.findDatanode(dn);
BlockInfo next = this.getNext(dnIndex);
BlockInfo prev = this.getPrevious(dnIndex);
this.setNext(dnIndex, null);
this.setPrevious(dnIndex, null);
if(prev != null)
prev.setNext(prev.findDatanode(dn), next);
if(next != null)
next.setPrevious(next.findDatanode(dn), prev);
if(this == head) // removing the head
head = next;
return head;
是一个典型的链表删除操作。
12) int listCount(DatanodeDescriptor dn)
一个链表遍历操作，将特定datanode上面的所有block遍历，代码是
for(BlockInfo cur = this; cur != null;
cur = cur.getNext(cur.findDatanode(dn)))
count++;
13) boolean listIsConsistent(DatanodeDescriptor dn)
检查一致性，即检查链表中next->prev==cur,代码为
while(cur != null) {
next = cur.getNext(cur.findDatanode(dn));
if(next != null) {
nextPrev = next.getPrevious(next.findDatanode(dn));
if(cur != nextPrev) {
System.out.println("Inconsistent list: cur->next->prev != cur");
return false;
}
}
cur = next;
count++;
}
以上是blocksInfo中的所有方法和结构，总的来说blockInfo维护了一个三元组，并对三元组进行一个操作，设计了所有副本对应的datanode对象以及datanode对象上面保存的其他block对象的信息。
2. BlocksMap中的第二个结构是NodeIterator,下面说明
private static class NodeIterator implements Iterator<DatanodeDescriptor>
这里，NodeIterator是一个迭代器模式，迭代某个blockInfo对象对应的所有datanode对象。在此类中，维护了一个nextIdx,是游标，初始为0，然后根据next()方法不断增加，获得所有的datanode对象。
3. BlocksMap中最重要的结构出现了，为private Map<BlockInfo, BlockInfo> map;
其中key为Block对象，前面说了Block对象之保存了基本信息，该信息是存储在FSImage中的，value为BlockInfo对象，BlockInfo对象是要通过blockReport从datanode上面获得的。如果知道一个Block对象，通过HashMap即可得到该Block的其它信息，维护了一个映射关系。
下面是围绕着该映射关系的一些重要方法。
4. private BlockInfo checkBlockInfo(Block b, int replication)
检查该Block是否在map中，如果不在，生成一个BlockInfo对象，放入map中。
5. INodeFile getINode(Block b)
根据Block对象在map中找到BlockInfo，如果BlockInfo对象存在，获得其对应的INodeFile对象。
6. BlockInfo addINode(Block b, INodeFile iNode)
将Block对象存储在BlocksMap结构中，并且该Block对应的INodeFile指定。
7. void removeINode(Block b)
将该Block对象对应的INodeFile对象删除，同时检查该Block对象如果不属于任何Datanode，则从BlocksMap中删除。
8. removeBlock(BlockInfo blockInfo)
从BlocksMap结构中删除Block对象，同时为了删除Block对象，首先将其对应的INodeFile对象置为null，然后将所有其对应的Datanode对象将该块移除。
9. BlockInfo getStoredBlock(Block b)
从BlocksMap中检索出Block对象对应的BlockInfo对象。
10. Iterator<DatanodeDescriptor> nodeIterator(Block b)
返回迭代器，该迭代器迭代某个Block对象对应的所有Datanode对象。
11. int numNodes(Block b)
返回某个Block对象对应的所有Datanode对象个数，比迭代器快。
12. addNode(Block b, DatanodeDescriptor node, int replication)
removeNode(Block b, DatanodeDescriptor node)
都涉及了DatanodeDescriptor的方法，在DatanodeDescriptor类中在解释。