本文由 酷壳coolshell 译自墙外文章“NoSQL Data Modeling Techniques”。 这篇文章看完之后，你可能会对NoSQL的数据结构会有些感觉。我的感觉是，关系型数据库想把一致性，完整性，索引，CRUD都干 好，NoSQL只干某一种事，但是牺牲了很多别的东西。总体来说，我觉得NoSQL更适合做Cache。 下面是正文—— NoSQL 数据库经常被用作很多非功能性的地方，如，扩展性，性能和一致性的地方。这些NoSQL的特性在理论和实践中都正在被大众广泛地研究着，研究的热点正是那些和性能分布式相关的非功能性的东西，我们都知道 CAP 理论被 很好地应用于了 NoSQL 系统中（陈皓注：CAP即，一致性(Consistency)， 可用性(Availability)， 分区容忍性(Partition tolerance)，在分布式系统中，这三个要素最多只能同时实现两个，而NoSQL一般放弃的是一致性）。但在另一方面，NoSQL的数据建模技术却 因为缺乏像关系型数据库那样的基础理论没有被世人很好地研究。这篇文章从数据建模方面对NoSQL家族进行了比较，并讨论几个常见的数据建模技术。 要开始讨论数据建模技术，我们不得不或多或少地先系统地看一下NoSQL数据模型的成长的趋势，以此我们可以了一些他们内在的联系。下图是 NoSQL家族的进化图，我们可以看到这样的进化：Key-Value时代，BigTable时代，Document时代，全文搜索时代，和Graph数 据库时代：（陈皓注：注意图中SQL说的那句话，NoSQL再这样发展下去就是SQL了，哈哈。） NoSQL Data Models 首先，我们需要注意的是SQL和关系型数据模型已存在了很长的时间，这种面向用户的自然性意味着： 最终用户一般更感兴趣于数据的聚合显示，而不是分离的数据，这主要通过SQL来完成。 我们无法通过人手工控制数据的并发性，完整性，一致性，或是数据类型校验这些东西的。这就是为什么SQL需要在事务，二维表结构（schema）和外表联合上做很多事。 另一方面，SQL可以让软件应用程序在很多情况下不需要关心数据库的数据聚合，和数据完整性和有效性进行控制。而如果我们去除了数据一致性，完整性这些东西，会对性能和分布存储有着重的帮助。正因为如此，我们才有数据模型的进化： Key-Value 键值对存储是非常简单而强大的。下面的很多技术基本上都是基于这个技术开始发展的。但 是，Key-Value有一个非常致命的问题，那就是如果我们需要查找一段范围内的key。（陈皓注：学过hash-table数据结构的人都应该知 道，hash-table是非序列容器，其并不像数组，链接，队列这些有序容器，我们可以控制数据存储的顺序）。于是，有序键值 （Ordered Key-Value） 数据模型被设计出来解决这一限制，来从根本上提高数据集的问题。 Ordered Key-Value 有序键值模型也非常强大，但是，其也没有对Value提供某种数据模 型。通常来说，Value的模型可以由应用负责解析和存取。这种很不方便，于是出现了 BigTable类型的数据库，这个数据模型其实就是map里有map，map里再套map，一层一层套下去，也就是层层嵌套的key- [...]
Java NIO原理图文分析及代码实现
具体分析： 一．java NIO 和阻塞I/O的区别 1. 阻塞I/O通信模型 假如现在你对阻塞I/O已有了一定了解，我们知道阻塞I/O在调用InputStream.read()方法时是阻塞的，它会一直等到数据到来时（或超时）才会返回；同样，在调用ServerSocket.accept()方法时，也会一直阻塞到有客户端连接才会返回，每个客户端连接过来后，服务端都会启动一个线程去处理该客户端的请求。阻塞I/O的通信模型示意图如下： 如果你细细分析，一定会发现阻塞I/O存在一些缺点。根据阻塞I/O通信模型，我总结了它的两点缺点： 1. 当客户端多时，会创建大量的处理线程。且每个线程都要占用栈空间和一些CPU时间 2. 阻塞可能带来频繁的上下文切换，且大部分上下文切换可能是无意义的。 在这种情况下非阻塞式I/O就有了它的应用前景。 2. java NIO原理及通信模型 Java NIO是在jdk1.4开始使用的，它既可以说成“新I/O”，也可以说成非阻塞式I/O。下面是java NIO的工作原理： 1. 由一个专门的线程来处理所有的 IO 事件，并负责分发。 2. 事件驱动机制：事件到的时候触发，而不是同步的去监视事件。 3. 线程通讯：线程之间通过 wait,notify 等方式通讯。保证每次上下文切换都是有意义的。减少无谓的线程切换。 阅读过一些资料之后，下面贴出我理解的java NIO的工作原理图： （注：每个线程的处理流程大概都是读取数据、解码、计算处理、编码、发送响应。） Java NIO的服务端只需启动一个专门的线程来处理所有的 IO 事件，这种通信模型是怎么实现的呢？呵呵，我们一起来探究它的奥秘吧。java NIO采用了双向通道（channel）进行数据传输，而不是单向的流（stream），在通道上可以注册我们感兴趣的事件。一共有以下四种事件： 事件名 对应值 [...]
八种常用的排序算法
下面要讲到的8种排序都属于内部排序，既在内存中完成，主要从理论原理方面来分析的。 插入排序 ①直接插入排序 例：六个数12 15 9 20 6 31 24 用直接插入排序，如下图： 思路： 第一步：从给出的六个数中，随便拿出一个数，比如12，形成一个有序的数据序列（一个数当然是有序的数据序列了，不看12之外的数，就当其他的数不存在）； 第二步：从剩下的五个数中挑出一个数来，比如15，和刚才的12作比较，12<15，因此，放在12后面，形成数据序列12 15； 第三步：从剩下的四个数中挑出一个数来，比如9，和刚才的有序数据序列12 15作比较，9 < 12 < 15，因此，放在最前面，形成数据序列9 12 15； 第N步，经过这样一个一个的插入并对比，就形成了上图所示的排序结果。在一个元素插入时，首先要和数据序列中最大的元素作比较，如果遇到相同的，则放在相同元素的后面。 特性： 因为要不断的插入，因此直接插入排序一般采用链表结构，属于稳定排序。 ②希尔（Shell）排序 是直接插入排序的改进，例：十个数57 68 59 52 72 28 96 33 24 19用希尔排序，如下图： 思路： 第一步：用排序数字的总数除以2，取奇数得到步长（增量）d1 [...]
常用数据结构–二叉树
二叉树并不是一种特殊的树，是一种独立的数据结构。下面是一些关于二叉树入门级的、纯理论的东东，高手请Alt+F4，千万别往下翻，会影响您的心情！ 二叉树的分类 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。 完全二叉树：除了最下面一层，其他层结点都是饱满的，并且最下层上的结点都集中在该层最左边的若干位置上。（满二叉树也是完全二叉树） 非完全二叉树：既不是满二叉树，也非完全二叉树。 例： 图1 二叉树的遍历 前序遍历（先根遍历）：根左右。 后序遍历（后根遍历）：左右根。 中序遍历（中根遍历）：左跟右。 层次遍历：一层一层自左向右。 例： 图2 图中前序遍历结果是：1,2,4,5,7,8,3,6； 图中中序遍历结果是：4,2,7,8,5,1,3,6； 图中后序遍历结果是：4,8,7,5,2,6,3,1； 图中层次遍历结果是：1,2,3,4,5,6,7,8； 树和二叉树的转换 将树的孩子结点转成二叉树的左子结点，树的兄弟结点转成二叉树的右子结点。 例： 图3 二叉树的一些重要特性 1、在二叉树的第i层上最多有2^(n-1)个结点（i>=1）； 例： 以图1为例：任一图中第2层，最多只能有2个结点。验证正确！ 2、深度为k的二叉树最多有2^k – 1个结点（K>=1）； 例： [...]
常用数据结构–线性结构
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图： 常用的线性结构有：线性表，栈，队列，循环队列，数组。线性表中包括顺序表、链表等，其中，栈和队列只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；线性表则是在内存中数据的一种组织、存储的方式。 顺序表 顺序表将元素一个接一个的存入一组连续的存储单元中，在内存物理上是连续的。如下图： 顺序表存储密度较大，节省空间；但需要事先确定容量，在时间性能方面，读运算较快，时间复杂度为O(1)；查找运算为O(n/2)，和链表同样；插入运算和删除运算如果要操作中间一个元素，比如3，那么就需要把3后面的元素全部进行移动，因此时间复杂度相对链表要大一些，插入时间复杂度最好为O(0)或最坏为O(n)；删除时间复杂度为O([n-1]/2)； 链表 链表拥有很多结点，每个结点前半部分是数据域，后半部分是指针域，指针域指针指向下一个结点；链表可分为单链表、循环链表和双链表。 单链表： 从上图可以看出，单链表的上一个结点指针指向下一个结点，最后一个结点的指针域为null。 结点的删除： 删除一个结点，如删除上图中q结点，只需将p结点中的指针域指向a3，然后将a2释放掉（free）即可。 结点的插入： 插入一个结点，如插入上图中s结点，首先将s的指针域指向a2（也就是把s的next赋值为p的next），然后将p结点的指针域指向x即可（p的next指向x）。 循环链表 循环链表与单链表唯一不同之处是，循环链表的最后一个结点指针不为空，而是指向头结点。结点的插入和删除和单链表非常相似，就不再示范了。 双链表 双链表拥有一前一后两个指针域，从两个不同的方向把链表连接起来，如此一来，从两个不同的方向形成了两条链，因此成为双链表。因此，双链表的灵活度要大于单链表。 结点的删除： 双链表的操作比单链表要稍显复杂（按照单链表思路来做其实也不难），如上图，要删除p节点，首先需要将a1的后驱指向a3，然后将a3的前驱指向a1，最后将p节点释放掉即可。 结点的插入： 如上图，插入q结点，首先要按照方向，将步骤拆分，首先将q节点的前驱指向p结点后驱，紧接着将x后驱指向a2；然后按照顺序完成图中所示的3、4步即可。（经@llhhyy1989 @voteforvip @wanghuan203 三位童鞋的指正，发现此处有误，正确插入方法可查看评论，为保留错误原文不做改动！不懂具体插入过程可移步：百度知道） 从空间性能来看，链表的存储密度要差一些，但在容量分配上更灵活一些。从时间性能来看，查找运算与顺序存储相同，插入运算和删除运算的时间复杂度为O(1)，要更优于顺序存储，但读运算则弱一些，为O([n+1]/2)，最好为1，最坏为n。 栈 上面提到栈属于一个逻辑概念，栈的实现可以用顺序也可以用链式。它遵循先进后出原则，如下图： Java中测试代码如下： package com.snail.test; import java.util.Stack; public class TestStack { public static void main(String[] args) [...]
Memcached运行状态
STAT pid 22459 进程ID STAT uptime 1027046 服务器运行秒数 STAT time 1273043062 服务器当前unix时间戳 STAT version 1.4.4 服务器版本 STAT pointer_size 64 操作系统字大小(这台服务器是64位的) STAT rusage_user 0.040000 进程累计用户时间 STAT rusage_system 0.260000 进程累计系统时间 STAT curr_connections 10 当前打开连接数 STAT total_connections 82 曾打开的连接总数 STAT connection_structures 13 服务器分配的连接结构数 [...]
GC策略的调优
GC策略在G1还没成熟的情况下，目前主要有串行、并行和并发三种，对于大内存的应用而言，串行的性能太低，因此使用到的主要是并行和并发两种，具体这两种GC的策略在深入JVM章节中已讲解， 并行和并发GC的策略通过-XX:+UseParallelGC和-XX:+UseConcMarkSweepGC来指定，还有一些细节的配置参数用来配置策略的执行方式，例如：-XX:ParallelGCThreads、-XX:CMSInitiatingOccupancyFraction等，新生代对象回收只可选择并行，在此就举例来看看两种GC策略在Full GC时的具体表现状况。 测试GC策略状况的代码如下： public class GCPolicyDemo { /** * @param args */ public static void main(String[] args) throws Exception{ System.out.println("ready to start"); Thread.sleep(10000); List<GCPolicyDataObject> cacheObjects=new ArrayList<GCPolicyDataObject>(); for (int i = 0; i < 2048; i++) { [...]
UDP实现MINA聊天服务器时处理分片的线程池的实现–0.1版
import java.util.HashMap; import java.util.LinkedList; import org.apache.mina.core.buffer.IoBuffer; import cn.edu.zju.cst.mina.im.server.entity.Group; import cn.edu.zju.cst.mina.im.server.entity.Piece; import cn.edu.zju.cst.mina.im.server.util.Configuration; public class GroupManage extends ThreadGroup { private static boolean isClosed = false; private HashMap<Long, Group> groupList; private LinkedList<Long> workQueue; private int threadID; private static int threadPoolID; private int [...]
深入研究java.lang.ThreadLocal类
一、概述 ThreadLocal是什么呢？其实ThreadLocal并非是一个线程的本地实现版本，它并不是一个Thread，而是threadlocalvariable(线程局部变量)。也许把它命名为ThreadLocalVar更加合适。线程局部变量(ThreadLocal)其实的功用非常简单，就是为每一个使用该变量的线程都提供一个变量值的副本，是Java中一种较为特殊的线程绑定机制，是每一个线程都可以独立地改变自己的副本，而不会和其它线程的副本冲突。 从线程的角度看，每个线程都保持一个对其线程局部变量副本的隐式引用，只要线程是活动的并且 ThreadLocal 实例是可访问的；在线程消失之后，其线程局部实例的所有副本都会被垃圾回收（除非存在对这些副本的其他引用）。 通过ThreadLocal存取的数据，总是与当前线程相关，也就是说，JVM 为每个运行的线程，绑定了私有的本地实例存取空间，从而为多线程环境常出现的并发访问问题提供了一种隔离机制。 ThreadLocal是如何做到为每一个线程维护变量的副本的呢？其实实现的思路很简单，在ThreadLocal类中有一个Map，用于存储每一个线程的变量的副本。 概括起来说，对于多线程资源共享的问题，同步机制采用了“以时间换空间”的方式，而ThreadLocal采用了“以空间换时间”的方式。前者仅提供一份变量，让不同的线程排队访问，而后者为每一个线程都提供了一份变量，因此可以同时访问而互不影响。 二、API说明 ThreadLocal() 创建一个线程本地变量。 T get() 返回此线程局部变量的当前线程副本中的值，如果这是线程第一次调用该方法，则创建并初始化此副本。 protected T initialValue() 返回此线程局部变量的当前线程的初始值。最多在每次访问线程来获得每个线程局部变量时调用此方法一次，即线程第一次使用 get() 方法访问变量的时候。如果线程先于 get 方法调用 set(T) 方法，则不会在线程中再调用 initialValue 方法。 若该实现只返回 null；如果程序员希望将线程局部变量初始化为 null 以外的某个值，则必须为 [...]
Java线程池
通过Executors创建线程池的时候调用newFixedThreadPool方法，继承的大概结构如下： 创建完成之后，线程池的结构如下： 在创建完线程池之后就可以调用execute方法来执行给定的Runnable了，具体的代码如下： public void execute(Runnable command) { if (command == null) throw new NullPointerException(); if (poolSize >= corePoolSize || !addIfUnderCorePoolSize(command)) { if (runState == RUNNING && workQueue.offer(command)) { if (runState != RUNNING || poolSize == 0) ensureQueuedTaskHandled(command); } else [...]