Graph database_neo4j 底层存储结构分析(4)

3.3.2   DynamicStore 类型

3.3.2.1        AbstractDynamicStore 的存储格式

neo4j 中对于字符串等变长值的保存策略是用一组定长的 block 来保存,block之间用单向链表链接。类 AbstractDynamicStore 实现了该功能,下面是其注释说明。

/**

* An abstract representation of a dynamic store. The difference between a

* normal AbstractStore and a AbstractDynamicStore is

* that the size of a record/entry can be dynamic.

* Instead of a fixed record this class uses blocks to store a record. If a

* record size is greater than the block size the record will use one or more

* blocks to store its data.

* A dynamic store don’t have a IdGenerator because the position of a

* record can’t be calculated just by knowing the id. Instead one should use a

* AbstractStore and store the start block of the record located in the

* dynamic store. Note: This class makes use of an id generator internally for

* managing free and non free blocks.

* Note, the first block of a dynamic store is reserved and contains information

* about the store.

*/

Graph database_neo4j 底层存储结构分析(4)

AbstractDynamicStore 类对应的存储文件格式如上图所示, 整个文件是有一个block_size=BLOCK_HEADER_SIZE(8Bytes)+block_content_size的定长数组和一个字符串“StringPropertyStore v0.A.2”或“ArrayPropertyStore v0.A.2”或“SchemaStore v0.A.2”(文件类型描述TYPE_DESCRIPTOR和 neo4j 的 ALL_STORES_VERSION构成)。访问时,可以通过 id 作为数组的下标进行访问。其中,文件的第1个 record 中前4 字节用来保存 block_size。文件的第2个 record开始保存实际的block数据,它由8个字节的block_header和定长的 block_content(可配置)构成. block_header 结构如下:

  • inUse(1 Byte):第1字节,共分成3部分

[x__ ,    ]  0: start record, 1: linked record

[   x,    ]  inUse

[    ,xxxx]  high next block bits

    • 第1~4 bit 表示next_block 的高4位
    • 第5 bit表示block 是否在 use;
    • 第8 bit 表示 block 是否是单向链表的第1个 block;0 表示第1个block, 1表示后续 block.
    • nr_of_bytes(3Bytes):本 block 中保存的数据的长度。
    • next_block(4Bytes): next_block 的低 4 个字节,加上 inUse 的第1~4 位,next_block 的实际长度共 36 bit。以数组方式存储的单向链表的指针,指向保存同一条数据的下一个 block 的id.

    3.3.2.2        AbstractDynamicStore.java

    下面看一下 AbstractDynamicStore.java 中 getRecord() 和readAndVerifyBlockSize() 成员函数,可以帮助理解 DynamicStore 的存储格式。

    • getRecord( long blockId, PersistenceWindow window, RecordLoad load )
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    private DynamicRecord getRecord( long blockId, PersistenceWindow window, RecordLoad load )</pre>
    <div>{
     
    DynamicRecord record = new DynamicRecord( blockId );
     
    Buffer buffer = window.getOffsettedBuffer( blockId );
     
    /*
     
    * First 4b
     
    * [x   ,    ][    ,    ][    ,    ][    ,    ] 0: start record, 1: linked record
     
    * [   x,    ][    ,    ][    ,    ][    ,    ] inUse
     
    * [    ,xxxx][    ,    ][    ,    ][    ,    ] high next block bits
     
    * [    ,    ][xxxx,xxxx][xxxx,xxxx][xxxx,xxxx] nr of bytes in the data field in this record
     
    *
     
    */
     
    long firstInteger = buffer.getUnsignedInt();
     
    boolean isStartRecord = (firstInteger & 0x80000000) == 0;
     
    long maskedInteger = firstInteger & ~0x80000000;
     
    int highNibbleInMaskedInteger = (int) ( ( maskedInteger ) >> 28 );
     
    boolean inUse = highNibbleInMaskedInteger == Record.IN_USE.intValue();
     
    if ( !inUse && load != RecordLoad.FORCE )
     
    {
     
    throw new InvalidRecordException( "DynamicRecord Not in use, blockId[" + blockId + "]" );
     
    }
     
    int dataSize = getBlockSize() - BLOCK_HEADER_SIZE;
     
    int nrOfBytes = (int) ( firstInteger & 0xFFFFFF );
     
    /*
     
    * Pointer to next block 4b (low bits of the pointer)
     
    */
     
    long nextBlock = buffer.getUnsignedInt();
     
    long nextModifier = ( firstInteger & 0xF000000L ) << 8;
     
    long longNextBlock = longFromIntAndMod( nextBlock, nextModifier );
     
    boolean readData = load != RecordLoad.CHECK;
     
    if ( longNextBlock != Record.NO_NEXT_BLOCK.intValue()
     
    && nrOfBytes < dataSize || nrOfBytes > dataSize )
     
    {
     
    readData = false;
     
    if ( load != RecordLoad.FORCE )
     
    {
     
    throw new InvalidRecordException( "Next block set[" + nextBlock
     
    + "] current block illegal size[" + nrOfBytes + "/" + dataSize + "]" );
     
    }
     
    }
     
    record.setInUse( inUse );
     
    record.setStartRecord( isStartRecord );
     
    record.setLength( nrOfBytes );
     
    record.setNextBlock( longNextBlock );
     
    /*
     
    * Data 'nrOfBytes' bytes
     
    */
     
    if ( readData )
     
    {
     
    byte byteArrayElement[] = new byte[nrOfBytes];
     
    buffer.get( byteArrayElement );
     
    record.setData( byteArrayElement );
     
    }
     
    return record;
     
    }
    • readAndVerifyBlockSize()
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    </pre>
    <div>protected void readAndVerifyBlockSize() throws IOException
     
    {
     
    ByteBuffer buffer = ByteBuffer.allocate( 4 );
     
    getFileChannel().position( 0 );
     
    getFileChannel().read( buffer );
     
    buffer.flip();
     
    blockSize = buffer.getInt();
     
    if ( blockSize <= 0 )
     
    {
     
    throw new InvalidRecordException( "Illegal block size: " +
     
    blockSize + " in " + getStorageFileName() );
     
    }
     
    }

    3.3.2.3        类DynamicArrayStore, DynamicStringStore

    类SchemaStore,DynamicArrayStore(ArrayPropertyStore), DynamicStringStore(StringPropertyStore)都是继承成自类AbstractDynamicStore,所以与类DynamicArrayStore, DynamicStringStore和 SchemaStore对应文件的存储格式,都是遵循AbstractDynamicStore的存储格式,除了block块的大小(block_size)不同外。

    db 文件 存储类型 block_size
    neostore.labeltokenstore.db.names StringPropertyStore NAME_STORE_BLOCK_SIZE=30
    neostore.propertystore.db.index.keys StringPropertyStore NAME_STORE_BLOCK_SIZE=30
    neostore.relationshiptypestore.db.names StringPropertyStore NAME_STORE_BLOCK_SIZE=30
    neostore.propertystore.db.strings StringPropertyStore string_block_size=120
    neostore.nodestore.db.labels ArrayPropertyStore label_block_size=60
    neostore.propertystore.db.arrays ArrayPropertyStore array_block_size=120
    neostore.schemastore.db SchemaStore BLOCK_SIZE=56

    block_size 通过配置文件或缺省值来设置的,下面的代码片段展示了neostore.propertystore.db.strings 文件的创建过程及block_size 的大小如何传入。

    1)        GraphDatabaseSettings.java

    1
    2
    3
    4
    5
    6
    7
    </pre>
    <div>public static final Setting string_block_size = setting("string_block_size", INTEGER, "120",min(1));
     
    public static final Setting array_block_size = setting("array_block_size", INTEGER, "120",min(1));
     
    public static final Setting label_block_size = setting("label_block_size", INTEGER, "60",min(1));</div>
    <pre>
        2)        StoreFactory.java的Configuration 类
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    </pre>
    <div>public static abstract class Configuration
     
    {
     
    public static final Setting string_block_size = GraphDatabaseSettings.string_block_size;
     
    public static final Setting array_block_size = GraphDatabaseSettings.array_block_size;
     
    public static final Setting label_block_size = GraphDatabaseSettings.label_block_size;
     
    public static final Setting dense_node_threshold = GraphDatabaseSettings.dense_node_threshold;
     
    }

    3)        StoreFactory.java的createPropertyStore 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    </pre>
    <div>public void createPropertyStore( File fileName )
     
    {
     
    createEmptyStore( fileName, buildTypeDescriptorAndVersion( PropertyStore.TYPE_DESCRIPTOR ));
     
    int stringStoreBlockSize = config.get( Configuration.string_block_size );
     
    int arrayStoreBlockSize = config.get( Configuration.array_block_size )
     
    createDynamicStringStore(new File( fileName.getPath() + STRINGS_PART), stringStoreBlockSize, IdType.STRING_BLOCK);
     
    createPropertyKeyTokenStore( new File( fileName.getPath() + INDEX_PART ) );
     
    createDynamicArrayStore( new File( fileName.getPath() + ARRAYS_PART ), arrayStoreBlockSize );
     
    }

    4)        StoreFactory.java的createDynamicStringStore函数

    1
    2
    3
    4
    5
    6
    7
    8
    </pre>
    <div>private void createDynamicStringStore( File fileName, int blockSize, IdType idType )
     
    {
     
    createEmptyDynamicStore(fileName, blockSize, DynamicStringStore.VERSION, idType);
     
    }

    5)        StoreFactory.java的createEmptyDynamicStore 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    </pre>
    <div>
    /**
     
    * Creates a new empty store. A factory method returning an implementation
     
    * should make use of this method to initialize an empty store. Block size
     
    * must be greater than zero. Not that the first block will be marked as
     
    * reserved (contains info about the block size). There will be an overhead
     
    * for each block of <CODE>AbstractDynamicStore.BLOCK_HEADER_SIZE</CODE>bytes.
     
    */
     
    public void createEmptyDynamicStore( File fileName, int baseBlockSize,
     
    String typeAndVersionDescriptor, IdType idType)
     
    {
     
    int blockSize = baseBlockSize;
     
    // sanity checks
     
     
    blockSize += AbstractDynamicStore.BLOCK_HEADER_SIZE;
     
    // write the header
     
    try
     
    {
     
    FileChannel channel = fileSystemAbstraction.create(fileName);
     
    int endHeaderSize = blockSize
     
    + UTF8.encode( typeAndVersionDescriptor ).length;
     
    ByteBuffer buffer = ByteBuffer.allocate( endHeaderSize );
     
    buffer.putInt( blockSize );
     
    buffer.position( endHeaderSize - typeAndVersionDescriptor.length() );
     
    buffer.put( UTF8.encode( typeAndVersionDescriptor ) ).flip();
     
    channel.write( buffer );
     
    channel.force( false );
     
    channel.close();
     
    }
     
    catch ( IOException e )
     
    {
     
    throw new UnderlyingStorageException( "Unable to create store "
     
    + fileName, e );
     
    }
     
    idGeneratorFactory.create( fileSystemAbstraction, new File( fileName.getPath() + ".id"), 0 );
     
    // TODO highestIdInUse = 0 works now, but not when slave can create store files.
     
    IdGenerator idGenerator = idGeneratorFactory.open(fileSystemAbstraction,
     
    new File( fileName.getPath() + ".id"),idType.getGrabSize(), idType, 0 );
     
    idGenerator.nextId(); // reserve first for blockSize
     
    idGenerator.close();
     
    }
    上一篇:深入理解css3中的线性渐变


    下一篇:Linux 中指定启动 tomcat 的 jdk 版本