中文亚洲欧美,国产精品成人品,国产欧美午夜

java io以及unix io模型

nod0620 — Thu, 29 Sep 2011 05:15:00 GMT

摘要: IO分两个阶�D�： 1.通知内核准备数据�?.数据从内核缓冲区拯��到应用缓冲区 �Ҏ��q?点IO�c�d��可以分成�Q?1.��d��IO�Q�在两个阶段上面都是��d��的�?2.非阻塞IO�Q�在�W?阶段�Q�程序不断的轮询直到数据准备好，�W?阶段�q�是��d��?3.IO复用�Q�在�W?阶段�Q�当一个或者多个IO准备��q�A�Ӟ��通知�E�序�Q�第2阶段�q�是��d��的，在第1阶段�q�是轮询实现的，只是所有的IO都集中在一个地方，�q�个地方�q?.. 阅读全文

nod0620 2011-09-29 13:15 发表评论

nod0620 — Tue, 20 Sep 2011 14:27:00 GMT

摘要: 囑ַ��Ҏ��U�程池的�cȝ��构，双��是放入线�E�池执行的�Q务类�l�构ExecutorServiceExecutorService定义了线�E�池的基本的�Ҏ��Q�AbstractExecutorService是个抽象�c�，实现了ExecutorService的部分，主要是实��C��几个submit()�Ҏ��Q��ƈ且提供方法将提交�q�来的�Q务封装成FutureTask,ThreadPoolExecutor则实现线�E�池的管理Futu... 阅读全文

nod0620 2011-09-20 22:27 发表评论

java thread 之Lock

nod0620 — Sat, 17 Sep 2011 16:12:00 GMT

concurrent包里面有很多Lock的具体实玎ͼ�其具体的实现都是��Z��AQS实现�?br />
ReentrantLock
ReentrantLock是可重入的互斥锁�Q�重�Ҏ��重入和互斥，ReentrantLock ��由最�q�成功获得锁的线�E�所持有�Q�当�q�个�U�程再次��试拥有�q�个Lock时就是重入。互斥就�?br />在某一旉��只有一个线�E�能持有Lock�?br />    public void lock() {
        sync.lock();
    }
获得锁方法，Sync是AQS的抽象子�c�，实现可重入和互斥的大部分功能。在Sync的子�c�M��有FairSync和NonfairSync两种代表公��^锁策略和非公�q�锁�{�略

Sync lock�Ҏ��留给子类��d��玎ͼ�NonfairSync的实玎ͼ�
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }
不管是不是有其他�U�程在AQS的阻塞的队列里面�Q�如果当前线�E�能获得�U�程�Q�就直接获得�U�程�Q�不行的话执行AQS的acquire()�Ҏ��Q�基本就是进入阻塞队列的命了�?br />关键�?AQS的acquire()中调用的tryAcquire(int arg)是留�l�子�c�d��现的�Q�是在进入阻塞队列前再尝试一�ơ获取锁(lock()�Ҏ��到这个点上面可能其他�U�程已经释放�?

NonfairSync的tryAcquire(int arg)调用的nonfairTryAcquire()实现:
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {//关键�?
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;//关键�?
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
关键�?�Q�state�?�Q�没有线�E�请求锁�Q�直接分配给本线�E?br />关键�?. 如果本线�E�已�l�得到锁�Q�state�?�Q�即重入�?br />
FairSync的实�?
    final void lock() {
            acquire(1);//关键�?
        }
    protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (isFirst(current) && //关键�?
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
关键�?�Q�公�q�策略，没有�l�当前线�E�优�?br />关键�?�Q�判断当前线�E�有没有在阻塞队列的�W�一位，没在�W�一位不往下��l�执行，�q�样先给��d��队列的线�E�机会，�q�样做速度比较慢，吞吐量比较小

    public boolean tryLock() {
        return sync.nonfairTryAcquire(1);
    }
tryLock��试获得锁，不能获得话就直接�q�回�Q�没有公�q�策略一说�?br />
unlock
    public void unlock() {
        sync.release(1);
    }

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }
tryRelease()留给AQS子类执行�Q?br />        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }
如果state被减后还不�ؓ0�Q�表�C��个锁被一个线�E�重入后�q�没有完全释放，release()�Ҏ��后面不会执行�Q�也��是不会执行unpark��d��队列中的�U�程.

ReentrantReadWriteLock
ReentrantReadWriteLock内部有两个锁�Q�互斥可重入的WriteLock和共享的ReadLock
内部实现中state字段的高16位代表的是read count�Q�低16位代表的是write count
AQS的实��C��有NonfairSync和FairSync之分�Q?br />主要区别是同时有��d��U�程时候对待读写线�E�策略不同�?br />NonfairSync:
final boolean writerShouldBlock(Thread current) {
            return false; // writers can always barge
        }
        final boolean readerShouldBlock(Thread current) {
            /* As a heuristic to avoid indefinite writer starvation,
             * block if the thread that momentarily appears to be head
             * of queue, if one exists, is a waiting writer. This is
             * only a probablistic effect since a new reader will not
             * block if there is a waiting writer behind other enabled
             * readers that have not yet drained from the queue.
             */
            return apparentlyFirstQueuedIsExclusive();
        }
write永远都不��d��Q�read的话看阻塞队列header之后的node是不是write的，如果是就��d��Q�可以避免read一直运行导致的write饥饿�?br />FairSync�Q?br />      final boolean writerShouldBlock(Thread current) {
            // only proceed if queue is empty or current thread at head
            return !isFirst(current);
        }
        final boolean readerShouldBlock(Thread current) {
            // only proceed if queue is empty or current thread at head
            return !isFirst(current);
        }
write和read都有判断是不是阻塞队列header后的�W�一个node�?br />
对于ReadLock
     public void lock() {
            sync.acquireShared(1);
        }
调用AQS的acquireShared()�Q�其中会执行留给AQS子类实现的tryAcquireShared():
protected final int tryAcquireShared(int unused) {
            /*
             * Walkthrough:
             * 1. If write lock held by another thread, fail
             * 2. If count saturated, throw error
             * 3. Otherwise, this thread is eligible for
             *    lock wrt state, so ask if it should block
             *    because of queue policy. If not, try
             *    to grant by CASing state and updating count.
             *    Note that step does not check for reentrant
             *    acquires, which is postponed to full version
             *    to avoid having to check hold count in
             *    the more typical non-reentrant case.
             * 4. If step 3 fails either because thread
             *    apparently not eligible or CAS fails,
             *    chain to version with full retry loop.
             */
            Thread current = Thread.currentThread();
            int c = getState();
            if (exclusiveCount(c) != 0 &&
                getExclusiveOwnerThread() != current)
                return -1;
            if (sharedCount(c) == MAX_COUNT)
                throw new Error("Maximum lock count exceeded");
            if (!readerShouldBlock(current) &&
                compareAndSetState(c, c + SHARED_UNIT)) {
                HoldCounter rh = cachedHoldCounter;
                if (rh == null || rh.tid != current.getId())
                    cachedHoldCounter = rh = readHolds.get();
                rh.count++;
                return 1;
            }
            return fullTryAcquireShared(current);
        }
�{�略是以下的几点�Q?br />1.如果当前write持有锁，直接�q�回-1.
2.没有write持有锁，判断是否需要阻塞读��h��Q�之后原子更新read count
3.上面成功后就�q�回1�Q�不成功的话在��@环中试着��d��Q?br />     final int fullTryAcquireShared(Thread current) {
            /*
             * This code is in part redundant with that in
             * tryAcquireShared but is simpler overall by not
             * complicating tryAcquireShared with interactions between
             * retries and lazily reading hold counts.
             */
            HoldCounter rh = cachedHoldCounter;
            if (rh == null || rh.tid != current.getId())
                rh = readHolds.get();
            for (;;) {
                int c = getState();
                int w = exclusiveCount(c);
                if ((w != 0 && getExclusiveOwnerThread() != current) ||
                    ((rh.count | w) == 0 && readerShouldBlock(current)))
                    return -1;
                if (sharedCount(c) == MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
                if (compareAndSetState(c, c + SHARED_UNIT)) {
                    cachedHoldCounter = rh; // cache for release
                    rh.count++;
                    return 1;
                }
            }
        }
unLock�Ҏ��是��read count �?�Q�然后查看阻塞队列有没有�U�程需要unpark

WriteLock的实现和ReetrantLock的实现是一致的
Semaphore
Semaphore是信号量的概念，主要控制同一旉��内对讉K��资源的线�E�数的控制。底层实现是AQS�?br />acquireShared()和releaseShared().

CountDownLatch
CountDownLatch在完成一�l�正在其他线�E�中执行的操作之前，允许�U�程�{�待直到他们完成操作
await()�Ҏ��一直等到state=0�Q�初始时CountDownLatch初始化state��Z��入的数��|��一个线�E?br />执行操作完成的话执行countDown()�Ҏ��state�?�Q�直��Cؓ0�Q�await()�Ҏ��不再��d��?br />
CyclicBarrier
当一�l�线�E�调用CyclicBarrier.await()�Ҏ��Q�就会阻塞在那里�Q�当最后一个线�E�进入调用此�Ҏ��Ӟ��执�?br />一个公��q��Runnable.原理是：初始化时有count属性，当前面count-1个线�E�到来都condition.await()�Q�第count�?br />�U�程来就执行公共Runnable�Q�然后执行condition.signAll()�Ҏ��来��得其他线�E�从��d��中解脱出�?

nod0620 2011-09-18 00:12 发表评论

java thread 之AQS

nod0620 — Thu, 15 Sep 2011 14:57:00 GMT

摘要: JDK1.5引入了Doug Lea大神的concurrent框架�Q�其中AbstractQueuedSynchronizer是concurrent框架的基本，从大��的paper中可以看�?.传统的synchronized不能�q�行中段�Q�这个不合�?.如果��concurrent重心攑֜��数竞争下优化锁�Q�而在其他情况下放�ȝ��慢执行的�{�略是不正确�?.需要可预测的维护效率，即��在同步竞争激烈的情况下，理想�?.. 阅读全文

nod0620 2011-09-15 22:57 发表评论

java thread

nod0620 — Wed, 14 Sep 2011 08:53:00 GMT

�U�程状�?/strong>
   jdk中线�E�状态分�?new,runnable,blocked,waiting,timed_waiting,dead.其中new为刚创徏�q�没有开始执行的状态，
而runnable状态分为可以执行和正在执行�Q�可以执行是因�ؓ可能要等cpu旉��片等。blocked状态是指线�E�在��d��{�待监视器的锁。waiting是指执行了Object.wait()�Q�Thread.join()�{�方法进入waiting状态；timed_waiting是指带时间数的waiting状态，在时间到达之前都是在waiting状态，dead状态是指结束�Q务的�U�程状态，再也不能回到runnable状态了�?br />
在线�E�中有waiting set和ready set概念�?br />当一个对象执行Object.wait()/Object.join()�Q�该�U�程�q�入waiting set�Q�同旉��要释攄��视器的锁。监视器也是一个普通对象，在加上一些关键语法后�Q�就能成为监视器�?br />当一个对象执行Object.notify()�Ӟ��是在waiting set选择一个thread�q�入ready set�Q�当�q�个thread能获得这个监视器的锁时候，��可以进入runnable状态，否则��待在ready set�Q�notifyAll()是通知waiting set里面的所有线�E�，然后选择其中的一个，不确定是哪一个，�U�程的优先��也只是一个提�C�和指导�?br />Object.wait(time)/Object.join(time)�Ҏ��q�些都是在时间限制到达之前thread在waiting set�Q�时间到期之后自动进入ready set�?br />Thread.sleep()/Thread.yield()执行时thread都不会放弃监视器的锁�Q�只是进入ready set�Q�Thread.sleep()只是在指定的旉��内休眠，得不��C�Q何的资源.Thread.yield()只是提示thread工作差不多完成了�Q�可以让步给其他Thread�Q�这个让步不保证完成�Q�这个也只对同等�U�的�U�程有效�?br />
监视�?/strong>
   java使用监视器来表示同步锁，在Java里面�Q��Q何一个Object Reference都可以作为同步锁�Q�只要��用synchronized�Q?br />
public static final Object signal = new Object();
f1(){
   synchronized(signal){

   }
}
在jvm内部synchronized会被表示成monitorenter和monitorexit;在一个时间段�Q�只有一个线�E�能持有monitor�Q�也��是在monitorenter里面�Q�也��p��C��同步的目�?当想获得一个类变量锁的时候，可以使用�q�个�cȝ��class�c�R�?br />
内存模型
在jvm规范中规定java内存模型是java thread work memory和java main memory两部�?br />每个thread一个thread memory�Q�初始�ؓ�I�，必要时和main memory通信

规范规定了工作内存和��d��存之间通信�?个行为：use, assign, load, store,read,write, lock, and unlock
use:使用一个线�E�工作内存中的变量，看成�U�程的行�?br />assign:讄��一个线�E�工作内存中的变量，讄��的值来自线�E�执行引擎，看成�U�程的行�?br />read�Q�把��d��存的��D��到线�E�工作内存当中，看成��d��存的行�ؓ
load�Q�在read之后执行�Q�真正的把��D��到到工作内存当中�Q�看成线�E�的行�ؓ
store�Q�保存工作内存的��|��{�下在执行write后传输给��d��存，看成�U�程的行�?br />
write�Q�在store后执行，看成��d��存的行�ؓ
lock和unlock是获取监视器锁和释放锁的行�ؓ�Q�是�W�三方synchronized行�ؓ

�q�样的内存模型就会有问题�Q?br />�U�程工作内存是独立的�Q�在工作内存A的变量被工作内存B看到需要经�q�A-->��d��?->B的程度，那么什么时候进行工作内存到��d��存的通信呢？
�q�里需要涉及到�~�存一致性模型，卛_��作内�?�~�存)什么时候刷新和��d��d��存必��遵循一定的规则才可以�?
java使用释放一致性模�?在释��N��的时候写入主内存
也就是当synchronized表示的方法或者运行块执行�l�束时监视器锁释攑֐��Q�里面涉及的所有变�?局部变量除�?的值都写入了主内存�Q�当变量被其他线�E�看到的话，其值是最新的�?br />那么�Ҏ��或运行块未进行同步，可能有两斚w��的问�?
1.�Ҏ��的执行顺序是未定�?br />2.即��Ҏ��的执行顺序是相同的，�׃��工作内存的值未写到��d��存中也有可能有问�?br />
thread在jvm当中执行的顺序和代码中看到的��序可能是不一��L��Q��ؓ了性能优化�{�代码可能进行重排序�Q�所有jmm定义�?br />�U�程的执行顺序模型：happens-before模型�Q�规则如�?
1.一个线�E�当中，先出现的指��ohappens-before后出现的指��o
2.构造器的里面指令happens-before创徏对象的指�?br />3.对于一个监视器�Q�unlock happens-before 惛_��得锁的指�?br />4.对于volatile的变量，write happens-before read
5.A call to start() on a thread happens-before any actions in the started thread.
6.All actions in a thread happen-before any other thread successfully returns from a
join() on that thread.

happens-before模型保证了JMM内存模型的访问方式�?br />对于synchronized我们可以认�ؓ他符合了上面的第3�?br />对于volatile变量�Q�保证了在线�E�每�ơ修改后马上反映��C��内存当中�Q�也��是可见性�?/div>

1.All instance fields, static fields and array elements are stored in heap memory.存放在java堆内
2.

nod0620 2011-09-14 16:53 发表评论

linux�U�录

nod0620 — Wed, 07 Sep 2011 09:46:00 GMT
1./proc下面提供很多关于�pȝ��的信息，很多内核信息可以在此文�g夹下面看�?br />2.echo,昄��文本�?br />3.whereis command 昄��command在哪里，whatis command 昄��command是什�?br />4.free昄��内存信息
5.history 昄��历史指��o
6.locale 昄��当前�pȝ��的语�a�讄��
7.ps 昄��q�程消息�?ps aux | grep xxx
8.sysctl可以用来讄��核心的参敎ͼ�默认的文件是/etc/sysctl.conf
9.top昄��q�程消息�Q�主要是查看�pȝ��的一些关键性能指标
10.vmstat昄��虚拟内存�l�计信息
11.pgrep 查找�W�合条�g的进�E?br />12.exit 退出ssh或者终�?br />13.pidof 昄��当前正在�q�行的程序的�q�程id
14.kill PID�Q�pkill process_name�Q�killall comm 杀��d��部同名进�E?br />15.symlinks ��理和维护符号链�?br />16.chkconfig 讄��和检查系�l�的服务讄��
17.查看所有的shell命��o�Q�可以进行修�?br />18.export 讄��和显�C�环境变�?br />19.find 查找文�g命��o
20.wc�l�计文�g的行敎ͼ�字数�Q�字节数�Q�文件名
21.grep 正则表达式搜�?grep xxx 文�gxxx�Q?i 忽略大小写；-数字昄��匚w��行的上下数字行；-b 在每行前昄��字符偏移�?-n 昄��行数
22.tar -cvf 压羃;tar -xvf 解压

linux监控�Q?div>http://agapple.iteye.com/blog/1156719
ps详解�Q?
http://blog.chinaunix.net/space.php?uid=20053649&do=blog&id=161862
top详解�Q?br />
http://bbs.linuxtone.org/thread-1684-1-1.html
mpstat
http://hi.baidu.com/kqzjhack/blog/item/20e1bb6744f9dd36aa184c44.html
http://www.ixpub.net/thread-645961-1-1.html

nod0620 2011-09-07 17:46 发表评论

hashcode

nod0620 — Wed, 07 Sep 2011 07:11:00 GMT
hashcode几点规定�Q?br />
�?Java 应用�E�序执行期间�Q�在对同一对象多次调用 hashCode �Ҏ��Ӟ��必须一致地�q�回相同的整敎ͼ�前提是将对象�q�行 equals 比较时所用的信息没有被修攏V�?
如果�Ҏ�� equals(Object) �Ҏ��Q�两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode �Ҏ��都必��ȝ��成相同的整数�l�果�?
如果�Ҏ�� equals(Object) �Ҏ��Q�两个对象不相等�Q�那么对�q�两个对象中的�Q一对象上调�?hashCode �Ҏ��不要求一定生成不同的整数�l�果�?/li>
HashMap使用分离链接法，��是在hashcode冲突的时候在hashcode对应的槽位��用链表，查找的时候先hashcode扑ֈ�槽位�Q�然后equals()�Ҏ��扑ֈ�链表中对应的对象�?br />jdk的容量是2^n�ơ，扑ֈ�槽位使用位与的方式代替模的方式提高性能
装蝲因子是装载的对象和hash表��L��量的比��|��Cؓλ�Q�这个代表��^均链表的长度�Q�在一�ơ不成功要查扄��q�_��节点�?br />
λ,一�ơ成功的查找则�ؓ1+λ/2

分离链接法之外还有线性探��法和��^�Ҏ��法�Q�双散列�{�探��法
探测法不是在冲突的时候利用链表进行存储，而是在冲�H�的位置往后查找一个空位置�q�行存储

�U�性探��法会遇��C��ơ聚焦的问题�Q�就是一个冲�H�的位置后面�q�箋的位�|�都不�ؓ�I?br />
那么可以�q�行�q�x��探测法消除一�ơ聚焦的问题�Q�虽然我们引�q�了二次聚焦的较��媄响的问题�Q�流行的函数为f(i)=i^2�?br />
�q�个时候hash表的定w��必须为素敎ͼ��q�样在表一半�ؓ�I�时�Q�才能��L��插入一个元�?br />如果定w��为非素数的时候，备选位�|�要��很�?br />
�|�上讨论hashmap的个��Cؓ素数或�?^n�ơ问题，是没有分清分��链接法和探��法�Q�只有在探测法的时候，素数才是最有效�?/div>

nod0620 2011-09-07 15:11 发表评论

��目��结

nod0620 — Wed, 31 Aug 2011 07:50:00 GMT
��d��q�底和今�q�上半年�Q�做了一个类似微博的sns的项�?#8212;求购��目�Q�有求购消息�Q�评论消息和好友关系�Q�也和项目组的同学一赯��Z��目的设计，不敢说架构，因�ؓ好多底层的存储，分库分表的功能我厂的其它团队已经完成�?br />

表设�?/h3>1.求购消息主要是图片和文字的说明，�q�个其实可以看成是个微博每个用户发表feed的表�Q�但有些不同�Q�这个下文再��_��q�里我们叫photo表，下面所说的囄��是求购消息�?br />考虑到求购消息比较多�Q�所以需要进行分表，假设�?个表�?strong>�׃��业务的需求是�Q�可以查看单张图片，可以看一个用��L��囄��列表�Q�问题来了，我们按什么进行分表？
看下表结�?

id是图片的id�Q�要查询单张囄��的话�Q�需要能快速的定位到哪一张表�Q�而查询一个用��L��囄��列表的话�Q�需要快速找到这个用��h��有的囄��Q�那么这个用��L��囄��应该是放�?br />一个表里面的，即通过user_id能�\由到一张表�Q�从而从�q�张表里面取得这个用��h��有的囄��?strong>通过上面分析�Q�如果选择user_id对表数量取模的��gؓ选择存储的第几个表，
那么一个user_id所有的囄��都在一张表里面了，�q�里对id��有要求�Q�id对表数量取模的��D��和user_id对表数量取模的��g��?�?br />�q�样做的�l�果是，id的��g��是连�l�的�Q�有些许的浪费，如果user_id分布不均的话�Q�对于每个表的数据量也会分布不均

2.评论�?br />对图片进行评论，对于单个囄��来说有评论列表，对于单个用户来说�Q�他能看到所有对他图片进行评论的评论列表�Q�所以采用了两套表的�Ҏ��Q�对于用photo_id分表�?br />的comment表，以及针对user_id分表的comment_u�?br />

3.好友关系�?br />�q�个�c�M��于微薄里面的��x��或者粉丝表,和评��一��P��q�里需要两套表�Q�一个是��x��表，一个是�_�丝�?br />

Feed��?/h3>当一个�h��x��另外一个�h的时候，那么被关注的人发表的囄��是能被另外一个�h看到的，�q�和微博的feed��是一��L��?br />�q�里有两�U�方式实玎ͼ�push模式(推模�?�Q�pull模式(拉模�?。push模式�Q�当一个用户发表图片的时候，��索这个用��L��
�_�丝表，为每个粉丝插入一条feed。pull模式�Q�当一个用户发表图片的时候，只是存一份数据，当一个用��h��看他的关注的用户的feed的时候，需要先��索关注表�Q�然后检索每一个关注用��h��没有新发的feed�?br />
push和pull模式各有利弊�Q�当使用push模式的时候，如果一个用�?名�h)的粉丝过多的话，那么每个�_�丝插入一条feed对存储的压力��太大了(100000�_�丝话，插入100000)�Q�存储空间浪费也非常的严重�?br />pull模式的话�Q�如果一个用户关注过多的时候，查询该用��L��x��列表也是有很大的代�h�?br />
��目用的是pull模式�Q�注意到求购��目的特�D�性，一般只是看最新的求购的消息，假设某个用户当前�?000条新feed�Q�这个用户也不能完全的看完，所以认为只要取得最新的消息里面的若�q�条�Q�其余的消息的话可以在历史feed列表里面看到或者下一�ơ看刎ͼ��q�里��有个timeline的概��c��当�ơ取得最新消息后�Q�需要把�q�个旉��点保存，下次查询的时候，从这个时间点�q�行查询�?br />
��目具体的做法：
1.查询用户的关注列�?br />2.从cache中取出timeline
3.timeline为空的话�Q�直接取出旧的feed 30条，更新timeline�Q�其中最新的一条的创徏旉��为timeline
4.timeline不�ؓ�I�的话，取得timeline之后的feed�Q�最大��gؓ30条，查过30条，取得的是最旧的30条，更新timeline�Q�其中最新的一条的创徏旉��为timeline�?br />

�W?步其实和微博的做法是不同的，假设�?000条feed�Q�微博是一�ơ性刷出来�Q�而这个是一�ơ刷�?0条，�q�里有个博弈在里面：
一�ơ刷�?0条，��h��的次数多了，查询多了�Q�但是一��?000条的单次查询压力大了�Q�还有多��h看了30条之后��l�刷新看的？所以我们采取降低单�ơ刷新的代�h�Q�这样对服务器峰值的压力也就下来�?br />

其它

�q�有很多优化的点没有说出来，比如路由表取模的时候，是用位与操作�?18%16==18&15)
�q�有各个能用到cache的地方尽量��用cache�Q�对于读写的话，可以增加��d��队列.
对于扩展�Q�性能�Q�后�l�考虑的：
当单个用户关注数��过一定数目，�q�个用户��需要特别的对待�Q�比如用户关注单独的变成一张表�Q�减��关注表的压�?br />对用��h��跃度�q�行分析�Q�活跃用��L��feed使用pull和push模式相结合的模式
对于�_�丝数很多的用户�Q�可以单独成表，发的feed可以先push�l�一部分用户�Q�让一部分用户先看到feed.

nod0620 2011-08-31 15:50 发表评论

nod0620 — Mon, 29 Aug 2011 09:38:00 GMT

remove

remove分成三种情况�Q�没有孩子节点的节点(即页�?,单个孩子节点的节点，两个孩子节点的节�?/p>

1)��子节点可以直接删除

2)单个孩子节点的节点删除了�Q�让其下的孩子节点直接和其父亲节点相�q?��是孩子节点和祖父节点相�q?

3)两个孩子节点的节点，��Z��保持排序状态，需要拿到这个节点的左子树的最大节�Ҏ��者右子树的最��节点，得到�q�个节点的数据代替要删除的节点，

然后删除�q�个左子树的最大节�Ҏ��者右子树的最��节点，因�ؓ左子树的最大节�Ҏ��有右节点(有右节点的话�Q�他��׃��是最大的�?,同理�Q�右子树的最��节�?/p>

没有左节点，所以要删除的这个节点只有一个或者没有孩子节点，只需要进�?)或�?)��完成了�?/p>

AVL�?/h3>

在插入节�Ҏ��通过旋�{(rotation)解决问题:

  /**
     * 插入一个元素到树里面，可能破坏了高度差�Q�需要找��C��个节点a�Q�该节点左子树和叛_��树被破坏了，则需要对�q�个节点(�q��因子)
     *
     * 树进行��^衡，有四�U�情�?
     *
     * 1.a节点的左儿子的左子树插入
     *
     * 2.a节点的左儿子的右子树插入
     *
     * 3.a节点的右儿子的左子树插入
     *
     * 4.a节点的右儿子的右子树插入
     *
     *
     * 1.4两种情况需要进行一�ơ旋�?br />     *
     * 2.3两种情况需要进行两�ơ旋�?br />     *
     * 旋�{的目的是��Z��使插入节点的树的高度降低1�Q�所以只要求旋�{�q��因子为根的树��可以了
    */

在删除节点的时候：

    /**
     * 删除一个节点，扑ֈ��q��因子�Q�他的左子树高度和右子树高度如果相差2的话�Q�就需要旋转，而且旋�{后，�q��因子的节点�ؓ根的树的高度肯定�?br />     *
     * 下降1�Q�这样��^衡因子所在的树的高度下降1�Q�也有可能需要进行旋转调��_��q�样调整一直到根节�?br />     *
     */

代码如下�Q?br />

package struct;

/**
* @author chenxiaohui
* @version 创徏旉��Q?011-8-26
*
*
*/
public class AvlTree {
    /**
     *
     * avl�?树中每个节点的左子树和右子树的高度最多差1的二叉查找树
     *
     *
     *
     */

    public int height(AvlNode node) {
        return node != null ? node.height : -1;
    }

    /**
     *
     *
     * 插入一个元素到树里面，可能破坏了高度差�Q�需要找��C��个节点a�Q�该节点左子树和叛_��树被破坏了，则需要对�q�个节点(�q��因子)
     *
     * 树进行��^衡，有四�U�情�?
     *
     * 1.a节点的左儿子的左子树插入
     *
     * 2.a节点的左儿子的右子树插入
     *
     * 3.a节点的右儿子的左子树插入
     *
     * 4.a节点的右儿子的右子树插入
     *
     *
     * 1.4两种情况需要进行一�ơ旋�?br />     *
     * 2.3两种情况需要进行两�ơ旋�?br />     *
     * @param t
     * @param tree
     * @return
     */

    public AvlNode insert(int t, AvlNode tree) {

        if (tree == null)
            return new AvlNode(t);

        int cmp = compare(t, tree.element);

        if (cmp < 0) {
            // 左子�?/span>
            tree.leftChild = insert(t, tree.leftChild);

            // 因�ؓ左子树插入了节点�Q�那么左子树比右子树�?�Ҏ��avl树的性质�Q�插入了节点
            // 要么高度差�ؓ1�Q�要么高度差�?�Q�所以当相差�?�Ӟ��需要进行树的调�?/span>
            if ((height(tree.leftChild) - height(tree.reightChild)) == 2) {

                // 当t比树左子树的元素�q�小的话�Q�就是在树的左子树的左边插入节点�Q�成为左子树的左子树�Q�需要一�ơ旋�?/span>
                if (compare(t, tree.leftChild.element) < 0) {

                    tree = rotateLeftChild(tree);
                } else {
                    // 当t比树左子树的元素�q�大的话�Q�就是在树的左子树的双��插入节点�Q�成为左子树的右子树�Q�需要两�ơ旋�?/span>
                    tree = doubleRotateLeftChild(tree);
                }
            }

        } else if (cmp > 0) {
            // 叛_��?/span>
            tree.reightChild = insert(t, tree.reightChild);

            if ((height(tree.reightChild) - height(tree.leftChild)) == 2) {
                // 当t比树叛_��树的元素�q�大的话�Q�就是在树的叛_��树的双��插入节点�Q�成为右子树的右子树�Q�需要一�ơ旋�?/span>
                if (compare(t, tree.reightChild.element) > 0) {
                    tree = rotateRightChild(tree);
                } else {
                    // 当t比树叛_��树的元素�q�小的话�Q�就是在树的叛_��树的左边插入节点�Q�成为右子树的左子树�Q�需要两�ơ旋�?/span>
                    tree = doubleRotateRightChild(tree);
                }
            }

        } else {
            // 树里面有�q�个�?/span>

        }
        tree.height = Math
                .max(height(tree.leftChild), height(tree.reightChild)) + 1;
        return tree;

    }

    /**
     * �W?�U�情况需要进行顺旉��旋�{(��x��?
     *
     * @param k2
     * @return
     */
    private AvlNode rotateLeftChild(AvlNode k2) {

        AvlNode k1 = k2.leftChild;

        k2.leftChild = k1.reightChild;
        k1.reightChild = k2;

        k2.height = Math.max(height(k2.leftChild), height(k2.reightChild)) + 1;
        k1.height = Math.max(height(k1.leftChild), height(k2)) + 1;
        return k1;

    }

    /**
     *
     * �W?�U�情况需要进行逆时针旋�?左旋�?
     *
     * @param k2
     * @return
     */
    private AvlNode rotateRightChild(AvlNode k2) {

        AvlNode k1 = k2.reightChild;

        k2.reightChild = k1.leftChild;
        k1.leftChild = k2;

        k2.height = Math.max(height(k2.leftChild), height(k2.reightChild)) + 1;
        k1.height = Math.max(height(k1.reightChild), height(k2)) + 1;
        return k1;

    }

    /**
     * �W?�U�情况需要进�?�?左旋�?
     *
     * @param k3
     * @return
     */
    private AvlNode doubleRotateLeftChild(AvlNode k3) {
        AvlNode k1 = k3.leftChild;
        k3.leftChild = rotateRightChild(k1);
        return rotateLeftChild(k3);
    }

    /**
     * �W?�U�情况需要进�?�?��x��?
     *
     * @param k3
     * @return
     */

    private AvlNode doubleRotateRightChild(AvlNode k3) {
        AvlNode k1 = k3.reightChild;
        k3.reightChild = rotateLeftChild(k1);
        return rotateRightChild(k3);
    }

    public int compare(int a, int b) {
        return a - b;
    }

    static class AvlNode {

        private int element;
        private int height;
        private AvlNode leftChild;
        private AvlNode reightChild;

        AvlNode(int element) {
            this(element, null, null);
        }

        AvlNode(int element, AvlNode left, AvlNode right) {
            this.element = element;
            this.leftChild = left;
            this.reightChild = right;
        }

    }

    public void sysout(AvlNode node) {
        if (node != null) {

            AvlNode a = node.leftChild;
            sysout(a);
            for (int i = 0; i < node.height; i++) {
                System.out.print("     ");
            }
            System.out.print(node.element);
            System.out.print("\n");
            AvlNode b = node.reightChild;
            sysout(b);
        }
    }

    /**
     * 删除一个节点，扑ֈ��q��因子�Q�他的左子树高度和右子树高度如果相差2的话�Q�就需要旋转，而且旋�{后，�q��因子的节点�ؓ根的树的高度肯定�?br />     *
     * 下降1�Q�这样��^衡因子所在的树的高度下降1�Q�也有可能需要进行旋转调��_��q�样调整一直到根节�?br />     *
     * @param t
     * @param tree
     * @return
     */
    public AvlNode delete(int t, AvlNode tree) {

        if (tree == null)
            return null;

        int cmp = compare(t, tree.element);

        if (cmp < 0) {
            tree.leftChild = delete(t, tree.leftChild);

            if ((height(tree.reightChild) - height(tree.leftChild)) == 2) {
                if (tree.leftChild == null) {
                    tree = rotateRightChild(tree);
                } else {
                    tree = doubleRotateRightChild(tree);

                }

            }
        } else if (cmp > 0) {
            tree.reightChild = delete(t, tree.reightChild);

            if ((height(tree.leftChild) - height(tree.reightChild)) == 2) {
                if (tree.reightChild == null) {
                    tree = rotateLeftChild(tree);
                } else {
                    tree = doubleRotateLeftChild(tree);
                }
            }
        } else if (cmp == 0) {
            tree = null;
        }

        if (tree != null) {
            tree.height = Math.max(height(tree.leftChild),
                    height(tree.reightChild)) + 1;
        }
        return tree;

    }

    public static void main(String[] args) {
        AvlTree avlTree = new AvlTree();
        AvlNode node = new AvlNode(20);
        /*
         * Random random = new Random(); for (int i = 0; i < 10; i++) { int y =
         * random.nextInt(100) + 1; node = avlTree.insert(y, node); }
         */

        node = avlTree.insert(8, node);
        node = avlTree.insert(3, node);
        node = avlTree.insert(10, node);
        node = avlTree.insert(2, node);
        node = avlTree.insert(5, node);
        node = avlTree.insert(30, node);

        node = avlTree.insert(50, node);
        node = avlTree.insert(6, node);
        node = avlTree.insert(20, node);
        node = avlTree.insert(35, node);
        node = avlTree.insert(43, node);
        node = avlTree.insert(60, node);
        node = avlTree.insert(18, node);
        node = avlTree.insert(26, node);
        node = avlTree.insert(33, node);
        node = avlTree.insert(40, node);
        node = avlTree.insert(45, node);
        node = avlTree.insert(62, node);

        // avlTree.sysout(node);

        node = avlTree.delete(2, node);
        avlTree.sysout(node);

    }
}

nod0620 2011-08-29 17:38 发表评论

classloader记录

nod0620 — Wed, 24 Aug 2011 02:40:00 GMT

classloader是一个双亲委�z�模型的�l�构.

一般是如上囄��?br />

Bootstrap ClassLoader/启动�c�d��载器
他的parent为null, 主要负责'sun.boot.class.path'�pȝ��属性指定的 �?-Xbootclasspath 选项指定的jar包装入工�?

Bootstrap ClassLoader是jvm控制的，不是java语言层面�~�写的，默认加蝲jdk_home/jre/lib/下面的jar包和其他相关的东西，如jdk的核心包rt.jar��是在这里被加蝲�?br />

Extension ClassLoader/扩展�c�d��载器
主要负责jdk_home/jre/lib/ext目录�?'java.ext.dirs'�pȝ��属性指�?的jar包或 -Djava.ext.dirs 指定目录下的jar包装入工�?他的parent�?Bootstrap ClassLoader

System ClassLoader/�pȝ��c�d��载器
主要负责java -classpath/-Djava.class.path所指的目录下的�c�M��jar包装入工�?一般我们会配置环境变量classpath�Q�这个就是蝲入classpath指定的�\径下jar和class,
�q�_��我们指定一�?."��P��是指定从当前目录下开始搜索class�c?parent�?Extension ClassLoader.

User Custom ClassLoader/用户自定义类加蝲�?java.lang.ClassLoader的子�c?
在程序运行期�? 通过java.lang.ClassLoader的子�c�d��载class文�g.

classloader要加载class先从底向上传递给父亲加蝲�c�，最��层的classloader如果能够加蝲��加载进来，不行的话�Q�就自上而下传递，只到一个classloader能进行类的加载，
如果没有一个classloader能加载的话，��׃��抛出ClassNotFoundException或者NoClassDefFoundError异常�Q�这个就是双亲委�z�模�?br />
classloader�q�种模式保证了不同的classloader之间�c�M��会相互的影响�Q�那么也保证了好的类不会被恶意的�c�L��破坏�Q�这个也是jvm沙箱模式安全的一个保�?br />
在不同classloader的同名的�c�d��例不能互相沟通，�c�d��转换�Q�instanceof�Q�如果这样做�Q�则会抛出ClassCastException.所以抛出ClassCastException的原因不止和�l�承�Q�实现有关系�Q?br />�q�和classloader有关�p?

当运行时发现一个新class要load�Ӟ��除代码已指定由哪classloader的实例load外，先由调用者的classloader所在的classloader tree去load�Q�如果super�c?interface�c�d��于这个树是新的也一起会被load。这是caller classloader的概�?

双亲委派可以被打��_��全权负责也可被打��_��所以运行时军_��c�L��自哪里，�q�是由classloader树和load class的代码是怎样而决定�?br />

Thread Context ClassLoader�Q�线�E�上下文classloader�Q�是hold住了一ClassLoader的实例，�q�个holder在线�E�运行流�E�里可以到达隐式传递classloader。这个classloader是一个不会主动load的实例，��是说在�q�个�U�程�q�行下遇到新�c�这个classloader不会��d��去load�Q�只有自��q��昑ּ�代码或你看不见的jar里用昑ּ�代码用这�?div>classloader loadClass()或Class.forName()�Q�才会生效。因此，caller classloader�?thread context classloader�Q�在执行��C��的代码时�Q�已定。�ƈ且执行流�E�的不同�Q�到你代码时的入口也不同�Q�被攄��入thread的thread context classloader和Caller ClassLoader不一定一��P��因此是不�E�_��?br />
需要稳定的话，��p��保证在设计时��p��虑到各�U�入口和用法的情况，然后得到��定的classloader存在 thread context classloader或者第三方的class loader中，tomcat的类加蝲体系��是�q�样做的.

nod0620 2011-08-24 10:40 发表评论

中文亚洲欧美,国产精品成人品,国产欧美午夜

java io以及unix io模型

java thread 之Lock

java thread 之AQS

java thread

linux�U�录

hashcode

��目���结

其它

remove

AVL�?/h3>

代码如下�Q?br />

classloader记录

��目��结