1.BoltDB源码解析（七）Put和Delete操作
2.HashMap实现原理一步一步分析(1-put方法源码整体过程)
3.记一次源码追踪分析，从Java到JNI，再到JVM的C++：fileChannel.map()为什么快；源码分析map方法，put方法

BoltDB源码解析（七）Put和Delete操作

       Put和Delete的实现

       上一篇文章我们了解了BoltDB的Get API的实现。现在，我们来探讨Put和Delete API的php源码网模版实现：

       Put API的主要功能是将一对键值对插入到Bucket中，如果键已经存在，则更新对应的值。首先，进行一些限制条件的检查，例如Put操作是否由写事务发起的，因为Put只能由写事务调用。此外，还需要检查键和值的大小是否符合限制条件。需要注意的是，Put操作和Get操作一样，这里也使用了Cursor来定位键应该放置的位置。

       在实际的Put操作中，会调用Cursor的一个不显眼的方法：

       这个方法实际上非常有用，它从当前Bucket的B-tree的根节点开始，一直到Cursor定位到的leaf page，为每个page创建一个对应的node结构。当然，如果一个page已经有对应的node，就直接使用它。

       为什么要这么做呢？这是因为事务篇中提到的修改操作具有“传染性”，修改B-tree的leaf节点会导致从root到leaf的所有page都需要修改，而BoltDB的修改操作都是在page对应的node里进行的，不是直接在page上修改，因此需要为这些page建立node结构。具体建立node结构的是Bucket的node方法：

       Bucket的node方法有两处需要注意，一个是新建的node会被追加到parent node的children中，记录下这些修改的node之间的关系，这个children在node持久化时会有用(node.spill方法)。另一个是现金网源码求购node的数据是如何从page中读取的，这是由node的read方法完成的。

       node建立好之后，就在要修改的leaf对应的node上调用put方法：

       node的put方法相对简单，它是在inodes数组上查找对应的位置，如果exact为true，表示找到了相同的key，直接更新value；如果exact为false，相当于找到了应该插入的位置，然后在对应的inode上记录数据。我们来看一下inodes数组的定义：

       inodes数组是node实际存储数据的地方，由多个inode组成，每个不同的key对应一个不同的inode，inode之间是按key排序的。对于leaf节点来说，inode里使用key和value；对于branch节点来说，inode里使用key和pgid，pgid代表一个child page的id。value和pgid不会同时使用。

       put方法结束后，当前的Put操作也就结束了。也就是说，Put操作所做的仅仅是把新增或修改的数据放入到它所在的page对应的node内存中。

       顺便提一下Delete操作，它和Put操作非常类似，在建立起node结构之后，在对应的node的inodes数组中删除找到的key相等的inode就完成了，这里不再展开。

       那么，什么时候会把这些node里的数据持久化到DB文件里呢？是在整个写事务commit的时候。

       事务的Commit实现

       下面是事务commit的代码简化，保留了重要部分：

       Commit的整体流程比较长，下面一点一点进行说明。

       tx.root.rebalance()，这个root是源码最全的网站root Bucket，rebalance是对root Bucket下所有子Bucket的所有node进行rebalance。这是什么意思？注意node的初始数据虽然来自一个page，但在经历了一些Delete操作后，有些node里面的数据可能过少，这时会先把这个node和它的左兄弟或右兄弟node合并(node的rebalance方法)，合并后node数会减少，但不存在node里数据过少的情况。这个操作对应于B-tree的merge操作，只不过这些node都是Go的内存结构，合并起来非常简单。当然，合并后把这些node spill到page的操作，需要的page总数也会减少。

       tx.root.spill()，这个方法是把root Bucket下所有子Bucket的所有node的内容都写入这个事务分配的dirty page里。注意这些dirty page是这个事务临时分配在内存里的，结构和DB文件的page完全一样，但还不是mmap映射的DB的page。

       刚开始看到spill这个方法时，感觉它代价有些高，感觉像是把整个B-tree都走了一遍。后来仔细看才发现不是这么回事。这个spill只对有node结构的节点进行处理，那些没修改过的page没有对应的node，根本不会处理。

       注意在经过多次Put操作后，node里存放的数据可能出现一个page写不下的情况，比如insert了几千个key value。spill会先把这样的node split成多个大小合适的node(node的split方法)，然后把这些node分别写入不同的page中。这个操作对应于B-tree的split操作。和rebalance方法类似的道理，因为这些node都是Go的内存结构，split起来非常容易。短轰炸模板源码

       if tx.meta.pgid > opgid，这个判断是看当前事务需要的page数是否大于事务执行前DB文件有的page数，如果大于，说明DB文件放不下了，就调用db.grow增大文件，以容纳新增的page。

       紧接着是freelist的持久化操作，因为写事务可能使用了freelist里的一些page，同时也可能释放了一些page到freelist里，所以freelist很可能发生了变化，需要持久化。

       tx.write()，这个方法就是把所有的临时分配的dirty page都写入DB文件对应的page里。

       tx.writeMeta()，这个方法是把这个tx里的meta写到meta0或者meta1里面（写事务会交替写这两个meta page，这也是个常用技术，叫ping-pong buffer）。它的代码值得看一下：

       首先把meta写到临时分配的buf里，然后用文件IO写到DB文件里，最后调用fdatasync，把OS文件的buffer cache持久化到磁盘上。至此，写事务的所有数据都已经落盘完毕。后面新开启的事务会因为这个meta的txid是最大的，而选择使用这个最新的meta page。而这个meta page包括最新的root bucket，最新的freelist，最新的pgid，这些总体构成了一个DB的最新版本，保证新开启的事务读到最新版本的数据。

       看tx.write()和tx.writeMeta()的实现可以发现，写入数据用的是db.ops.writeAt，而这个方法默认值就是File.WriteAt方法，所以实际写入文件用的从源码构建项目是文件IO，而不是直接写mmap内存。而BoltDB使用mmap一开始就把mmap映射的内存标记为只读的，压根不允许直接写mmap内存。为什么要这么做呢？

       猜测可能是为了安全。前面讲到Get操作为了性能是zero copy的，发现Get返回来的value是mmap上数据的指针，如果mmap设置为可读写的，应用程序代码五花八门，可能会通过指针一不小心修改了mmap上的数据，这样的修改因为走的不是API是无法保证事务的。把mmap设置为只读的消除了这种可能性。反过来说，如果mmap设置为可读写的，Get就不能返回mmap上的指针了，为了安全一定要copy一份数据出来才行，降低了Get的性能。

       这里还有个很自然而且很重要的问题是，如果事务commit失败了呢，BoltDB如何保证事务的原子性（ACID的A），确保这个写事务的所有操作，不论是落盘的，还是没落盘的，都不会生效？

       原子性要求，不管是commit走到哪一步，哪怕是已经把修改的数据，甚至包括修改的freelist已经落盘，只要最终事务commit失败，都不能对正确性产生任何影响。这里的正确性是指，数据库的状态（有实际的key value数据，freelist， pgid等共同构成）必须是在这个写事务运行之前的状态，数据不能被破坏，这个写事务也不能留下可被后续事务读到的任何更新。

       要做到原子性貌似挺难的，因为事务的commit里包括很多步骤，这些步骤都不是原子性的。不过重要的一点是，不论commit运行到哪一步，因为tx.writeMeta是最后一步，只有这一步运行成功commit才算成功，如果说commit失败了，那么tx.writeMeta一定是没运行，或者运行了半截，这个meta page没写完整，机器断电了。总之，这些情况下我们不会得到一个合法的新的meta page(这种情况下meta的validate方法会失败，因为meta的checksum不对)。这时候ping-pong buffer的meta page就起重要的作用了，因为交替写meta page的原因，即使这个写事务新的meta page没写成功，这个写事务运行前版本的meta page还在，而这个meta page包括这个写事务运行前的DB版本所有的状态（kv数据，freelist，pgid等）。这个meta page会被后续事务使用，就像那个失败的写事务从来没有运行过一样。而那个写事务留下的kv数据的page，freelist的page，即使是持久化了，也因为没有写成新的meta，没有机会被用到。

       还有个自然的疑问，即使这个失败的写事务写的page因为没有合法的meta无法被引用，不会影响正确性，但无法被引用是不是也意味着这些page无法被回收，浪费了磁盘空间？

       答案是也不会。在原来版本的meta里的free list和pgid的共同作用下，这些page会被视为free的，还可以使用，不会出现无法回收这些page的情况。

       还有个疑问，既然BoltDB交替写meta0和meta1，是不是连续两个事务commit正好在写meta时失败，数据库就废了？

       仔细研究发现，还是没事！因为写事务的txid也是meta的一部分，一个写事务失败，导致txid不会增长，下一次写事务的txid还是一样，meta的交替写是因为txid的变化引起的，既然没变化，就不交替了。所以下一个写事务即使写meta还失败了，也还是写的上一个写事务写的那个meta，不会把两个meta都写坏。

       总结一下，ping-pong buffer的meta page真是设计得精巧，是BoltDB达到原子性的关键！

HashMap实现原理一步一步分析(1-put方法源码整体过程)

       本文分享了HashMap内部的实现原理，重点解析了哈希(hash)、散列表(hash table)、哈希码(hashcode)以及hashCode()方法等基本概念。

       哈希(hash)是将任意长度的输入通过散列算法转换为固定长度输出的过程，建立一一对应关系。常见算法包括MD5加密和ASCII码表。

       散列表(hash table)是一种数据结构，通过关键码值映射到表中特定位置进行快速访问。

       哈希码(hashcode)是散列表中对象的存储位置标识，用于查找效率。

       Object类中的hashCode()方法用于获取对象的哈希码值，以在散列存储结构中确定对象存储地址。

       在存储字母时，使用哈希码值对数组大小取模以适应存储范围，防止哈希碰撞。

       HashMap在JDK1.7中使用数组+链表结构，而JDK1.8引入了红黑树以优化性能。

       HashMap内部数据结构包含数组和Entry对象，数组用于存储Entry对象，Entry对象用于存储键值对。

       在put方法中，首先判断数组是否为空并初始化，然后计算键的哈希码值对数组长度取模，用于定位存储位置。如果发生哈希碰撞，使用链表解决。

       本文详细介绍了HashMap的存储机制，包括数组+链表的实现方式，以及如何处理哈希碰撞。后续文章将继续深入探讨HashMap的其他特性，如数组长度的优化、多线程环境下的性能优化和红黑树的引入。

记一次源码追踪分析，从Java到JNI，再到JVM的C++：fileChannel.map()为什么快；源码分析map方法，put方法

       前言

       在系统IO相关的系统调用有read/write，mmap，sendfile等这些。

       其中read/write是普通的读写，每次都需要将buffer从用户空间拷贝到内核空间；

       而mmap使用的是内存映射，会将磁盘文件对应的页映射（拷贝）到内核空间的page cache，并记录到用户进程的页表中，使得用户空间也可以像操作用户空间一样操作该文件的映射，最后再由操作系统来讲该映射（脏页）回写到磁盘；

       sendfile则使用的是零拷贝技术，在mmap的基础上，当发送数据的时候只拷贝fd和offset等元数据信息，而将数据主体直接拷贝至protocol buffer，实现了内核数据零冗余的零拷贝技术

       本文地址：/post//

问题/目的问题1Java中哪些API使用到了mmap问题2怎么知道该API使用到了mmap，如何追踪程序的系统调用目的1源码中分析验证，从Java到JNI，再到C++：fileChannel.map()使用的是系统调用mmap目的2源码验证分析：调用mmapedByteBuffer.put(Byte[])时JVM在搞些什么？mmap比普通的read/write快在哪？揭晓答案1mmap在Java NIO中的体现/使用

       看一个例子

// 1GBpublic static final int _GB = 1**;File file = new File("filename");FileChannel fileChannel = new RandomAccessFile(file, "rw").getChannel();MappedByteBuffer mmapedByteBuffer = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, _GB);for (int i = 0; i < _GB; i++) { count++;mmapedByteBuffer.put((byte)0);}

       其中fileChannel.map()底层使用的就是系统调用mmap，函数签名为： public abstract MappedByteBuffer map(MapMode mode,long position, long size)throws IOException

答案2程序执行的系统调用追踪/** * @author Tptogiar * @description * @date /5/ - : */public class TestMappedByteBuffer{ public static final int _4kb = 4*;public static final int _GB= 1**;public static void main(String[] args) throws IOException, InterruptedException { // 为了方便在日志中找到本段代码的开始位置和结束位置，这里利用文件io来打开始标记FileInputStream startInput = null;try { startInput = new FileInputStream("start1.txt");startInput.read();} catch (IOException e) { e.printStackTrace();}File file = new File("filename");FileChannel fileChannel = new RandomAccessFile(file, "rw").getChannel();MappedByteBuffer map = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, _GB); //我们想分析的语句问题2for (int i = 0; i < _GB; i++) { map.put((byte)0); // 下文中需要分析的语句目的2}// 打结束标记FileInputStream endInput = null;try { endInput = new FileInputStream("end.txt");endInput.read();} catch (IOException e) { e.printStackTrace();}}}

       把上面这段代码编译后把“.class”文件拉到linux执行，并用linux上的strace工具记录其系统调用日志，拿到日志文件我们可以在日志中看到以下信息（关于怎么拿到日志可以参照我的博文：无（代写））：

       注：日志有多行，这里只选取我们关注的

// ...// 看到了我们打的开始标志openat(AT_FDCWD, "start1.txt", O_RDONLY) = -1 ENOENT (No such file or directory)// ... // 打开文件，文件描述符fd为6openat(AT_FDCWD, "filename", O_RDWR|O_CREAT, ) = 6// 判断文件状态fstat(6, { st_mode=S_IFREG|, st_size=, ...}) = 0// ... // 判断文件状态fstat(6, { st_mode=S_IFREG|, st_size=, ...}) = 0// 进行内存映射mmap(NULL, , PROT_READ|PROT_WRITE, MAP_SHARED, 6, 0) = 0x7f2fd6cd// ...// 程序退出exit(0)// 看到了我们打的结束标志openat(AT_FDCWD, "end.txt", O_RDONLY) = -1 ENOENT (No such file or directory)

       在上面程序的系统调用日志中我们确实看到了我们打的开始标志，结束标志。在开始标志和结束标志之间我们看到了我们的文件"filename"确实被打开了，文件描述符fd = 6；在打开文件后紧接着又执行了系统调用mmap，这一点我们Java代码一致，这样，我们就验证了我们答案1中的结论，可以开始我们的下文了

源码追踪分析，从Java到JNI，再到JVM的C++目的1寻源之旅：fileChannel.map()

       我们知道我们执行Java代码fileChannel.map()确实会在底层调用系统调用，那怎么在源码中得到验证呢？怎么落脚于源码进行分析呢？下面开始我们的寻源之旅

       FileChannelImpl.map() 注：由于代码较长，这里代码中略去了一些我们不关注的,比如异常捕获等

public MappedByteBuffer map(MapMode mode, long position, long size)throws IOException{ // ...try { // ...synchronized (positionLock) { // ...long mapPosition = position - pagePosition;mapSize = size + pagePosition;try { // ！我们要找的语句就在这！addr = map0(imode, mapPosition, mapSize);} catch (OutOfMemoryError x) { // 如果内存不足，先尝试进行GCSystem.gc();try { Thread.sleep();} catch (InterruptedException y) { Thread.currentThread().interrupt();}try { // 再次试着mmapaddr = map0(imode, mapPosition, mapSize);} catch (OutOfMemoryError y) { // After a second OOME, failthrow new IOException("Map failed", y);}}} // ...} finally { // ...}}

       上面函数源码中真正执行mmap的语句是在addr = map0(imode, mapPosition, mapSize),于是我们寻着这里继续追踪

       FileChannelImpl.map0()

// Creates a new mappingprivate native long map0(int prot, long position, long length)throws IOException;

       可以看到，该方法是一个native方法，所以后面的源码我们需要到这个FileChannelImpl.class对应的fileChannelImpl.c中去看，所以我们需要去找到JDK的源码

       在JDK源码中我们找到fileChannelImpl.c文件

       fileChannelImpl.c 根据JNI的对应规则，我们找到该文件内对应的Java_sun_nio_ch_FileChannelImpl_map0方法，其源码如下：

JNIEXPORT jlong JNICALLJava_sun_nio_ch_FileChannelImpl_map0(JNIEnv *env, jobject this, jint prot, jlong off, jlong len){ void *mapAddress = 0;jobject fdo = (*env)->GetObjectField(env, this, chan_fd);jint fd = fdval(env, fdo);int protections = 0;int flags = 0;if (prot == sun_nio_ch_FileChannelImpl_MAP_RO) { protections = PROT_READ;flags = MAP_SHARED;} else if (prot == sun_nio_ch_FileChannelImpl_MAP_RW) { protections = PROT_WRITE | PROT_READ;flags = MAP_SHARED;} else if (prot == sun_nio_ch_FileChannelImpl_MAP_PV) { protections =PROT_WRITE | PROT_READ;flags = MAP_PRIVATE;}// ！我们要找的语句就在这里！mapAddress = mmap(0,/* Let OS decide location */len,/* Number of bytes to map */protections,/* File permissions */flags,/* Changes are shared */fd, /* File descriptor of mapped file */off); /* Offset into file */if (mapAddress == MAP_FAILED) { if (errno == ENOMEM) { JNU_ThrowOutOfMemoryError(env, "Map failed");return IOS_THROWN;}return handle(env, -1, "Map failed");}return ((jlong) (unsigned long) mapAddress);}

       我们要找的语句就上面代码中的mapAddress = mmap(0,len,protections,flags,fd,off),至于为什么不是直接的mmap，而是mmap，是因为这里的mmap是一个宏，在文件上方有其定义，如下：

#define mmap mmap

       至此，我们就在源码中得到验证了我们问题2中的结论：fileChannelImpl.map()底层使用的是mmap系统调用

目的2寻源之旅：mmapedByteBuffer.put(Byte[ ])

       接着我们来看看当我们调用mmapedByteBuffer.put(Byte[])JVM底层在搞些什么动作

       MappedByteBuffer ?首先我们得知道，当我们执行MappedByteBuffer map = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, _GB)时，实际返回的对象是DirectByteBuffer类的实例，因为MappedByteBuffer为抽象类，且只有DirectByteBuffer继承了它，看下面两图就明白了

       DirectByteBuffer 于是我们找到DirectByteBuffer内的put(Byte[ ])方法

public ByteBuffer put(byte x) { unsafe.putByte(ix(nextPutIndex()), ((x)));return this;}

       可以看到该方法内实际是调用Unsafe类内的putByte方法来实现功能的，所以我们还得去看Unsafe类

       Unsafe.class

public native voidputByte(long address, byte x);

       该方法在Unsafe内是一个native方法，所以所以我们还得去看unsafe.cpp文件内对应的实现

       unsafe.cpp

       在JDK源码中，我们找到unsafe.cpp

       在这份源码内，没有使用JNI内普通加前缀的方法来形成对应关系

       不过我们还是能顺着源码的蛛丝轨迹找到我们要找的方法

       注意到源码中有这样的注册机制，所以我们可以知道我们要找的代码就是上图中标注的代码

       顺藤摸瓜，我们就找到了该方法的定义

UNSAFE_ENTRY(void, Unsafe_SetNative##Type(JNIEnv *env, jobject unsafe, jlong addr, java_type x)) \UnsafeWrapper("Unsafe_SetNative"#Type); \JavaThread* t = JavaThread::current(); \t->set_doing_unsafe_access(true); \void* p = addr_from_java(addr); \*(volatile native_type*)p = x; \t->set_doing_unsafe_access(false); \UNSAFE_END \

       该方法内主要的逻辑语句就是以下两句：

/** * @author Tptogiar * @description * @date /5/ - : */public class TestMappedByteBuffer{ public static final int _4kb = 4*;public static final int _GB= 1**;public static void main(String[] args) throws IOException, InterruptedException { // 为了方便在日志中找到本段代码的开始位置和结束位置，这里利用文件io来打开始标记FileInputStream startInput = null;try { startInput = new FileInputStream("start1.txt");startInput.read();} catch (IOException e) { e.printStackTrace();}File file = new File("filename");FileChannel fileChannel = new RandomAccessFile(file, "rw").getChannel();MappedByteBuffer map = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, _GB); //我们想分析的语句问题2for (int i = 0; i < _GB; i++) { map.put((byte)0); // 下文中需要分析的语句目的2}// 打结束标记FileInputStream endInput = null;try { endInput = new FileInputStream("end.txt");endInput.read();} catch (IOException e) { e.printStackTrace();}}}0

       至此，我们就知道：其实我们调用mmapedByteBuffer.put(Byte[ ])时，JVM底层并不需要涉及到系统调用（这里也可以用strace工具追踪从而得到验证）。也就是说通过mmap映射的空间在内核空间和用户空间是共享的，我们在用户空间只需要像平时使用用户空间那样就行了————获取地址，设置值，而不涉及用户态，内核态的切换

总结

       fileChannelImpl.map()底层用调用系统函数mmap

       fileChannelImpl.map()返回的其实不是MappedByteBuffer类对象，而是DirectByteBuffer类对象

       在linux上可以通过strace来追踪系统调用

       JNI中“.class”文件内方法与“.cpp”文件内函数的对应关系不止是前缀对应的方法，还可以是注册的方式，这一点的追寻代码的时候有很大帮助

       directByteBuffer.put()方法底层并没有涉及系统调用，也就不需要涉及切态的性能开销(其底层知识执行获取地址，设置值的操作)，所以mmap的性能就比普通读写read/write好

       ...

原文：/post/