layout: post
title: "javaCollection和Map源码分析"
category: Study Notes

tags: ["读书", "源码阅读", "Java"]

{% include JB/setup %}

集合包中最常用的是Collection和Map两个接口的实现类。Collection用于存放多个单对象，Map用于存放Key-Value形式的键值对。

Collection中常用的是两种类型的接口：List和Set。两者最明显的差别是List支持放入重复的对象，而Set不支持。

1. ArrayList

实现方式：
ArrayList采用的是数组方式来存放数据。在调用空构造器的情况下会创建一个大小为10的Object数组。

插入对象：

• add（E）

如果插入一个对象以后，ArrayList依然没有满，那就是单纯的将数组中某个元素的值赋值为传入的对象。

如果插入一个对象后，ArrayList会产生溢出，则要将数组的容量扩大。新的数组的容量计算方法为：旧数组容量 * 1.5 + 1。在得到新的数组容量以后，将原数据的数据拷贝到新数组中Arrays.copyOf。

• add（int，E）

允许将元素直接插入指定的int位置上。这个方法的实现首先要确保插入的位置是当前Array数组中存在的，之后还要确保数组的容量是够用的。

在完成以上动作后，它要将数据对象进行一次复制，然后将int指定的index后面的数据往后挪动一位，然后才能将指定的index位置的复制为传入的对象。

{
    fastRemove（）
    将index后的对象往前复制一位
}

删除对象：

• remove（E）

ArrayList首先判断对象是否为null。

如果是null，则遍历数组中已有值的元素，并比较其是否为null，若为null，则调用fastRemove来删除相应位置的对象。fastRemove（）会将index后的对象往前复制一位，并将数组中的最后一个元素的值设置为null，即释放了对此对象的引用。

如果这个对象不是null，唯一的不同在于通过E的equals来比较元素的值是否相同，如相同则认为是需要删除对象的位置，然后同样是通过调用fastRemove来完成对象的删除。

• remove（int）

的实现比remove（E）多了一个数组范围的检测，但少了对象位置的查找，因此性能会更好。

遍历对象：

• iterator（）

当调用hasNext（）方法时，比较当前指向的数组的位置是否和数组中已有的元素的大小相等，如相等则返回false，否则返回true。

当调用next方法时，首先比较在创建此Iterator时获取的modCount与当前的modCount，如果这两个modCount不相等，则说明在获取next元素时，发生了对于集合大小产生影响（新增，删除）的动作。当产生这种情况时，则抛出ConcurrentModificationException。如果modCount相等，则调用get方法来获取相应位置的元素。

判断对象是否存在：

• contains（E）

做法为遍历整个ArrayList中已有的元素，通过equals来判断是否和元素相等。

indexOf和lastIndexOf是ArrayList中用于获得对象所在位置的方法，其中indexOf为从前往后寻找，而lastIndexOf为从后往前寻找。

注意要点：

• ArrayList基于数组方式实现，无容量的限制
• ArrayList在执行插入元素时可能要扩容，在删除元素时并不会减小数组的容量（如希望相应的减少数组容量，可以调用ArrayList的trimToSize（）），在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
• ArrayList是非线程安全的。

2. LinkedList

linkedList基于双向链表机制，所谓双向链表机制是指集合中的每个元素都知道其前一个元素及其后一个元素的位置。这样的机制可以快速实现集合中元素的移动。

LinkedList（）

在创建LinkedList对象时，应首先创建一个element属性为null，next属性为null及previous属性为null的Entry对象，并赋值给全局的header属性。在执行构造器时，LinkedList将header的next及previous都指向header。

add（E）

LinkedList的add方法不用像ArrayList那样，要考虑扩容及复制数组的问题，但它每增加一个元素，都要创建一个新的Entry对象，并要修改相邻的两个元素的属性。

remove（E）

删除时只须直接删除链表上的当前元素，并将当前元素中的element，previous及next属性设置为null，即可完成对象的删除。

get（int）

由于LinkedList的元素并没有存储在一个数组中，因此其get操作过程比ArrayList更为复杂。

首先判断当前要获取的位置是否小于LinkedList值的一半，如小于，则从头一直找到index位置所对象的next元素；如大于，则从队列的尾部往前，一直找到index位置所对应的previous元素。

iterator（）

由于LinkedList是基于双向链接实现的，因此其在遍历时还可往前遍历，通过调用hasPrevious和previous来完成遍历过程。

注意要点：

• LinkedList基于双向链表机制实现。
• LinkedList在插入元素时，须创建一个新的Entry对象，并切换相应元素的前后元素的引用；在查找元素时，须遍历链表；在删除元素时，要遍历链表，找到要删除的元素，然后从链表上将此元素删除即可
• LinkedList是非线程安全

REFERENCE:

林昊，《分布式Java应用》，电子工业出版社，2011

layout: post
title: "分布式系统漫谈 Google三驾马车：GFS"
category: Reading Notes

tags: ["读文章", "分布式系统", "GFS"]

{% include JB/setup %}

Google File System

GFS是一个可扩展的分布式文件系统，用于大型的，分布式，对大量数据进行访问的应用。它运行于廉价的普通硬件上，提供容错功能。

Google设置一个主（master）来保存目录和索引信息，这是为了简化系统结果，提高性能来考虑的，但是这就会造成主（master）成为单点故障或者瓶颈。为了消除主（master）的单点故障Google把每个chunk设置的很大（64M），这样，由于代码访问数据的本地性，application端和master的交互会减少，而主要数据流量都是Application和chunkserver之间的访问。

master所有信息都储存在内存里，启动时信息从chunkserver中获取。

The master stores thress major types of metadata: the file and chunk namespaces,the mapping from files to chunks, and the locations of each chunk's replicas.

Having a single master vastly simplifies our design and enables the master to make sophisticated chunk placement and replication decisions using global knowledge. However, we must minimize its involvement in reads and writes so that it does not become a bottleneck. Clients never read and write file data through the master. Instead, a client asks the master which chunkservers it should contact. It caches this information for a limited time and interacts with the chunkservers directly for many subsequent operations.

Neither the client nor the chunkserver caches file data. Client caches offer little benefit because most applications stream through huge files or have working sets too large to be cached. Not having them simplifies the client and the overall system by eliminating cache coherence issues. Clients do cache metadata, however. Chunkservers need not cache file data because chunks are stored as local files and so Linux's buffer cache already keeps frequently accessed data in memory.

宿主储存三种元文件，文件和chunk的名字，文件和chunk的关联关系，还有每个chunk的位置。

拥有一个宿主很大程度上简化了设计并且能让宿主利用全局的知识来做必要的chunk处理。但是我们也必须减少宿主在读写操作中的参与度以防止宿主变成瓶颈。clients不从宿主中读写文件，而是只向宿主查询chunkserver的信息。client 缓存这个信息一段时间并且直接对chunkserver进行操作。

client和chunkserver都不缓存文件。之所以都不缓存文件是因为很多应用所用的文件都太大去让client缓存，但client缓存元文件。chunkserver也不去缓存文件，因为chunks都储存为本地文件并且linux系统已经将经常使用的数据缓存在内存中了。

GFS对外提供create, delete, open, close, read和write操作，同时还有snapshot和record append.

Snapshot creates a copy of a file or a directory tree at low cost.

Record append allows multiple clients to applend data to the same file concurrently while guaranteeing the atomicity of each individual client's append. 能让多个clients在同一文件后同时添加数据只要每个client所要加的东西都在一起，不会client a和client b要加的数据交叉。client a写了一半写起client b，client b写了一半又开始写client a了。