月度归档:八月 2013

[转] 深入多线程编程

线程库
多线程编程定式
无锁编程(Lock Free)
阻塞型同步(Blocking Synchronization)
非阻塞型同步(Non-blocking Synchronization)
优先级反转(Priority Inversion)
优先级继承(Priority Inheritance)
优先级顶置(Priority Overhead)
内存屏障

转载自:http://blog.chinaunix.net/uid-20682147-id-3160080.html

PDF文档查阅链接:

深入多线程编程

| 1 分2 分3 分4 分5 分 (5.00- 1票) Loading ... Loading ... | 归档目录:多线程编程 | 标签: , |

一道基础的词法解析题

原日志信息
标题:《计算单词数目的小程序-2009-05-24考试》
发布时间:5/24/2009
作者:童燕群

2009年,公司开始推行技能鉴定考试,这是我第一次参加的技能鉴定考试,那次考试最终以成绩不作为技术等级评定的依据收场。据说有的部门直接以金钱来奖励考分高者,在天涯论坛上面闹得沸沸扬扬。当年做这道题目时用完了所有考试时间,但是仍然没有调通,晚上回家后又接着奋战几个小时,重新写了这份代码。在现在看来,当时那个迫切想写代码的心情真的是难以理解。软件维护工作做多了,好像是会有这样的感觉。

直接贴代码,题目在代码头部的注释中。

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.86- 7票) Loading ... Loading ... | 归档目录:C/C++, 算法数据结构, 职业发展 | 标签: , |

[分享]百度分布式数据库

很老的视频了,感觉讲得不错,百度09年都已经SSD了,我们却还在挣扎着怎样精简流程来节省元数据的访问。右边是视频中用于讲解的PPT。

  

| 1 分2 分3 分4 分5 分 (5.00- 1票) Loading ... Loading ... | 归档目录:移动互联, 软件技术 | 标签: , |

[转] 宫崎骏用动漫教给我们的人生哲理,每一句都能说到心里!

引导语:那些触动心弦的台词,那些感动灵魂的画面,那些照亮前行方向哲理,那些陪伴我们成长的童话……让我们一起重温那些青葱岁月里,宫崎骏给我们带来的温暖细腻的小美好~

千与千寻

曾经发生的事不可能忘记,只是暂时想不起来而已。——《千与千寻》

我到现在都想不起自己的名字。可是真是不可思议,我居然还记得你的名字。——《千与千寻》

人生就是一列开往坟墓的列车,路途上会有很多站,很难有人可以至始至终陪着走完。——《千与千寻》

当陪你的人要下车时,即使不舍,也该心存感激,然后挥手道别。——《千与千寻》

一直向前走。千万别向后看。否则就永远回不去那个世界了。——《千与千寻》

千万不可以丢失自我。——《千与千寻》

只有一个人在旅行时,才听得到自己的声音,它会告诉你,这世界比想象中的宽阔,这个世界上,你可以碰到机遇,而绝不可能碰到“神”,自己的路,还是得自己走!——《千与千寻》

这世上有一条路无论如何也不能走,那就是歧途,只要走错一步结果都会是粉身碎骨。——《千与千寻》

哈尔的移动城堡

我一直在躲避,但我终于找到要保护的人了,那就是你。——《哈尔的移动城堡》

人老的好处就是,看到什么怪物,都没什么好害怕的了。——《哈尔的移动城堡》

因为爱你,只要你一个肯定,我就足够勇敢。——《哈尔的移动城堡》

爱上某人,不是因为他给了你需要的东西,而是因为他给了你从未有过的感觉。——《哈尔的移动城堡》

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 2票) Loading ... Loading ... | 归档目录:文字网摘 | 标签: , , , , , , , , , , , , , , , , , , |

[转] 舌尖上的科学家

slzk20133336-1-l17世纪50年代的某一天清晨,如果你来到位于比利时西部的一座公园,有可能会看到一个奇怪的遛鸟人:只见他伸出舌头,把舌尖嘬得像一条小蛇,吸引一只麻雀来吃,只听吸溜一声,麻雀将“小蛇”吞了下去……这个人不是疯子,他是著名科学家范赫尔蒙特,正在进行消化的研究。他的实验是这样的:伸出舌头,让一只驯化的麻雀来吃,麻雀把他的舌头吞下去,这样就使他的舌尖感觉到了麻雀喉咙里那强烈的酸味,从而让他弄明白了一个问题:麻雀为什么消化得那么快?

因被天上掉下的苹果砸昏了头,在报复性地猛吃烂苹果时发现了万有引力的牛顿,还有一则流传至今的轶事:在煮牛奶时,由于太专心,放糖时他竟把自己的手表当作糖放到了牛奶里。在吃饭问题上和牛顿一样狼狈的还有安培。在和妻子分居两地时,不得不亲自下厨的安培,就发出过“煮饭比物理难”的感叹。但让牛顿羡慕得流口水的是,为了给安培补充营养,每次回家,妻子都要给他准备一块牛肉,让安培感觉自己“像是上帝的子民,在逾越节里吃着羊羔肉,洋溢着感谢”。这舌尖上的爱,或许正是成就一代电磁学大师的第一块基石。

就在一些科学家为吃饭苦恼时,另一些科学家却把食物转化成了科学成果。1955年12月的一天,美国科学家罗伯特·小温特沃夫走到食品店,买了一瓶花生酱,回到实验室,他舀出一匙花生酱,放到高温高压环境中,将其“烹饪”成了钻石。

1950年代,美国科学家詹姆斯·沃森在剑桥大学的卡文迪许实验室工作。英国的工作条件非常合他的胃口,可英国那“无味的肉,没有颜色的菜,和那煮得稀烂的土豆”却总是叫他的肠胃剧烈地疼痛。就是在这样的痛苦中,沃森成功地建立了DNA双螺旋结构模型,并因此获得了诺贝尔奖。印度数学奇才拉马努扬在剑桥大学时也经历了同样的遭遇,不过却没有沃森幸运,因严重的营养不良,年仅33岁便与世长辞。

与之相比,无论走到哪里都可以看到中餐馆的华裔科学家就非常幸运了。1956年5月,杨振宁去哥伦比亚大学拜访李政道,没有找到停车的地方,他们就开着车绕着哥大转,他们一边转一边讨论起了宇称不守恒的可能性,最后,他们烦了,不再讨论下去,在一家中餐馆前把车停了下来。在中餐馆里,两人基本上得出了一个让他们名扬世界的结论:宇称不守恒。

1960年代初,美国物理学家默里·盖尔曼受一种烹饪技术的启发:“把一片野鸡肉放在两片小牛肉中间烹调,然后再把两片小牛肉扔掉”,发现了强相互作用对称,而美国拓扑学家斯梅尔则受到厨师揉面团的启发,提出了一种几何模型——“斯梅尔马蹄”。

受“揉面团”启发的还有中国天文学家张衡。一天,张衡的妻子正在厨房烙饼,突然见丈夫走进来,抓起一团面就揉了起来,只见他把面揉成圆圆的一团,又把它在芝麻里一滚。妻子还以为张衡闹着玩呢,却听他眉飞色舞地说:“老婆,这个面团呢,好比是天球,上面的芝麻,好比是星星……”在希腊语里,“美食家”一词藏在“天文学家”一词里,不错,张衡就是一位潜伏的美食家,他做出了一张让我们无比骄傲的大饼——天体模型“浑天仪”。

[转载信息]
作者:李浅予
原文地址:http://blog.sina.com.cn/s/blog_4a923e3201018u79.html
文章已发表于2013年第33期《三联生活周刊》。

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 归档目录:奇趣见闻, 文字网摘 | 标签: |

一个明显的jetty-8大文件传输性能大幅降低问题分析

这个问题很早就分析、修改和验证过了,一直没有来得及总结整理。今天突然想起来了,首先用我那蹩脚的英语给jetty的维护团队提了一个问题单,在等待他们回复的同时,我也把我发现问题的过程分享一下。

问题单链接:https://bugs.eclipse.org/bugs/show_bug.cgi?id=415282

经过打断点和调试,发现如下调用占用了性能下降(相对于jetty7版本)的绝大多数处理耗时:

public class HttpOutput extends ServletOutputStream 
{
/* ------------------------------------------------------------ */
private void write(Buffer buffer) throws IOException
{
if (_closed)
throw new IOException("Closed");
if (!_generator.isOpen())
throw new EofException();

// Block until we can add _content.
while (_generator.isBufferFull())
{
_generator.blockForOutput(getMaxIdleTime());
if (_closed)
throw new IOException("Closed");
if (!_generator.isOpen())
throw new EofException();
}

// Add the _content
_generator.addContent(buffer, Generator.MORE);

// Have to flush and complete headers?

if (_generator.isAllContentWritten())
{
flush();
close();
}
else if (_generator.isBufferFull())
_connection.commitResponse(Generator.MORE);

// Block until our buffer is free
while (buffer.length() > 0 && _generator.isOpen())
{
_generator.blockForOutput(getMaxIdleTime());
}
}
}
具体的耗时消耗在:_generator.blockForOutput(getMaxIdleTime());
从函数名字都可以看出来,当网络繁忙时,会走到这个流程,在blockForOutPut中,首先会注册一个socket可写的事件,当该socket上面可以写数据时,通知当前业务线程,随后业务线程投入休眠。等待事件分发线程检查可读事件,并唤醒自己。这样在这个交互中不可避免的会损失部分数据传输性能,每一包数据虽然只会损失一点点性能,但是传输一个很大的文件时,就会发现这个损失的巨大,在10GE的网卡上面,数据传输的性能降低到了原来的1/10,这个影响太明显了。
 
那么问题到底出在哪里呢?
看下面的代码:
public class HttpGenerator extends AbstractGenerator
{
public void addContent(Buffer content, boolean last) throws IOException
{
if (_noContent)
throw new IllegalStateException("NO CONTENT");

if (_last || _state==STATE_END)
{
LOG.warn("Ignoring extra content {}",content);
content.clear();
return;
}
_last = last;

// Handle any unfinished business?
if (_content!=null && _content.length()>0 || _bufferChunked)
{
if (_endp.isOutputShutdown())
throw new EofException();
flushBuffer();
if (_content != null && _content.length()>0)
{
if (_bufferChunked)
{
Buffer nc=_buffers.getBuffer(_content.length()+CHUNK_SPACE+content.length());
nc.put(_content);
nc.put(HttpTokens.CRLF);
BufferUtil.putHexInt(nc, content.length());
nc.put(HttpTokens.CRLF);
nc.put(content);
content=nc;
}
else
{
Buffer nc=_buffers.getBuffer(_content.length()+content.length());
nc.put(_content);
nc.put(content);
content=nc;
}
}
}

_content = content;
_contentWritten += content.length();

// Handle the _content
if (_head)
{
content.clear();
_content=null;
}
else if (_endp != null && (_buffer==null || _buffer.length()==0) && _content.length() > 0 && (_last || isCommitted() && _content.length()>1024))
{
_bypass = true;
}
else if (!_bufferChunked)
{
// Yes - so we better check we have a buffer
if (_buffer == null)
_buffer = _buffers.getBuffer();

// Copy _content to buffer;
int len=_buffer.put(_content);
_content.skip(len);
if (_content.length() == 0)
_content = null;
}
}
}
 
问题出在下面这段代码上面:
// Handle the _content
if (_head)
{
content.clear();
_content=null;
}
else if (_endp != null && (_buffer==null || _buffer.length()==0) && _content.length() > 0 && (_last || isCommitted() && _content.length()>1024))
{
_bypass = true;
}
else if (!_bufferChunked)
{
// Yes - so we better check we have a buffer
if (_buffer == null)
_buffer = _buffers.getBuffer();

// Copy _content to buffer;
int len=_buffer.put(_content);
_content.skip(len);
if (_content.length() == 0)
_content = null;
}
我的理解,_bypass变量标志不使用缓存,直接将数据刷到客户端,如果这是jetty8的新增特性,那么也不应该是到外层再调用blockforoutput方法,而是直接flushbuffer即可。很明显这是一个bug,bypass的判断条件有误,_buffer为空,这是不使用缓存的条件,但是_buffer.length() == 0并不是该特性的条件,每一次初始化的时候都会默认操作_buffer使得_buffer.length() == 0。这样就导致了每一包数据都走进了blockforoutput流程。应该是一个明显的笔误,问题的修改方法即是去掉该不当的判断条件,只保留_buffer==null的判断。
 
同前面的jetty若干性能问题的分析一样,这个问题的分析也耗费了大量的时间和精力,最终是借助于比对jetty7和jetty8的代码和不停的加日志打点调试得出的。每一个问题的解决都是一段辛酸的故事。
| 1 分2 分3 分4 分5 分 (5.00- 18票) Loading ... Loading ... | 归档目录:Jetty | 标签: , |

Java网络应用程序(Geronimo、Jetty)调试及问题定位方法简介

Java网络应用程序调试及问题定位方法简介

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 归档目录:Geronimo, Java, Jetty, 实用脚本 | 标签: , , |

[转] 高并发系统设计

一、服务器内部设计

服务器设计涉及Socket的阻塞/非阻塞,操作系统IO的同步和异步(之前被人问到过两次。第一次让我说说知道的网络模型,我说ISO模型和TCP/IP模型,结果被鄙视了。最后人说了解linux epoll吗?不了解呀!汉,回去查资料才知道是这回事。第二次让我说说知道线程模型,汉!这个名词感觉没有听说过,线程?模型?半同步/半异步,领导者/跟随者知道吗。再汉,我知道同步/异步,还有半同步/半异步?啥呀?领导者/跟随者,我现在没有领导。回去一顿恶补,原来是ACE框架里边经常有这样的提法,Reactor属于同步/半同步,PREACTOR属于领导者/跟随者模式。瀑布汗。小插曲一段,这些不懂没关系,下边我慢慢分解),事件分离器,线程池等。内部设计希望通过各个模块的给出一个简单设计,经过您的进一步的组合和打磨,就可以实现一个基本的高并发服务器。

1. Java高并发服务器

Java设计高并发服务器相对比较简单。直接是用ServerSocket或者Channel+selector实现。前者属于同步IO设计,后者采用了模拟的异步IO。为什么说模拟的异步IO呢?记得网上看到一篇文章分析了java的selector。在windows上通过建立一个127.0.0.1到127.0.0.1的连接实现IO的异步通知。在linux上通过建立一个管道实现IO的异步通知。考虑到高并并发系统的要求和java上边的异步IO的限制(通常操作系统同时打开的文件数是有限制的)和效率问题,java的高并发服务器设计不做展开深入的分析,可以参考C高并发服务器的分析做同样的设计。

2. C高并发服务器设计
1) 基本概念

Ø 阻塞和非阻塞socket

所谓阻塞Socket,是指其完成指定的任务之前不允许程序调用另一个函数,在Windows下还会阻塞本线程消息的发送。所谓非阻塞Socket,是指操作启动之后,如果可以立即得到结果就返回结果,否则返回表示结果需要等待的错误信息,不等待任务完成函数就返回。一个比较有意思的问题是accept的Socket是阻塞的还是非阻塞的呢?下边是MSDN上边的一段话:The accept function extracts thefirst connection on the queue of pending connections on socket s. It thencreates and returns a handle to the new socket. The newly created socket is thesocket that will handle the actual connection; it has the same properties assocket s, including the asynchronous events registered with the WSAAsyncSelector WSAEventSelect functions.

Ø 同步/异步IO

有两种类型的文件IO同步:同步文件IO和异步文件IO。异步文件IO也就是重叠IO。 
      在同步文件IO中,线程启动一个IO操作然后就立即进入等待状态,直到IO操作完成后才醒来继续执行。而异步文件IO方式中,线程发送一个IO请求到内核,然后继续处理其他的事情,内核完成IO请求后,将会通知线程IO操作完成了。 
      如果IO请求需要大量时间执行的话,异步文件IO方式可以显著提高效率,因为在线程等待的这段时间内,CPU将会调度其他线程进行执行,如果没有其他线程需要执行的话,这段时间将会浪费掉(可能会调度操作系统的零页线程)。如果IO请求操作很快,用异步IO方式反而还低效,还不如用同步IO方式。 
      同步IO在同一时刻只允许一个IO操作,也就是说对于同一个文件句柄的IO操作是序列化的,即使使用两个线程也不能同时对同一个文件句柄同时发出读写操作。重叠IO允许一个或多个线程同时发出IO请求。异步IO在请求完成时,通过将文件句柄设为有信号状态来通知应用程序,或者应用程序通过GetOverlappedResult察看IO请求是否完成,也可以通过一个事件对象来通知应用程序。高并发系统通常采用异步IO方式提高系统性能。

Ø 事件分离器

事件分离器的概念是针对异步IO来说的。在同步IO的情况下,执行操作等待返回结果,不要事件分离器。异步IO的时候,发送请求后,结果是通过事件通知的。这是产生了事件分离器的需求。事件分离器主要任务是管理和分离不同文件描述符上的所发生的事件,让后通知相应的事件,派发相应的动作。

Ø 线程池

线程池基本上比较简单,实现线程的借入和借出,创建和销毁。最完好可以做到通过一个事件触发一个线程开始工作(注:在epoll中,事件触发又分为边沿触发和水平触发)。

2) 常见的设计模式

根据Socket的阻塞非阻塞,IO的同步和异步。可以分为如下4中情形

阻塞同步 阻塞异步
非阻塞同步 非阻塞异步

阻塞同步方式是原始的方式,也是许多教科书上介绍的方式,因为Socket和IO默认的为阻塞和同步方式。基本流程如下:

listen_fd = socket( AF_INET,SOCK_STREAM,0 )

bind( listen_fd, (struct sockaddr*)&my_addr, sizeof(struct sockaddr_in))

listen( listen_fd,1 )

accept( listen_fd, (struct sockaddr*)&remote_addr,&addr_len )

recv( accept_fd ,&in_buf ,1024 ,0 )

close(accept_fd)

阻塞异步方式有所改进,但是Socket的阻塞方式,前一个连接没有处理完成,下一个连接不能接入,是高并发服务器所不可接收的方式。只不过在上边阻塞同步方式的基础上使用select(严格来说select是一种IO多路服用技术。因为linux尚没有完整的实现异步IO,而winsock实在理解socket没有linux上面那么直观。,这里为了方便,没有做严格的区分)或者其它异步IO方式。

非阻塞同步方式,通过设置socket选项为NONBLOCK,可以很快的接收连接,但是处理采用同步IO方式,服务器处理性能也比较差。

上边三种方式不做深入介绍。下边主要从非阻塞异步IO方式介绍。

非阻塞异步IO方式中,由于异步IO方式在同一系统可能有多种实现,不同系统也有不同实现,下边介绍几种常见的IO方式和服务器框架。

Ø Select

Select采用轮训注册的fd方式。是一种比较老的IO多路服用实现方式,效率相对要差一些。Select方式在windows和linux上都支持。

基本框架如下:


socket( AF_INET,SOCK_STREAM,0 )
fcntl(listen_fd, F_SETFL,flags|O_NONBLOCK);
bind( listen_fd, (structsockaddr *)&my_addr,sizeof(struct sockaddr_in))
listen( listen_fd,1 )
FD_ZERO( &fd_sets );
FD_SET(listen_fd,&fd_sets);
for(k=0; k<=i; k++){

FD_SET(accept_fds[k],&fd_sets);
}
events = select( max_fd + 1,&fd_sets, NULL, NULL, NULL );
if(FD_ISSET(listen_fd,&fd_sets) ){
accept_fd = accept( listen_fd, (structsockaddr
*)&remote_addr,&addr_len );
}
for( j=0; j<=i; j++ ){
if(
FD_ISSET(accept_fds[j],&fd_sets) ){

recv( accept_fds[j] ,&in_buf ,1024 ,0 );
}
}

Ø Epoll

Epoll是linux2.6内核以后支持的一种高性能的IO多路服用技术。服务器框架如下:

socket( AF_INET,SOCK_STREAM,0 )
fcntl(listen_fd, F_SETFL,flags|O_NONBLOCK);
bind( listen_fd, (structsockaddr *)&my_addr,sizeof(struct sockaddr_in))
listen( listen_fd,1 )
epoll_ctl(epfd,EPOLL_CTL_ADD,listen_fd,&ev);
ev_s = epoll_wait(epfd,events,20,500 );
for(i=0; i<ev_s;i++){

if(events[i].data.fd==listen_fd){

accept_fd = accept( listen_fd,(structsockaddr *)&remote_addr,&addr_len
);

fcntl(accept_fd, F_SETFL,flags|O_NONBLOCK);

epoll_ctl(epfd,EPOLL_CTL_ADD,accept_fd,&ev);

}

else if(events[i].events&EPOLLIN){

recv( events[i].data.fd ,&in_buf,1024 ,0 );

}
}

Ø AIO

在windows上微软实现了异步IO,通过AIO可以方便的实现高并发的服务器。框架如下:

WSAStartup( 0x0202 , & wsaData)
CreateIoCompletionPort(INVALID_HANDLE_VALUE,NULL, 0 , 0 )
WSASocket(AF_INET,SOCK_STREAM, 0 , NULL, 0 , WSA_FLAG_OVERLAPPED)
bind(Listen, (PSOCKADDR) & InternetAddr, sizeof
(InternetAddr))
listen(Listen, 5 )
WSAAccept(Listen, NULL, NULL,NULL, 0 )
PerHandleData =(LPPER_HANDLE_DATA) GlobalAlloc(GPTR, sizeof
(PER_HANDLE_DATA)
CreateIoCompletionPort((HANDLE)Accept, CompletionPort, (DWORD) PerHandleData,
0 )
PerIoData= (LPPER_IO_OPERATION_DATA)GlobalAlloc(GPTR, sizeof
(PER_IO_OPERATION_DATA))
WSARecv(Accept,&(PerIoData->DataBuf),1,&RecvBytes,&Flags,&(PerIoData->Overlapped),
NULL)
(GetQueuedCompletionStatus(CompletionPort, & BytesTransferred,
(LPDWORD) &
PerHandleData,(LPOVERLAPPED * ) & PerIoData, INFINITE)
if (PerIoData -> BytesRECV >PerIoData ->
BytesSEND){
WSASend(PerHandleData-> Socket, & (PerIoData
->DataBuf), 1 , & SendBytes, 0 ,

& (PerIoData ->Overlapped), NULL)
}

3) 引入线程池和事件分离器后

由于上边只是单纯的使用非阻塞Socket和异步IO的方式。提高了接收连接和处理的速度。但是还是不能解决两个客户端同时连接的问题。这时就需要引入多线程机制。引入多线程后,又有许多策略。Linux上通常采用主进程负责接收连接,之后fork子进程处理连接。Windows通常采用线程池方式,避免线程创建和销毁的开销,当然linux上也可以采用线程池方式。采用多进程和多线程方式后。事件处理也可以再优化,定义一个简单的事件处理器,把所有事件放入一个队列,各个线程去事件队列取相应的事件,然后自己开始工作。这就是我上边提到的半同步/半异步方式了。如果线程工作的时候是接收到连接后,自己处理后续的发送和接收,然后选出另外一个线程作为领导继续接收连接,其它线程作为追随者。这就是领导者/追随者模式了。具体可以参考ACE的Reactor和Preactor的具体实现。半同步和/半异步网上也有很多的讨论,可以自己深入研究。代码就比较复杂了,这里就不给出代码了。

二、分布式系统设计

前面讲述了分布式系统中的核心的服务器的实现。可以是http服务器,缓存服务器,分布式文件系统等的内部实现。下边主要从一个高并发的大型网站出发,看一个高并发系统的设计。下边是一个高并发系统的逻辑结构:

分布式系统设计

主要是参考这篇文章http://www.chinaz.com/web/2010/0310/108211.shtml。下边主要想从这个架构的各个部分的实现展开。

1. 缓存系统

缓存是每一个高并发,高可用系统不可或缺的模块。下边就几个常见缓存系统系统进行介绍。

Squid

Squid作为一个前端缓存,通常部署在网络的离用户最近的地方,通过缓存网站的页面,使用户不必每次都跑到服务器去取数据,提高系统响应和性能。实现应该比较简单:一个带有存储功能的代理。用户访问页面的时候,由它代理,然后存储请求结果,下次再访问的时候,查看是否需要更新,有更新就去服务器取新数据,否则直接返回用户页面。

Ehcache

Ehcache是一个对象缓存系统。通常在J2EE中配合Hibernate使用,这里请原谅作者本人之前是做J2EE开发的,其它使用方式暂不是很了解。应用查询数据库,对经常需要查询,却更新不频繁的数据,可以放入ehcache缓存,提高访问速度。Ehcahe支持内存缓存和硬盘两种方式,支持分布式缓存。数据缓存的基本原理就是:为需要缓存的对象建立一个map,临时对象放入map,查询的时候先查询map,没有找到再查找数据库。关机时可以序列化到硬盘。分布式缓存没有研究过。

页面缓存和动态页面静态化

在大型网站经常使用的一种缓存技术就是动态页面的缓存。由于动态页面经常更新,上边的缓存就不起作用了。通常会采用SSI(Server side include)等技术将动态页面的或者页面片段进行缓存。

还有一种就是动态页面静态化。

2. 负载均衡系统

Ø 负载均衡策略

负载均衡策略有随机分配,平均分配,分布式一致性hash等。随机分配就是通过随机数选择一个服务器来服务。平均分配就是一次循环分配一次。分布式一致性hash算法,比较负载,把资源和节点映射到一个换上,然后通过一定的算法资源对应到节点上,使得添加和去掉服务器变得非常容易,减少对其它服务器的影响。很有名的一个算法,据说是P2P的基础。了解不是很深,就不详细说了,要露马脚了。

Ø 软件负载均衡

软件负载均衡可以采用很多方案,常见的几个方案有:

基于DNS的负载均衡,通过DNS正向区域的配置,将一个域名根据一定的策略解析到多个ip地址,实现负载均衡,这里需要DNS服务器的配合。
基于LVS的负载均衡。LVS可以将多个linux服务器做成一个虚拟的服务器,对外提供服务器,实现负载均衡。
基于Iptables的负载均衡。Iptables可以通过做nat,对外提供一个虚拟IP,对内映射到多个服务器实现负载均衡。基本上可以和硬件均衡方案一致了,这里的linux服务器相当于一台路由器。

Ø 硬件负载均衡

基于路由器的负载均衡,在路由器上配置nat实现负载均衡。对外网一个虚拟IP,内网映射几个内网IP。一些网络设备厂商也提供了一些负载均衡的设备,如F5,不过价格不菲哦。数据库的负载均衡数据库的负载均衡可以是数据库厂商提供的集群方案。

云计算

转载信息:

作者:周顺利
原文链接:http://blog.csdn.net/shatty/article/details/6629896
注:本文大多数观点和代码都是从网上或者开源代码中抄来的,为了疏理和组织这片文章,作者也费了不少心血,为了表示对我劳动的尊重,请转载时注明作者和出处。

| 1 分2 分3 分4 分5 分 (4.50- 6票) Loading ... Loading ... | 归档目录:C/C++, IO编程, 多线程编程 | 标签: , , , , , |

DRBD源码分析(二)——内核模块网络配置和启动

在上一篇里面分析到了基于netlink的connector,connector正是内核态与用户态配置命令交互的通道。用户通过调用用户态的工具,发送相应的命令参数,用户态工具将命令参数转换成相应的消息包,内核态解析消息后得到相应的指令,继续转换成函数调用,最后得以执行。

首先仔细看一下上一节提到的创建connector时注册的收数据的回调函数:

#ifdef KERNEL_HAS_CN_SKB_PARMS
STATIC void drbd_connector_callback(struct cn_msg *req, struct netlink_skb_parms *nsp)
{
#else
STATIC void drbd_connector_callback(void *data)
{
struct cn_msg *req = data;
#endif
struct drbd_nl_cfg_req *nlp = (struct drbd_nl_cfg_req *)req->data;
struct cn_handler_struct *cm;
struct cn_msg *cn_reply;
struct drbd_nl_cfg_reply *reply;
struct drbd_conf *mdev;
int retcode, rr;
int reply_size = sizeof(struct cn_msg)
+ sizeof(struct drbd_nl_cfg_reply)
+ sizeof(short int);

if (!try_module_get(THIS_MODULE)) {
printk(KERN_ERR "drbd: try_module_get() failed!\n");
return;
}

#ifdef KERNEL_HAS_CN_SKB_PARMS
if (!cap_raised(nsp->eff_cap, CAP_SYS_ADMIN)) {
retcode = ERR_PERM;
goto fail;
}
#endif

mdev = ensure_mdev(nlp);
if (!mdev) {
retcode = ERR_MINOR_INVALID;
goto fail;
}

trace_drbd_netlink(req, 1);

if (nlp->packet_type >= P_nl_after_last_packet) {
retcode = ERR_PACKET_NR;
goto fail;
}
printk("packet_type is %d\n", nlp->packet_type);
cm = cnd_table + nlp->packet_type;

/* This may happen if packet number is 0: */
if (cm->function == NULL) {
retcode = ERR_PACKET_NR;
goto fail;
}

reply_size += cm->reply_body_size;

/* allocation not in the IO path, cqueue thread context */
cn_reply = kmalloc(reply_size, GFP_KERNEL);
if (!cn_reply) {
retcode = ERR_NOMEM;
goto fail;
}
reply = (struct drbd_nl_cfg_reply *) cn_reply->data;

reply->packet_type =
cm->reply_body_size ? nlp->packet_type : P_nl_after_last_packet;
reply->minor = nlp->drbd_minor;
reply->ret_code = NO_ERROR; /* Might by modified by cm->function. */
/* reply->tag_list; might be modified by cm->function. */

rr = cm->function(mdev, nlp, reply);

cn_reply->id = req->id;
cn_reply->seq = req->seq;
cn_reply->ack = req->ack + 1;
cn_reply->len = sizeof(struct drbd_nl_cfg_reply) + rr;
cn_reply->flags = 0;

trace_drbd_netlink(cn_reply, 0);
rr = cn_netlink_send(cn_reply, CN_IDX_DRBD, GFP_KERNEL);
if (rr && rr != -ESRCH)
printk(KERN_INFO "drbd: cn_netlink_send()=%d\n", rr);

kfree(cn_reply);
module_put(THIS_MODULE);
return;
fail:
drbd_nl_send_reply(req, retcode);
module_put(THIS_MODULE);
}

值得注意的是:

rr=cm->function(mdev,nlp,reply);

这一句,这里相当于是一个多态,function绑定到哪一个方法由消息包中携带的包类型决定:


cm=cnd_table+nlp->packet_type;

系统在初始化时级生成了一个全局的静态函数表,类似P_primary的标识符是在编译时动态生成的宏。表示其所在的元素的下标,同时也月包类型相对应。

static struct cn_handler_struct cnd_table[] = {
[ P_primary ] = { &drbd_nl_primary, 0 },
[ P_secondary ] = { &drbd_nl_secondary, 0 },
[ P_disk_conf ] = { &drbd_nl_disk_conf, 0 },
[ P_detach ] = { &drbd_nl_detach, 0 },
[ P_net_conf ] = { &drbd_nl_net_conf, 0 },
[ P_disconnect ] = { &drbd_nl_disconnect, 0 },
[ P_resize ] = { &drbd_nl_resize, 0 },
[ P_syncer_conf ] = { &drbd_nl_syncer_conf, 0 },
[ P_invalidate ] = { &drbd_nl_invalidate, 0 },
[ P_invalidate_peer ] = { &drbd_nl_invalidate_peer, 0 },
[ P_pause_sync ] = { &drbd_nl_pause_sync, 0 },
[ P_resume_sync ] = { &drbd_nl_resume_sync, 0 },
[ P_suspend_io ] = { &drbd_nl_suspend_io, 0 },
[ P_resume_io ] = { &drbd_nl_resume_io, 0 },
[ P_outdate ] = { &drbd_nl_outdate, 0 },
[ P_get_config ] = { &drbd_nl_get_config,
sizeof(struct syncer_conf_tag_len_struct) +
sizeof(struct disk_conf_tag_len_struct) +
sizeof(struct net_conf_tag_len_struct) },
[ P_get_state ] = { &drbd_nl_get_state,
sizeof(struct get_state_tag_len_struct) +
sizeof(struct sync_progress_tag_len_struct) },
[ P_get_uuids ] = { &drbd_nl_get_uuids,
sizeof(struct get_uuids_tag_len_struct) },
[ P_get_timeout_flag ] = { &drbd_nl_get_timeout_flag,
sizeof(struct get_timeout_flag_tag_len_struct)},
[ P_start_ov ] = { &drbd_nl_start_ov, 0 },
[ P_new_c_uuid ] = { &drbd_nl_new_c_uuid, 0 },
};

比如,在一次完整的用户态与内核态的交互中,用户态会多次发出P_get_state消息,该消息的包类型码为17。

类似cn_handler_struct这样的函数表,在drbd的代码中随处可见,无论是内核态还是用户态,这样一致的风格,应该非常利于扩展和维护。看代码的人也会觉得非常轻松,不至于无章可循。

DRBD的配置信息、虚拟设备、网络通信端口、对端信息等都是通过drbdsetup或者drbdadm工具以netlink消息包发送到内核态的。

在收到5号消息包时,drbd_nl_net_conf会被调用。在该函数中,会启动worker内核线程,该线程监控一个等待队列,当有事件到来时,即取出处理:

int drbd_worker(struct drbd_thread* thi)
{
...
w = NULL;
spin_lock_irq(&mdev->data.work.q_lock);
ERR_IF(list_empty(&mdev->data.work.q))
{
/* something terribly wrong in our logic.
* we were able to down() the semaphore,
* but the list is empty... doh.
*
* what is the best thing to do now?
* try again from scratch, restarting the receiver,
* asender, whatnot? could break even more ugly,
* e.g. when we are primary, but no good local data.
*
* I'll try to get away just starting over this loop.
*/
spin_unlock_irq(&mdev->data.work.q_lock);
continue;
}
w = list_entry(mdev->data.work.q.next, struct drbd_work, list);
list_del_init(&w->list);
spin_unlock_irq(&mdev->data.work.q_lock);

if (!w->cb(mdev, w, mdev->state.conn < C_CONNECTED))
{
/* dev_warn(DEV, "worker: a callback failed! \n"); */
if (mdev->state.conn >= C_CONNECTED)
drbd_force_state(mdev, NS(conn, C_NETWORK_FAILURE));
}
...
}

启动了worker线程之后,几乎所有的内核态的事务都会交给这个线程来处理。

继续回到drbd_nl_net_conf方法中,在初始化完worker线程后,会继续执行如下语句:

retcode=_drbd_request_state(mdev,NS(conn,C_UNCONNECTED),CS_VERBOSE);

这里既是与对端协商确定当前谁是主节点。在该方法中会向等待队列中放入一个事务,该事务为启动一个receiver线程,receiver线程会使用配置文件中指定的端口和IP信息建立tcp socket监听,等待对端的链接。此时,如果对端一直未有连接过来,本端尝试与对端连接也一直无法建立,则会根据配置等待指定的超时时间,之后会将本段置为Standalone状态。这也就是我们常见的两台服务器同时重启时,会发现一端的启动过程卡在drbd的等待上面。

| 1 分2 分3 分4 分5 分 (4.83- 6票) Loading ... Loading ... | 归档目录:C/C++, DRBD | 标签: |

迷宫营救公主算法

今天下班前在公司的技术题库中看到这道题目,思路很快就有了,递归遍历每一条可能的路径,然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了,在矩阵较小的时候还好,当矩阵稍微大一点时根本算不过来,感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了,也完全没有意义。公主等到花儿都谢啦。。

貌似这位同学的算法还不错,还没来得及研究,先做个链接:http://blog.csdn.net/joseph_1118/article/details/9390301

应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里,后面再继续研究优化。题目和代码都在一起:

/**
* 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。
* 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只
* 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步。地图由’S’,’P’,’.’,’*’
* 四种符号构成,’.’表示王子可以通过,’*’表示墙,王子不能通过;’S’表示王子的位置;’P’表示公主
* 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:
*/

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 9票) Loading ... Loading ... | 归档目录:Java, 算法数据结构 | 标签: , |
返回顶部