神奇的Unsafe类: Java实例内存布局初探


前情提要

Java相比C/C++最大的一个特点就是没有提供指针, 或者说没有提供对内存的直接访问操作, 导致很多比较底层的操作根本无法进行.
一方面给Java带来了内存上的安全性, 不像C/C++稍微一处理不好就会Segment Fault, 更可怕的是内存访问越界了程序却没有退出, 这会导致程序发生一些莫名其妙的事情, 比如说由于错误修改了循环的迭代变量导致循环无法退出(被坑过的我流下了眼泪)等.
但另一方面降低了Java的灵活性, 也让人无法弄清楚Java的运行时内存布局, 以及进行一些神奇的Hack操作.

但是在Hotspot虚拟机中, 提供了UnSafe类可以给我们进行很多非常底层的虚拟机操作, 包括:

  • 根据对象和偏移读写内存的getInt(Object o, long offset)/putInt(Object o, long offset, int x)
  • 根据地址直接读写内存的getAddress(long address)/putAddress(long address, long x)
  • 在直接内存区(Direct Memory)中分配内存的allocateMemory(long bytes)/freeMemory(long address), 这部分内存主要是被java.nio中的类所使用
  • 内存直接复制copyMemory(Object srcBase, long srcOffset, Object destBase, long destOffset, long bytes) 类似于memcpy
  • 属性偏移计算方法objectFieldOffset(Field f)
  • 一些底层内存信息addressSize()/pageSize()
  • 从字节码直接生成一个类defineClass(String name, byte[] b, int off, int len)
  • 加载实例也不是一个问题allocateInstance(Class cls)
  • 手动模拟Synchronized的加锁解锁操作monitorEnter(Object o)/monitorExit(Object o)
  • 抛出一个异常throwException(Throwable ee)
  • 喜闻乐见的CAS操作compareAndSwapObject(Object o, long offset, Object expected, Object x)
  • 以volatile模式操作某个属性getIntVolatile(Object o, long offset)
  • 读值并直接相加/设置的新原语getAndAddInt(Object var1, long var2, int var4)/getAndSetInt(Object var1, long var2, int var4)
  • 栅栏操作storeFence()/loadFence()

等等

不过, Oracle已经在JDK11里正式移除Unsafe类, 毕竟这些底层操作从某种角度来说破坏了Java构建的安全性, 虽然似乎其实有大量的开源框架都在使用该类, 比如Spring/Netty/Hadoop等等, 在新的JDK11下似乎也有替换的解决方案.
不过这些都不是重点, 本文的重点是如何通过Unsafe类提供的getAddress(long address)观察对象实例的内存布局.

正篇开始

Java的对象实例内存布局其实是一个老生常谈的问题了, 无论是著名的深入理解Java虚拟机还是网上都有很多文章说过这个问题, 但是我几乎没有看到结合实验来说明实例布局的实际情况的文章, 所以本文从实验的角度来说明这个问题.

对象实例内存布局总的来说, 可以分为三块:

  • 对象头
  • 实例数据
  • 对齐填充

下图展示了32位虚拟机的情况:
20190314172833568_30071.png

事实上, 对于64位虚拟机来说对象头其实有128Bit, 也就是16Byte. 在没有开启对象指针压缩的前提下, 对象头的布局才是如下所示:

|------------------------------------------------------------------------------------------------------------|--------------------|
|                                            Object Header (128 bits)                                        |        State       |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                                  Mark Word (64 bits)                         |    Klass Word (64 bits)     |                    |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
| unused:25 | identity_hashcode:31 | unused:1 | age:4 | biased_lock:1 | lock:2 |    OOP to metadata object   |       Normal       |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
| thread:54 |       epoch:2        | unused:1 | age:4 | biased_lock:1 | lock:2 |    OOP to metadata object   |       Biased       |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                       ptr_to_lock_record:62                         | lock:2 |    OOP to metadata object   | Lightweight Locked |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                     ptr_to_heavyweight_monitor:62                   | lock:2 |    OOP to metadata object   | Heavyweight Locked |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                                                                     | lock:2 |    OOP to metadata object   |    Marked for GC   |
|------------------------------------------------------------------------------|-----------------------------|--------------------|

不过, 从JDK6开始, JVM就会默认开启对象指针压缩, 如果要让内存的结构如上图所示, 必须要手动关掉它-XX:-UseCompressedOops才行.

Talk is cheap. Show me the code.

public class MemoryAccess{
    private final static Unsafe unsafe = getUnsafe();
    public int a = 12345678;
    public int b = 87654321;
    public long c = -1;
    public char d = 66;

    public static void main(String[] args){
        MemoryAccess o = new MemoryAccess();
        long base = getBaseAddress(o), size = sizeOf(o);
        System.out.printf("Base: %x, Size: %d\n", base, size);

        // Read Memory First
        readMemory(base, size);

        // Fetch HashCode
        System.out.printf("HashCode: %x\n", o.hashCode());

        // Read a first
        System.out.println("Old a Val: " + o.a);
        // Modify a via memory
        int offset = 24, newAVal = 23333333;
        long newMemoryVal = (unsafe.getAddress(base + offset) & 0xffffffff00000000L) + newAVal;
        unsafe.putAddress(base + offset, newMemoryVal);
        // Read a again
        System.out.println("New a Val: " + o.a);

        // Read Memory Again
        readMemory(base, size);
    }

    static Unsafe getUnsafe(){
        try{
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            return (Unsafe)f.get(null);
        }catch(NoSuchFieldException | IllegalAccessException e){
            e.printStackTrace();
        }
        return null;
    }

    public static long sizeOf(Object object){
        long metaAddr = unsafe.getInt(object, 8L);
        return unsafe.getAddress(metaAddr + 4L) >>> 32;
    }

    static long getBaseAddress(Object obj){
        Object[] array = new Object[]{obj};
        long baseOffset = unsafe.arrayBaseOffset(Object[].class);
        return unsafe.getLong(array, baseOffset);
    }

    static void readMemory(long base, long length){
        System.out.printf("| %3s | %79s | %17s | %23s |\n", "Offset", "Binary", "Hex", "Dec");
        for(int i = 0; i < length; i += 8){
            long val = unsafe.getAddress(base + i);
            int leftVal = (int)(val >> 32);
            int rightVal = (int)(val);
            System.out.printf("| %6d | %s | %8x %8x | %11d %11d |\n", i, getLongBinaryStr(val), leftVal, rightVal, leftVal, rightVal);
        }
    }

    static String getLongBinaryStr(long val){
        return getLongBinaryStr(val, true);
    }

    static String getLongBinaryStr(long val, boolean padding){
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < 64; i++){
            if(padding && i % 4 == 0 && i != 0){
                builder.insert(0, " ");
            }
            builder.insert(0, val & 0x1);
            val = val >>> 1;
        }
        return builder.toString();
    }
}

简单解释一下:

  • getUnsafe用于获取Unsafe类的实例, 因为Unsafe类本来的设计是限定在rt.jar的内部使用, 直接使用getUnsafe()方法的话, 它会在内部验证Caller的类加载器是否为空, 即BootstrapClassLoader.
public static Unsafe getUnsafe() {
    Class cc = sun.reflect.Reflection.getCallerClass(2);
    if (cc.getClassLoader() != null)
        throw new SecurityException("Unsafe");
    return theUnsafe;
}
  • sizeOf用于获取对象实例的大小, 首先是从对象头中取得类在方法区的指针, 然后通过取方法区中的数据获得类的实例大小.
  • getBaseAddress用于获取一个对象实例的基地址, Unsafe类中也没有提供获得对象基地址的方法, 这里用了一个非常巧妙的方法, 即先把对象放到一个数组中, 然后读取数组的值即可知道对象指针的值, 也就是对象实例的基地址了.
  • readMemory用于从基地址开始打印指定长度的内存到控制台, 由于getAddress只能以64bit读取数据, 这里将这64bit分成左右两个部分分别显示十六进制和十进制值
  • getLongBinaryStr用于将long长度的数用带前缀0的二进制打印出来, Long.toBinaryString()是没有前缀0的

输出的结果如下所示:

Base: d4dc74e0, Size: 40
| Offset |                                                                          Binary |               Hex |                     Dec |
|      0 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 |        0        1 |           0           1 |
|      8 | 0000 0000 0000 0000 0000 0000 0000 0000 0001 0111 1110 0011 0100 0010 0100 0000 |        0 17e34240 |           0   400769600 |
|     16 | 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 | ffffffff ffffffff |          -1          -1 |
|     24 | 0000 0101 0011 1001 0111 1111 1011 0001 0000 0000 1011 1100 0110 0001 0100 1110 |  5397fb1   bc614e |    87654321    12345678 |
|     32 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0010 |        0       42 |           0          66 |
HashCode: 6e0be858
Old a Val: 12345678
New a Val: 23333333
| Offset |                                                                          Binary |               Hex |                     Dec |
|      0 | 0000 0000 0000 0000 0000 0000 0110 1110 0000 1011 1110 1000 0101 1000 0000 0001 |       6e  be85801 |         110   199776257 |
|      8 | 0000 0000 0000 0000 0000 0000 0000 0000 0001 0111 1110 0011 0100 0010 0100 0000 |        0 17e34240 |           0   400769600 |
|     16 | 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 | ffffffff ffffffff |          -1          -1 |
|     24 | 0000 0101 0011 1001 0111 1111 1011 0001 0000 0001 0110 0100 0000 1001 1101 0101 |  5397fb1  16409d5 |    87654321    23333333 |
|     32 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0010 |        0       42 |           0          66 |

我们可以看到对象的基地址是0xd4dc74e0, 对象的长度是40Byte.

前128Bit就是之前提到的对象头, 后面的数据分别是64bit长度的属性c=-1, 由于Intel x86是小端序, 所以接下来是32bit长的属性a=12345678和32bit长的属性b=87654321, 最后是8bit长的属性d=66, 以及补齐到64bit对齐的填充0.
和书中说的一样, 实例数据部分会优先分配比较长的属性, 并尽量将相同宽度的属性放在一起.

对于对象头, 参考之前的对象头表, 0x17e34240是指向metadata的指针, 对象长度也是从这个指针所指向的内存中获取的, 而MarkWord部分, 却只知道对象现在是无锁状态(01), 为什么理应放hashCode的部分是0呢?

因为我们还没有计算过hashCode, 只有计算过hashCode, 那么在对象头部分才会将hashCode的值填入.
我们读取过一遍hashCode以后, 再次读取对象头部分的时候, 就会发现hashCode部分存入了之前计算出的hash值, 即0x6e0be858.
从此可见, 对象头中的hashCode相当于是一层简单的缓存, 避免对同一个对象hashCode的重复计算.

后面的代码演示了, 通过直接对内存进行修改来修改对象属性的值. 我们首先读取了属性a的值为12345678, 通过直接对内存进行修改, 我们就其的值改为了23333333.
这里的offset可以通过对对象实例内存进行观察得到, 也可以通过之前提到的objectFieldOffset(Field f)方法获得, 我猜大概也可以直接从方法区中类的metadata中读到.

另外就是这里没有演示出来的一点, 对象的metadata和类的class对象在内存里没有任何关系, 类的class对象也是一个位于堆区的普通对象, 是Class类的一个实例.

总结与展望

通过对Unsafe的操作, 我们能够对对象实例部分的内存进行任意读写, 经过测试, 整个堆区的内存都是可以任意读写的.
这从某种角度来说提供了一个高效的修改对象的方式, 相比反射过程冗长的检查过程, 这种方式简单直接当然也很容易出错, 而且非常依赖于具体的实现.

通过对对象实例内存的读取, 可以对对象实例内存的布局和数据变化有了更加深入的认识和了解, 实例内存布局不再是一个简单的图表或者一个虚拟机实现的头文件, 而是实实在在的数据变化.

考虑到, 我们可以通过对象实例获取到对象方法区的指针, 那么可以通过方法区内存的读取, 从而得到类在方法区内存的布局.
更进一步说, 如果我们能够找到对象的方法表, 而且这块内存可写, 那么我们其实可以做到方法级的Hook操作.
目前已知的一些Hook, 无论是自定义类加载器/动态代理或者是Instrument机制, 我们都只能整体的替换一个类, 而不能做到精准地只替换掉一个方法.
也许, 通过这种操作, 能够实现单独对一个方法的替换.

当然, 这样的hack操作肯定不会在生产环境中使用, 但是从对JVM深入理解以及好玩的角度来说, 我觉得继续探究一下还是挺有意思的.

Ref1: http://mishadoff.com/blog/java-magic-part-4-sun-dot-misc-dot-unsafe/
Ref2: https://github.com/keerath/openjdk-8-source/blob/master/jdk/src/share/classes/sun/misc/Unsafe.java


简单Websocket通信实现


服务端推送技术

众所周知, HTTP协议是客户端向服务端单向请求的文本协议. 一般来说, 服务端返回请求结果以后, TCP连接就会关闭.
在这样的协议模式下, 是无法支持全双工通信的, 也就是服务端无法主动向客户端推送信息, 必须等待客户端请求才能返回信息.
因此, 服务端推送技术一般有如下几种解决方案:

  • 定时轮询: 这种方式是传统WEB解决服务端推送的方案

    • 问题主要是延迟大, 而且对服务端的压力非常高, 当然可以通过在服务端之间加一层缓存之类的方法加以缓解, 但依然效率太低, 而且浪费带宽
  • 长轮询: 是定时轮询的改进版, 即不再每次请求时服务端都立刻返回, 而是直到数据发生变化再返回

    • 能够有效节省带宽, 但问题主要是, 需要同时维持大量HTTP连接, 对服务端的压力也不小
    • 需要在服务端做额外处理
  • HTTP长连接: 在长轮询的基础上, 服务端在返回数据后不再断开TCP连接

    • 相比长轮询能够更加有效节省带宽, 而且通信的实时性更高, 依然是需要维持大量HTTP连接
    • 需要在客户端和服务端都做额外处理, 兼容性较差
  • HTML5 SSE: 直接运行于HTTP服务之上的服务器推送方案, 优点时方便简单, 缺点和上面一样, 需要维持大量HTTP连接
  • HTML5 WebSocket: 相当于在应用层重新实现了一个全双工的通信协议, 能够从HTTP协议升级(101)而来

    • 如果客户端支持的话, 这是实现HTTP全双工通信的最优方案, WebSocket协议与HTTP协议独立, 那么就可以将两个服务器分别实现, 从而避免给HTTP服务器带来太大连接压力

Java WebSocket

Java在2013年就已经通过JSR356支持了WebSocket技术, 使用起来非常简单, 使用注解就可以.

从实际业务出发, 我实现了一个AbstractEndPoint的抽象接口类, 封装了如下功能:

  • 维护客户端在线列表
  • 基于AES128生成AccessKey并验证
  • 封装了简单的文本信息发送

客户端在线列表需要考虑, 一个账号可能存在多个同时在线的客户端, 那么如果需要向一个账号发送消息就需要向所有在线的客户端发送消息.
因为操作的都是static的集合类, 所以需要考虑线程安全问题, 这里应该是读多写少所以采用ReadWriteLock.

public abstract class AbstractEndPoint {
    // Encrypt Parameters
    private final static String ivParameters = "1234567890123456"; // CBC需要16位长的IV, 随意设置
    private final static long expiredTime = 1000 * 60; // 一分钟过期
    private final static String magicStr = "QAQ"; // 用于替换accessKey中的/以避免无法捕捉到连接, 随意设置注意不要冲突
    // Static Map and rwLock - WARNING: Thread Safe Problem
    protected static Map<String, List<AbstractEndPoint>> clientMap = new HashMap<String, List<AbstractEndPoint>>(); // 在线列表
    protected static Map<String, SecretKey> keyMap = new HashMap<String, SecretKey>(); // 密钥列表
    protected static ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock(); // 读写锁
    // object Parameter
    protected String accountId;
    protected Session session;

    /**
     * 向指定账户发送文本信息
     * - 会向所有在线的连接发送消息
     * - 可以在上层套一层Object2Json比如GSON从而实现Object发送
     * - 或者使用JSR356的Encoder&Decoder
     *
     * @return 状态码 -2: 发送失败, -1:此用户不在线, 0:发送成功
     */
    public static int sendMessage(String accountId, String content){
        int statusCode = -2;
        try{
            if(rwLock.readLock().tryLock() || rwLock.readLock().tryLock(100, TimeUnit.MILLISECONDS)){
                try{
                    List<CustomEndPoint> endPoints = clientMap.get(accountId);
                    if(endPoints != null && endPoints.size() > 0){
                        for(CustomEndPoint endPoint : endPoints){
                            if(endPoint.session.isOpen()){
                                endPoint.session.getBasicRemote().sendText(content);
                            }
                        }
                        statusCode = 0;
                    }else{
                        statusCode = -1;
                    }
                }finally{
                    rwLock.readLock().unlock();
                }
            }
        }catch(InterruptedException | IOException e){
            e.printStackTrace();
        }
        return statusCode;
    }

    /**
     * 检查连接的有效性
     * 有效性包括:
     * 1. 账户含有对应的密钥
     * 2. 能够使用密钥解密加密内容
     * 3. 加密内容包含帐户名和密钥创建时间
     * 4. 密钥未过期
     *
     * @param accountId 帐号id
     * @param accessKey 连接密钥
     */
    protected boolean checkAccessible(String accountId, String accessKey){
        // 尝试验证accessKey的有效性
        boolean allowAccess = false;
        try{
            if(rwLock.readLock().tryLock() || rwLock.readLock().tryLock(100, TimeUnit.MILLISECONDS)){
                try{
                    if(keyMap.get(accountId) != null){ // 密钥存在
                        // 尝试解密AccessKey
                        accessKey = accessKey.replaceAll(magicStr, "/");
                        String information = decrypt(accessKey, keyMap.get(accountId));

                        // 验证AccessKey内信息
                        int position = information.indexOf(accountId + "_");
                        if(position != -1){
                            String createdTime = information.substring(accountId.length() + 1);
                            if(System.currentTimeMillis() - Long.parseLong(createdTime) < expiredTime){
                                allowAccess = true;
                            }
                        }
                    }
                }finally{
                    rwLock.readLock().unlock();
                }
            }
        }catch(Exception e){
            e.printStackTrace();
            log.error("Authority Exception: " + e.getMessage());
        }
        return allowAccess;
    }

    /**
     * 更新在线列表, 清除使用过的密钥
     */
    protected void updateSession(String accountId){
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(100, TimeUnit.MILLISECONDS)){
                try{
                    List<CustomEndPoint> endpoints = clientMap.get(accountId) == null ? new ArrayList<CustomEndPoint>() : clientMap.get(accountId);
                    endpoints.add(this);
                    clientMap.put(accountId, endpoints); // 添加到在线列表
                    clearClosedSession(accountId); // 清除当前账户已关闭的连接
                    keyMap.remove(accountId); // 删除AccessKey
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }

    /**
     * 清除已经关闭的连接
     *
     * @param accountId 指定时只清除指定帐号的连接, 否则清除所有帐号的连接(注意可能的性能问题, 当在线用户很多时)
     */
    protected void clearClosedSession(String accountId){
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(100, TimeUnit.MILLISECONDS)){
                try{
                    // Init accountIds
                    List<String> accountIds = new ArrayList<>();
                    if(accountId != null){
                        accountIds.add(accountId);
                    }else{
                        accountIds.addAll(clientMap.keySet());
                    }

                    // Delete closed session
                    for(String id : accountIds){
                        if(clientMap.containsKey(id)){
                            Iterator<CustomEndPoint> iterator = clientMap.get(id).iterator();
                            while(iterator.hasNext()){
                                CustomEndPoint endpoint = iterator.next();
                                if(!endpoint.session.isOpen()){
                                    iterator.remove();
                                }
                            }
                            if(clientMap.get(id).size() == 0){
                                clientMap.remove(id);
                            }
                        }
                    }
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }

    /**
     * 创建连接用AccessKey - AES加密后的 帐户名_时间戳
     * 因为Encode后的字符串可能含有/导致URL解析错误, 所以用magicStr替换
     *
     * @param accountId 用户名
     * @return 连接用密钥
     */
    public static String createAccessKey(String accountId){
        SecretKey key = generateSecretKey();
        String accessKey = encrypt(accountId + "_" + System.currentTimeMillis(), key);
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(100, TimeUnit.MILLISECONDS)){
                try{
                    keyMap.put(accountId, key);
                    return accessKey.replaceAll("/", magicStr);
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Failed to generate access key. ");
    }

    /**
     * 加密文本 - AES-128-CBC
     * 使用AES256需要额外的设置, 避免麻烦采用AES128
     *
     * @param plainText 原文本
     * @param key       加密密钥
     * @return 加密后的文本
     */
    private static String encrypt(String plainText, SecretKey key){
        if(key == null || plainText == null || plainText.isEmpty()){
            throw new IllegalArgumentException();
        }

        try{
            Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
            cipher.init(Cipher.ENCRYPT_MODE, key, new IvParameterSpec(ivParameters.getBytes()));
            byte[] encryptedTestBytes = cipher.doFinal(plainText.getBytes(StandardCharsets.UTF_8));
            return DatatypeConverter.printBase64Binary(encryptedTestBytes);
        }catch(NoSuchAlgorithmException | NoSuchPaddingException | InvalidKeyException | InvalidAlgorithmParameterException |
                IllegalBlockSizeException | BadPaddingException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Cannot encrypt text. ");
    }

    /**
     * 解密文本 - AES-128-CBC
     *
     * @param encryptedText 被加密过的文字
     * @param key           AES密钥
     * @return 解密后的文本
     */
    private static String decrypt(String encryptedText, SecretKey key){
        if(key == null || encryptedText == null || encryptedText.isEmpty()){
            throw new IllegalArgumentException();
        }

        byte[] encryptedBytes = DatatypeConverter.parseBase64Binary(encryptedText);
        try{
            Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
            cipher.init(Cipher.DECRYPT_MODE, key, new IvParameterSpec(ivParameters.getBytes()));
            byte[] plainTextBytes = cipher.doFinal(encryptedBytes);
            return new String(plainTextBytes);
        }catch(NoSuchAlgorithmException | NoSuchPaddingException | BadPaddingException | InvalidKeyException |
                IllegalBlockSizeException | InvalidAlgorithmParameterException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Cannot decrypt text. ");
    }

    /**
     * 随机产生AES加密所需密钥 - 128bit
     */
    private static SecretKey generateSecretKey(){
        try{
            return KeyGenerator.getInstance("AES").generateKey();
        }catch(NoSuchAlgorithmException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Failed to generate secretKey. ");
    }
}

具体的EndPoint实现放在了子类中, 由于经过Nignx转发以后连接可能会超时, 这里采用了心跳机制保证连接不超时.
另外, 浏览器的页面跳转也可能导致连接断开, 这一部分的连接断开是正常的, 不需要记录warn日志, 浏览器如果主动放弃连接, 也是不需要记录warn日志的.
需要注意的是, 如果验证成功的话需要发送一个连接确认信息告知客户端验证通过, 否则客户端无法分辨逻辑上的连接是否建立成功.

@ServerEndpoint("/ws/{accountId}/{accessKey}")
public class MessageEndpoint extends AbstractEndPoint {
    @OnOpen
    public void onOpen(final Session session, @PathParam("accountId") String accountId, @PathParam("accessKey") String accessKey) throws IOException{
        boolean allowAccess = checkAccessible(accountId, accessKey);
        if(allowAccess){ // 允许连接
            this.accountId = accountId;
            this.session = session;
            updateSession(accountId); // 添加到在线列表
            session.getBasicRemote().sendText("ok"); // 发送连接确认信息
            log.info(String.format("Account %s #%d connected", accountId, clientMap.get(accountId).size()));
        }else{ // 验证失败
            CloseReason reason = new CloseReason(CloseReason.CloseCodes.CANNOT_ACCEPT, "Authority Failed");
            session.close(reason);
        }
    }

    @OnMessage
    public void onMessage(String txt) {
        if(!txt.equals("heartBeat")){
            log.debug("Received Msg: " + txt);
        }
    }

    @OnClose
    public void onClose(Session session, CloseReason closeReason) {
        clearClosedSession(accountId);
        if(closeReason.getCloseCode().equals(CloseReason.CloseCodes.GOING_AWAY)){ // 浏览器跳转页面导致的断开
            log.info("Account " + accountId + " disconnected due to SWITCH THE PAGE.");
        }else{
            log.warn("Account " + accountId + " disconnected due to " + closeReason.getReasonPhrase());
        }
    }

    @OnError
    public void onError(Session session, Throwable error) {
        clearClosedSession(accountId);
        if(!error.getMessage().contains("The client aborted the connection.")){ // 浏览器主动放弃连接不记录
            log.warn("Error communicating with Account " + accountId + ". Detail: " + error.getMessage());
        }
    }
}

在浏览器端就比较简单, 这里比较简单的维护了一下无权访问时以及WebSocket出错时的Fallback, 只有当客户端收到ok信息时才能认为连接成功:

function readMessage() {
    var url = "requestAccessKey";
    var wsBaseUrl = $('base').attr('href').replace('http', 'ws');
    var sessionStorage = window.sessionStorage;
    if(sessionStorage.getItem("NoPermission") != null){ // 没有权限的情况下不再请求
        return;
    }
    // 如果不支持Websocket或者连接出错超过10次则使用轮询方式
    if (!'WebSocket' in window || Number(sessionStorage.getItem("wsRetryCnt")) > 10) {
        $.get(url, function (data) {
            console.log(data);
        }).onload = function (evt) { // 无权访问时, 停止操作
            if (this.status === 403) {
                sessionStorage.setItem("NoPermission", "1");
            }
        }
    } else {
        if (null == ws_client) { // connection closed or hasn't established.
            var tmp = $.get(url, function (data) {
                ws_client = new WebSocket(wsBaseUrl + "ws/" + data.accountId + "/" + data.accessKey);
                ws_client.onopen = function (evt) {
                    console.log("Connecting...");
                };
                ws_client.onmessage = function (evt) {
                    if(evt.data === "ok"){
                        sessionStorage.setItem("wsRetryCnt", "0");
                        console.log("Connection Created.");
                    }else{
                        console.log(data);
                    }
                };
                ws_client.onclose = function (evt) {
                    ws_client = null;
                    var retryCnt = sessionStorage.getItem("wsRetryCnt") == null ? 1 : Number(sessionStorage.getItem("wsRetryCnt")) + 1;
                    sessionStorage.setItem("wsRetryCnt", String(retryCnt));
                    console.log("Connection Failed #"+ retryCnt + ".");
                }
            }).onload = function (evt) {  // 无权访问时, 停止操作
                if (this.status === 403) {
                    sessionStorage.setItem("NoPermission", "1");
                }
            }
        } else { // 如果已经有ws对象, 那么在这里维持心跳保证连接不断开
            if (ws_client.readyState === WebSocket.CLOSING || ws_client.readyState === WebSocket.CLOSED) { // 如果连接已断开则重新建立连接
                ws_client = null;
            } else {
                ws_client.send("heartBeat");
            }
        }
    }
}

简单总结

WebSocket作为最先进的服务端推送/客户端服务端双工通信技术的实现, 单纯实现起来其实很简单, JSR356等已经做了大量的底层实现.
但是如果要结合业务并同时考虑到安全性等问题的话, 就需要从即时通讯的角度来充分思考需要在其上需要额外附加的机制.

从本质上来说, WebSocket为HTTP协议提供了这样一种功能, 从一个简单的单向的文本协议升级为一个更为复杂的全双工二进制通信协议, 正如WebSokcet中Socket一词, 在使用上更像是向操作系统升级了一个Socket来进行操作.


Hibernate SQLQuery缓存问题分析


前情提要

系统的ORM框架是Hibernate4.1.9, Cache Provider是Ehcache, 设置CacheRegion后遭遇到缓存不失效问题.
比如说: 使用SQL语句查询一个表的数目是10000, 这时候删除掉了该表的一条记录, 那么再次使用同一条语句查询数目时应该重新去数据库查询得到结果为9999, 但是因为缓存没有失效, 所以查出来的还是10000.
但是, Hibernate从古老的3.1版本直到最新的5.3.9都有这个问题, 就很emmmm

原因分析

这个主要的原因是Hibernate在处理SQLQuery时, 没有正确设置querySpaces, 也就是本次查询关联的表名.
如果检测到查询的关联表已经被修改, 那么这个缓存应该立即失效, 由于没有设置querySpaces导致任意SQLQuery都不会被这个机制所影响.

通过Hibernate的查询最后会到org.hibernate.loader.Loader类下的listUsingQueryCache中, 这里会尝试中从Cache中获取数据, 如果Cache中存在数据就返回Cache中的数据:

private List listUsingQueryCache(
        final SessionImplementor session,
        final QueryParameters queryParameters,
        final Set querySpaces,
        final Type[] resultTypes) {

    QueryCache queryCache = factory.getQueryCache( queryParameters.getCacheRegion() );

    QueryKey key = generateQueryKey( session, queryParameters );

    if ( querySpaces == null || querySpaces.size() == 0 )
        LOG.tracev( "Unexpected querySpaces is {0}", ( querySpaces == null ? querySpaces : "empty" ) );
    else {
        LOG.tracev( "querySpaces is {0}", querySpaces );
    }

    List result = getResultFromQueryCache(
            session,
            queryParameters,
            querySpaces,
            resultTypes,
            queryCache,
            key
        );

    if ( result == null ) {
        result = doList( session, queryParameters, key.getResultTransformer() );

        putResultInQueryCache(
                session,
                queryParameters,
                resultTypes,
                queryCache,
                key,
                result
        );
    }
    // ...
}

跟踪getResultFromQueryCache方法, 会发现他最终是从org.hibernate.cache.internal.StandardQueryCacheget方法里获取的数据:

public List get(
        QueryKey key,
        Type[] returnTypes,
        boolean isNaturalKeyLookup,
        Set spaces,
        SessionImplementor session) throws HibernateException {
    LOG.debugf( "Checking cached query results in region: %s", cacheRegion.getName() );

    List cacheable = (List) cacheRegion.get( key );
    logCachedResultDetails( key, spaces, returnTypes, cacheable );

    if ( cacheable == null ) {
        LOG.debug( "Query results were not found in cache" );
        return null;
    }

    Long timestamp = (Long) cacheable.get( 0 );
    if ( !isNaturalKeyLookup && !isUpToDate( spaces, timestamp ) ) {
        LOG.debug( "Cached query results were not up-to-date" );
        return null;
    }
    // ...

这里会在isUpToDate方法里检测数据是否已经失效, 该方法的实现在org.hibernate.cache.spi.UpdateTimestampsCache:

public boolean isUpToDate(Set spaces, Long timestamp) throws HibernateException {
    final boolean debug = LOG.isDebugEnabled();
    final boolean stats = factory != null && factory.getStatistics().isStatisticsEnabled();

    for ( Serializable space : (Set<Serializable>) spaces ) {
        Long lastUpdate = (Long) region.get( space );
        if ( lastUpdate == null ) {
            if ( stats ) {
                factory.getStatisticsImplementor().updateTimestampsCacheMiss();
            }
            //the last update timestamp was lost from the cache
            //(or there were no updates since startup!)
            //updateTimestamps.put( space, new Long( updateTimestamps.nextTimestamp() ) );
            //result = false; // safer
        }
        else {
            if ( debug ) {
                LOG.debugf(
                        "[%s] last update timestamp: %s",
                        space,
                        lastUpdate + ", result set timestamp: " + timestamp
                );
            }
            if ( stats ) {
                factory.getStatisticsImplementor().updateTimestampsCacheHit();
            }
            if ( lastUpdate >= timestamp ) {
                return false;
            }
        }
    }
    return true;
}

如果发现上次的更新时间lastUpdate比缓存的时间timestamp更新则会更新缓存, 但是因为SQLQuery不会设置querySpaces, 所以根本连这个循环都进不去= =

关于querySpaces的值的设置, 根据跟踪主要是在org.hibernate.loader.custom.sql.SQLCustomQuery中设置的:

    public SQLCustomQuery(
            final String sqlQuery,
            final NativeSQLQueryReturn[] queryReturns,
            final Collection additionalQuerySpaces,
            final SessionFactoryImplementor factory) throws HibernateException {

        LOG.tracev( "Starting processing of sql query [{0}]", sqlQuery );
        SQLQueryReturnProcessor processor = new SQLQueryReturnProcessor(queryReturns, factory);
        SQLQueryReturnProcessor.ResultAliasContext aliasContext = processor.process();


//        Map[] propertyResultMaps =  (Map[]) processor.getPropertyResults().toArray( new Map[0] );
//        Map[] collectionResultMaps =  (Map[]) processor.getCollectionPropertyResults().toArray( new Map[0] );
//
//        List collectionSuffixes = new ArrayList();
//        List collectionOwnerAliases = processor.getCollectionOwnerAliases();
//        List collectionPersisters = processor.getCollectionPersisters();
//        int size = collectionPersisters.size();
//        if (size!=0) {
//            collectionOwners = new int[size];
//            collectionRoles = new String[size];
//            //collectionDescriptors = new CollectionAliases[size];
//            for ( int i=0; i<size; i++ ) {
//                CollectionPersister collectionPersister = (CollectionPersister) collectionPersisters.get(i);
//                collectionRoles[i] = ( collectionPersister ).getRole();
//                collectionOwners[i] = processor.getAliases().indexOf( collectionOwnerAliases.get(i) );
//                String suffix = i + "__";
//                collectionSuffixes.add(suffix);
//                //collectionDescriptors[i] = new GeneratedCollectionAliases( collectionResultMaps[i], collectionPersister, suffix );
//            }
//        }
//        else {
//            collectionRoles = null;
//            //collectionDescriptors = null;
//            collectionOwners = null;
//        }
//
//        String[] aliases = ArrayHelper.toStringArray( processor.getAliases() );
//        String[] collAliases = ArrayHelper.toStringArray( processor.getCollectionAliases() );
//        String[] collSuffixes = ArrayHelper.toStringArray(collectionSuffixes);
//
//        SQLLoadable[] entityPersisters = (SQLLoadable[]) processor.getPersisters().toArray( new SQLLoadable[0] );
//        SQLLoadableCollection[] collPersisters = (SQLLoadableCollection[]) collectionPersisters.toArray( new SQLLoadableCollection[0] );
//        lockModes = (LockMode[]) processor.getLockModes().toArray( new LockMode[0] );
//
//        scalarColumnAliases = ArrayHelper.toStringArray( processor.getScalarColumnAliases() );
//        scalarTypes = ArrayHelper.toTypeArray( processor.getScalarTypes() );
//
//        // need to match the "sequence" of what we return. scalar first, entity last.
//        returnAliases = ArrayHelper.join(scalarColumnAliases, aliases);
//
//        String[] suffixes = BasicLoader.generateSuffixes(entityPersisters.length);

        SQLQueryParser parser = new SQLQueryParser( sqlQuery, new ParserContext( aliasContext ), factory );
        this.sql = parser.process();
        this.namedParameterBindPoints.putAll( parser.getNamedParameters() );

//        SQLQueryParser parser = new SQLQueryParser(
//                sqlQuery,
//                processor.getAlias2Persister(),
//                processor.getAlias2Return(),
//                aliases,
//                collAliases,
//                collPersisters,
//                suffixes,
//                collSuffixes
//        );
//
//        sql = parser.process();
//
//        namedParameterBindPoints = parser.getNamedParameters();


        customQueryReturns.addAll( processor.generateCustomReturns( parser.queryHasAliases() ) );

//        // Populate entityNames, entityDescrptors and querySpaces
//        entityNames = new String[entityPersisters.length];
//        entityDescriptors = new EntityAliases[entityPersisters.length];
//        for (int i = 0; i < entityPersisters.length; i++) {
//            SQLLoadable persister = entityPersisters[i];
//            //alias2Persister.put( aliases[i], persister );
//            //TODO: Does not consider any other tables referenced in the query
//            ArrayHelper.addAll( querySpaces, persister.getQuerySpaces() );
//            entityNames[i] = persister.getEntityName();
//            if ( parser.queryHasAliases() ) {
//                entityDescriptors[i] = new DefaultEntityAliases(
//                        propertyResultMaps[i],
//                        entityPersisters[i],
//                        suffixes[i]
//                    );
//            }
//            else {
//                entityDescriptors[i] = new ColumnEntityAliases(
//                        propertyResultMaps[i],
//                        entityPersisters[i],
//                        suffixes[i]
//                    );
//            }
//        }
        if ( additionalQuerySpaces != null ) {
            querySpaces.addAll( additionalQuerySpaces );
        }

//        if (size!=0) {
//            collectionDescriptors = new CollectionAliases[size];
//            for ( int i=0; i<size; i++ ) {
//                CollectionPersister collectionPersister = (CollectionPersister) collectionPersisters.get(i);
//                String suffix = i + "__";
//                if( parser.queryHasAliases() ) {
//                    collectionDescriptors[i] = new GeneratedCollectionAliases( collectionResultMaps[i], collectionPersister, suffix );
//                } else {
//                    collectionDescriptors[i] = new ColumnCollectionAliases( collectionResultMaps[i], (SQLLoadableCollection) collectionPersister );
//                }
//            }
//        }
//        else {
//            collectionDescriptors = null;
//        }
//
//
//        // Resolve owners
//        Map alias2OwnerAlias = processor.getAlias2OwnerAlias();
//        int[] ownersArray = new int[entityPersisters.length];
//        for ( int j=0; j < aliases.length; j++ ) {
//            String ownerAlias = (String) alias2OwnerAlias.get( aliases[j] );
//            if ( StringHelper.isNotEmpty(ownerAlias) ) {
//                ownersArray[j] =  processor.getAliases().indexOf( ownerAlias );
//            }
//            else {
//                ownersArray[j] = -1;
//            }
//        }
//        if ( ArrayHelper.isAllNegative(ownersArray) ) {
//            ownersArray = null;
//        }
//        this.entityOwners = ownersArray;

    }

可以看到这个构造函数的代码很长, 但大部分都被注释掉了, 和querySpaces有关的只有这一句querySpaces.addAll( additionalQuerySpaces );.
这里的additionalQuerySpaces是在建立查询时放入的一个参数, 可以手动指定querySpaces, 如果没有手动指定, 那么这里也是空的, 因此查询进行到Loader层的时候也会是空的.
可以看到这个方法中注释掉了大量代码, 其中也包括处理querySpaces的部分, 可能是原来写的有问题, 所以作者干脆注释掉算了= =
然后...直到最新版本, 也再也没有人动过这里的代码= =
所以说, 开源有好的地方, 但是也是有不好的地方的_(:3」∠)_

既然已经知道了问题, 那么有两种解决问题的思路:

  1. 重写SQLCustomQuery类, 将这里对querySpaces手动实现上去, 未来也许还可以提交一个PR

    • 这种方式的问题是, 单独对框架进行修改不利于日后的升级, 未来接手维护的人可能不太清楚你都改了那些内容, 会不会对业务有影响, 因此不敢轻易升级
  2. 不用Hibernate提供的缓存, 而是根据业务需要在Hibernate外手动建立一个针对业务的查询缓存

    • 这种方式感觉就是很不优雅= =

解决方法

业务层缓存

基本思路是实现一个单例, 然后使用ReadWriteLock对读写进行加锁以保证线程安全, 单例采用DCL实现:

public class CountCache{
    private volatile static CountCache instance;
    private Map<String, Long> cache = new HashMap<>();
    private Map<String, Long> cacheTime = new HashMap<>();

    // 加读写锁保证线程安全
    private ReadWriteLock rwLock = new ReentrantReadWriteLock();

    // 超时时间设置, 单位为秒
    private final static int timeout = 1800;

    // 防止直接创建实例
    private CountCache(){}

    /**
     * DCL形式的单例
     */
    public static CountCache getInstance(){
        if(instance == null){
            synchronized(CountCache.class){
                if(instance == null){
                    instance = new CountCache();
                }
            }
        }
        return instance;
    }

    /**
     * 读缓存内容, 如果写入时间超时, 则缓存无效
     */
    public long readCache(String key){
        try{
            if(rwLock.readLock().tryLock() || rwLock.readLock().tryLock(1, TimeUnit.SECONDS)){
                try{
                    if(cacheTime.containsKey(key)){
                        long interval = System.currentTimeMillis() - cacheTime.get(key);
                        // if timeout
                        if(interval / 1000 > timeout){
                            invalidateCache(key);
                            return -1;
                        }
                        // read cache
                        return cache.get(key);
                    }
                }finally{
                    rwLock.readLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
        return -1;
    }

    /**
     * 写缓存内容, 记录写入时间
     */
    public void writeCache(String key, long value){
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(1, TimeUnit.SECONDS)){
                try{
                    cache.put(key, value);
                    cacheTime.put(key, System.currentTimeMillis());
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }

    /**
     * 将缓存失效
     */
    public void invalidateCache(String key){
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(1, TimeUnit.SECONDS)){
                try{
                    cache.remove(key);
                    cacheTime.remove(key);
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }
}

魔改SQLCustomQuery

有没有什么办法在不修改Hibernate的Jar包的前提下实现对SQLCustomQuery类的替换呢?
能不能在运行时, 卸载掉原来的SQLCustomQuery类然后加载我们自定义的SQLCustomQuery类, 让我们自定义的类替换掉原有的实现?

替换原有类

经过调研, 替换原有类主要有两种思路:

  1. 自定义一个自己的类加载器, 然后越早越好, 使用这个自定义的类加载器来加载所有的类, 而不是Tomcat自带的WebappClassLoader, 这样整个WEB应用都会使用我们自定义的类加载器了, 这样在我们的类加载器对单独几个特殊的类来做特殊的加载就很容易

    • 理论基础是: 一个类会用它自己的类加载器来加载它所new的对象, 所以只要在很早的时候加载一个启动类, 那么由这个类派生出来的所有类都会使用我们的类加载器了
    • 实现上的话, 我们可以定一个黑名单, 在黑名单里的类不委托WebappClassLoader加载, 而是我们自己加载, 而正常的类都交给WebappClassLoader来加载, 使用正常的双亲委托机制
    • 但是, 很难找到一个那么早的时机来使用自己的类加载器, 要是需要修改Tomcat源码的话...还不如直接修改Hibernate源码了
  2. 使用Instrument机制, 这样需要在Java虚拟机启动的时候带一个Agent, 在Agent里面我们要对JVM虚拟机做一些操作就很容易, 替换一个类更是可行的

    • 比如说, IDEA就会在启动程序的时候带上-javaagent:C:\App\JetBrains\apps\IDEA-U\ch-0\183.5912.21\lib\idea_rt.jar=5451:C:\App\JetBrains\apps\IDEA-U\ch-0\183.5912.21\bin参数
    • 但是, 这样操作的话需要修改Tomcat的Boostrap脚本, 协调起来比较麻烦...还不如直接修改Hibernate源码了

更加简单的方法

经过测试, 其实根本没必要进行上述那么复杂的操作, Tomcat会优先加载WEB-INF/classes中的类然后才去加载WEB-INF/libs下的类, 因此我们只要在自己的应用里实现一个同名的类就可以了.
这样, Tomcat会优先加载我们应用中的类, 而忽略掉Jar包中的类的加载.

修改后的SQLCustomQuery如下:

public class SQLCustomQuery implements CustomQuery{
    // 缓存数据库中的所有表名
    private static Set<String> allUserTables;

    public SQLCustomQuery(
            final String sqlQuery,
            final NativeSQLQueryReturn[] queryReturns,
            final Collection additionalQuerySpaces,
            final SessionFactoryImplementor factory) throws HibernateException{

        // 省略SQLCustomQuery原有代码

        // 一个简单的提取SQL所查询的表的思路是, 因为我们的业务表拥有固定的前缀
        // 那么只需要按空格分开所有Token, 然后只保留固定前缀开头的单词最后去重即可, 但是有极低的可能性误判
        // 更加靠谱的思路的是, 我们去获取我们所有表的列表, 所以只取已知表的单词就是所查询的表
        // 考虑到第一种和第二种方法实现起来难度差不多, 所以干脆实现第二种了
        LOG.infov("Loaded Custom SQLCustomQuery of SQL Query [{0}]", sql);

        // 初始化或更新所有表的列表
        try{
            // 初次使用需要初始化
            if(allUserTables == null){
                allUserTables = queryUserTables();
            }
            // 如果谁想不开在代码修改表结构的话, 更新缓存的表名
            String lowerSQL = sql.toLowerCase();
            if(lowerSQL.contains("table") && (lowerSQL.contains("create") || lowerSQL.contains("drop"))){
                allUserTables = queryUserTables();
                LOG.warnv("Create/Drop Table! Query: [{0}]", sql);
            }
        }catch(NamingException | SQLException e){
            e.printStackTrace();
        }

        // 提取SQL查询中的所有Token, 并记录包含表名的Token
        String[] sqlTokens = sql.split("  *");
        for(String token : sqlTokens){
            if(allUserTables.contains(token)){
                querySpaces.add(token);
            }
        }
    }

    /**
     * 这里采用JDBC直接查询数据库所有表名
     */
    private Set<String> queryUserTables() throws NamingException, SQLException{
        Context ctx = new InitialContext();
        String dbName = ApplicationContainer.sc.getAttribute("dataSource").toString().toLowerCase();
        DataSource ds = (DataSource)ctx.lookup("java:comp/env/" + dbName);

        Connection conn = null;
        Set<String> result = new HashSet<>();
        try{
            conn = ds.getConnection();
            Statement st = conn.createStatement();
            ResultSet rs = st.executeQuery("select table_name from user_tables"); // Oracle 数据库
            while(rs.next()){
                result.add(rs.getString(1));
            }
        }finally{
            if(conn != null && !conn.isClosed()){
                conn.close();
            }
        }

        return result;
    }

一个简单获取所关联的表名思路就是先获取所有的表名, 然后看每一个SQL中的Token是否是表名, 如果是则添加到querySpaces中.
如果真的要去解析SQL, 建立AST语法树的话, 那就太麻烦了_(:3」∠)_
直接正则表达式的话, 因为很难预料业务代码会写出什么样的SQL, 所以并不是特别靠谱.

直接采用JDBC查询的原因是, 这样的操作比较快, 而且只查询一次, 且在框架内部操作并不适合再通过Hibernate去查询.

由于allUserTables被重复设置也没什么问题, 所以不太需要考虑线程安全问题.

当然, 根据我们的实际业务需要, 这样来处理querySpaces没有太大问题, 但是如果作为框架内部代码显然不能这么实现, 到时候还是需要解析SQL, 处理AST然后获得相关联的表. 等我什么时候学了编译原理, 这里还没有人改我就写一个然后提个PR吧233

简单总结

没什么想说的_(:3」∠)_ 辣鸡Hibernate(x

数据库范式简明解释


总的来说, 数据库范式就是逐渐消除数据冗余的过程.

1NF: 字段不可分

  • 属性的原子性约束
  • 一个数据库中字段不能包含多个可分的字段

    • 比如说不能把手机和邮箱记录在同一个字段中
    • 同理, 把多个手机记录在同一个字段中也是不合适的

2NF: 非主键字段完全依赖于主键 (消除部分子函数依赖)

  • 记录的惟一性约束
  • 消除了主键组合字段之间的依赖
  • 反例: 两个独立的组合主键 (K1, K2) -> (V1, V2) | (K1) -> (V1), (K2) -> (V2), (K1) -> (K2)

    • 修改为: (K1) -> (V1), (K2) -> (V2), (K1) -> (K2)

3NF: 非主键字段不依赖于其它非主键字段 (消除传递依赖)

  • 字段冗余性的约束
  • 消除了非主键字段之间的依赖
  • 不存在非主键字段对任一候选主键的传递函数依赖
  • 数据冗余: V1依赖于V2, 导致多个重复V1时, V2也发生重复 (K1) -> (V1, V2) | (V1) -> (V2)

    • 修改为: (K1) -> (V1), (V1) -> (V2)

BCNF: 任何字段不依赖于其他字段 (消除传递依赖)

  • 字段冗余性的约束
  • 消除了所有字段之间的依赖(
  • 不存在任何字段对任一候选主键的传递函数依赖
  • 主键依赖主键: (K1, K2) -> (V1) | (K1) -> (K2)

    • 修改为: (K1) -> (V1), (K1) -> (K2)
  • 与3NF的主要区别是: 3NF只考虑了非主键字段之间的依赖, 而没有考虑主键组合字段之间的依赖, BCNF是一种更严格的3NF

算法和数据结构总结大纲


时间复杂度

基本原则

一些容易混淆的时间复杂度分析

常数优化

  1. IO优化(快速读写)
  2. 避免浮点数, 尽量只处理整数
  3. 快速乘法, 通过对乘数拆解做移位
  4. 避免除法, 2的整数次幂除法可以用移位代替
  5. 避免取模, 快速取模方法

基本思想

递归

主要可以分为如下三种:

  • 尾部递归, 就是循环, 不支持循环的语言会有尾递归优化
  • 中间递归, 可以用一个栈模拟栈帧来将其转为循环, 比如阶乘的递归实现
  • 树状递归, 这个就比较复杂了, 最好是从需求上将其转为循环, 比如斐波拉契数列的递归实现

分治

前提: 如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解, 并可利用这些子问题的解求出原问题的解

流程:

  • 分解: 将一个问题分成多个类似的子问题(中间递归或者树状递归都可以)
  • 解决: 简单子问题可以直接求解
  • 合并: 将子问题的解合并成原问题的解

状态和状态转移方程:

  • 状态: 你要求解的子问题
  • 状态转移方程: 如何将子问题合并

例子:

  • 二分查找
  • 快速排序
  • 归并排序
  • MapReduce

贪心

前提:

  • 局部最优解可以合成为全局最优解
  • 某个状态以前的过程不会影响以后的状态, 只与当前状态有关(无后效性)

流程:

  • 分解: 将一个问题分解成线性的多个子问题(中间递归)
  • 解决: 对每一个线性子问题求局部最优解
  • 合并: 将子问题的局部最优解合并成全局最优解
可以视作为分治的一种特殊情况, 问题可以被分解链式的单个问题, 最后合并的时候是线性合并

动态规划

前提: 将原问题分解成为子问题后, 存在重叠子问题

可以视作为分治的一种特殊情况, 同样要求问题可以被分解为链式的单个问题, 只不过由于分解之后的子问题可能重复, 所以保存每一个子问题的最优解, 这个最优解可能在不同的状态下会被更新.
通常容易用递推实现

离散化

只考虑需要的值, 而不用考虑整个值域

基本数据结构

  • 逻辑结构: 集合/线性结构/树形结构/图形结构
  • 存储结构: 顺序存储/链式存储/索引存储/Hash存储

线性表

  • 数组/链表
  • 队列/栈

图论

存储方式

  • 邻接表
  • 邻接矩阵

基础算法

搜索和遍历
  • BFS
  • DFS
最短路算法

松弛操作: 更新两点距离

Dijkstra
  • 单源最短路
  • 要求: 非负权边
  • 适合稠密图, 邻接表
  • 思路: 贪心 O(N^2)

    • 分为已处理集合P和未处理集合Q
    • 每一步从Q中选择距离源点s最近的点u, 更新源点s到点u所有近邻的距离
SPFA(Bellman-Ford)
  • 稀疏图/负权边
  • 思路: 基于BFS O(kN)

    • 源点s入队列
    • 出队列节点u, 如果可以松弛, 节点u的所有近邻入队列
Floyd
  • 多源最短路
  • 思路: 动态规划

    • 假设>$D_k(i, j)$<表示从i到j的最短路径, 且只经过>$[1, k]$<的节点

      • 若经过k点, 那么>$D_k(i, j) = D_{k-1}(i, k) + D_{k-1}(k, j)$<
      • 若不经过k点, 那么>$D_k(i, j) = D_{k-1}(i, j)$<
      • 因此: >$D_k(i, j) = \min{D_{k-1}(i, j), D_{k-1}(i, k) + D_{k-1}(k, j)}$<
for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            d[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
最小生成树
Prim
  • 思路: 贪心 O(N^2)

    • 往集合V加入起始点s
    • 找到一端在V中另一端不在V中且权值最小的边
    • 记录这条边, 并把节点添加到V中
    • 直到所有节点都加入V
Kruskal
  • 思路: 并查集 O(NlogN)

    • 对所有边排序
    • 考虑每一条边的两个端点是否在同一并查集中
    • 如果不联通则合并两个并查集
    • 直到所有边都被检查, 或者所有节点都在同一个集合中(记录所有节点数做一次合并就减去一)
拓扑排序

并查集

  • 集合存在代表元素, 但不关心具体是哪一个元素
  • 常用操作

    • 快速找到代表元素/合并两个集合
  • 实现

    • 树和路径压缩

前缀和

  • 定义: 数组前N项的和: >$S[N]=a[1]+a[2]+\cdots+a[N]$<
  • 用途:

    • 快速得到区间和: >$S[M, N] = S[N] - S[M-1]$<
    • 区间快速运算: 对>$[M, N]$<加上k

      • 构造辅助数组aux[i], 表示>$[i, len(a)]$<区别的变化值

        • 拆分成: >$[M, len(a)]$<加上k, >$[N+1, len(a)]$<减去k
        • aux[M] = k, aux[N+1] = -k
        • 求aux的前缀和即可知道每个位置的变化量