neo4j 底层存储结构分析(5)

  • Post author:
  • Post category:IT
  • Post comments:0评论

上一节:neo4j 底层存储结构分析(4)

下一节:neo4j 底层存储结构分析(6)

3.5 Property 的存储

下面是neo4j graph db 中,Property数据存储对应的文件:

neostore.propertystore.db

neostore.propertystore.db.arrays

neostore.propertystore.db.arrays.id

neostore.propertystore.db.id

neostore.propertystore.db.index

neostore.propertystore.db.index.id

neostore.propertystore.db.index.keys

neostore.propertystore.db.index.keys.id

neostore.propertystore.db.strings

neostore.propertystore.db.strings.id

neo4j 中, Property 的存储是由 PropertyStore, ArrayPropertyStore, StringPropertyStore 和PropertyKeyTokenStore 4种类型的Store配合来完成的.

类PropertyStore对应的存储文件是neostore.propertystore.db, 相应的用来存储 string/array 类型属性值的文件分别是neostore.propertystore.db.strings (StringPropertyStore) 和 neostore.propertystore.db.arrays(ArrayPropertyStore). 其存储模型示意图如下:

neo4j_存储模型_property_2--20140423

其中PropertyStore是Property最主要的存储结构,当Property的Key-Value对的Value 是字符串或数组类型并且要求的存储空间比较大,在PropertyStore中保存不了,则会存在StringPropertyStore/ ArrayPropertyStore这样的DynamicStore 中。如果长度超过一个block ,则分block存储,并将其在StringPropertyStore/ ArrayPropertyStore中的第1个block 的 block_id 保存到 PropertyStore类型文件相应record 的PropertyBlock字段中。

 PropertyKeyTokenStore和StringPropertyStore 配合用来存储Propery的Key部分。Propery的Key是编码的,key 的 id 保存在 PropertyKeyTokenStore (即 neostore.propertystore.db.index),key 的字符串名保存在对应的StringPropertyStore类型文件neostore.propertystore.db.index.keys 中。

ArrayPropertyStore的存储格式见< 3.3.2 DynamicStore 类型>,下面分别介绍一下PropertyStore和PropertyKeyTokenStore(PropertyKeyTokenStore)的文件存储格式。

3.5.1   PropertyStore类型的存储格式

neostore.propertystore.db文件存储格式示意图如下,整个文件是有一个 RECORD_SIZE=41 Bytes 的定长数组和一个字符串描述符“PropertyStore v0.A.2”(文件类型描述TYPE_DESCRIPTOR和 neo4j 的 ALL_STORES_VERSION构成)。访问时,可以通过 prop_id 作为数组的下标进行访问。

neo4j_文件存储格式_PropertyStore--20140408

下面介绍一下 property record 中每个字段的含义:

  • highByte(1 Byte):第1字节,共分成2部分

/*

* [pppp,nnnn] previous, next high bits

*/

byte modifiers = buffer.get();

    1. 第1~4 bit 表示 next 的高4位;
    2. 第 5~8 bit表示 prev 的高4位
  • prev(4 Bytes) : Node或Relationship 的属性是通过双向链表方式组织的,prev 表示本属性在双向链表中的上一个属性的id。第2~5字节是prev property_id的 低32位. 加上highByte字节的第 5~8 bit作为高4位,构成一个完整的36位property_id。
  • next(4 Bytes) : next 表示本属性在双向链表中的下一个属性的id。第6~9字节是next property_id的 低32位. 加上highByte字节的第 1~4 bit作为高4位,构成一个完整的36位property_id。
  • payload:  payload 由block_header(8 Bytes)加3个property_block(8 Bytes)组成,共计 32 Bytes.  block_header 分成3部分:
    1. key_id(24 bits) : 第1 ~24 bit , property 的key 的 id
    2.  type( 4 bits ):   第25 ~28 bit , property 的 value 的类型,支持 string, Interger,Boolean, Float, Long,Double, Byte, Character,Short, array.
    3. payload(36 bits): 第29 ~64 bit, 共计36bit;对于Interger, Boolean, Float, Byte, Character , Short 类型的值,直接保存在payload;对于long,如果36位可以表示,则直接保存在payload,如果不够,则保存到第1个PropertyBlock中;double 类型,保存到第1个PropertyBlock中;对于 array/string ,如果编码后在 block_header及3个PropertyBlock 能保存,则直接保存;否则,保存到ArrayDynamicStore/StringDynamicStore 中, payload 保存其在ArrayDynamicStore中的数组下表。

3.5.2   String 类型属性值的保存过程

下面的代码片段展示了neo4j 中,比较长的 String 类型属性值的保存处理过程,其是如何分成多个 DynamicBlock 来存储的。

PropertyStore_encode

3.5.2.1        encodeValue 函数

encodeValue 函数是 PropertySTore.java 的成员函数, 它实现了不同类型的属性值的编码.

</pre>
<div>
public void encodeValue( PropertyBlock block, int keyId, Object value )

{

if ( value instanceof String )

{   // Try short string first, i.e. inlined in the property block

String string = (String) value;

if ( LongerShortString.encode( keyId, string, block, PropertyType.getPayloadSize() ) )

{

return;

}

// Fall back to dynamic string store

byte[] encodedString = encodeString( string );

Collection valueRecords = allocateStringRecords( encodedString );

setSingleBlockValue( block, keyId, PropertyType.STRING, first( valueRecords ).getId() );

for ( DynamicRecord valueRecord : valueRecords )

{

valueRecord.setType( PropertyType.STRING.intValue() );

block.addValueRecord( valueRecord );

}

}

else if ( value instanceof Integer )

{

setSingleBlockValue( block, keyId, PropertyType.INT, ((Integer) value).longValue() );

}

else if ( value instanceof Boolean )

{

setSingleBlockValue( block, keyId, PropertyType.BOOL, ((Boolean) value ? 1L : 0L) );

}

else if ( value instanceof Float )

{

setSingleBlockValue( block, keyId, PropertyType.FLOAT, Float.floatToRawIntBits( (Float) value ) );

}

else if ( value instanceof Long )

{

long keyAndType = keyId | (((long) PropertyType.LONG.intValue()) << 24);

if ( ShortArray.LONG.getRequiredBits( (Long) value ) <= 35 )

{   // We only need one block for this value, special layout compared to, say, an integer

block.setSingleBlock( keyAndType | (1L << 28) | ((Long) value << 29) );

}

else

{   // We need two blocks for this value

block.setValueBlocks( new long[]{keyAndType, (Long) value} );

}

}

else if ( value instanceof Double )

{

block.setValueBlocks( new long[]{

keyId | (((long) PropertyType.DOUBLE.intValue()) << 24),

Double.doubleToRawLongBits( (Double) value )} );

}

else if ( value instanceof Byte )

{

setSingleBlockValue( block, keyId, PropertyType.BYTE, ((Byte) value).longValue() );

}

else if ( value instanceof Character )

{

setSingleBlockValue( block, keyId, PropertyType.CHAR, (Character) value );

}

else if ( value instanceof Short )

{

setSingleBlockValue( block, keyId, PropertyType.SHORT, ((Short) value).longValue() );

}

else if ( value.getClass().isArray() )

{   // Try short array first, i.e. inlined in the property block

if ( ShortArray.encode( keyId, value, block, PropertyType.getPayloadSize() ) )

{

return;

}

// Fall back to dynamic array store

Collection arrayRecords = allocateArrayRecords( value );

setSingleBlockValue( block, keyId, PropertyType.ARRAY, first( arrayRecords ).getId() );

for ( DynamicRecord valueRecord : arrayRecords )

{

valueRecord.setType( PropertyType.ARRAY.intValue() );

block.addValueRecord( valueRecord );

}

}

else

{

throw new IllegalArgumentException( "Unknown property type on: " + value + ", " + value.getClass() );

}

}

3.5.2.2        allocateStringRecords 函数

allocateStringRecords 函数是 PropertySTore.java 的成员函数.

</pre>
<div>
private Collection allocateStringRecords( byte[] chars )

{

return stringPropertyStore.allocateRecordsFromBytes( chars );

}

3.5.2.3        allocateRecordsFromBytes 函数

allocateRecordsFromBytes 函数是 AbstractDynamicStore .java 的成员函数.

</pre>
<div>
protected Collection allocateRecordsFromBytes( byte src[] )

{

return allocateRecordsFromBytes( src, Collections.emptyList().iterator(),

recordAllocator );

}

3.5.2.4        allocateRecordsFromBytes 函数

allocateRecordsFromBytes 函数是 AbstractDynamicStore .java 的成员函数.

</pre>
<div>
public static Collection allocateRecordsFromBytes(

byte src[], Iterator recordsToUseFirst,

DynamicRecordAllocator dynamicRecordAllocator )

{

assert src != null : "Null src argument";

List recordList = new LinkedList<>();

DynamicRecord nextRecord = dynamicRecordAllocator.nextUsedRecordOrNew( recordsToUseFirst );

int srcOffset = 0;

int dataSize = dynamicRecordAllocator.dataSize();

do

{

DynamicRecord record = nextRecord;

record.setStartRecord( srcOffset == 0 );

if ( src.length - srcOffset > dataSize )

{

byte data[] = new byte[dataSize];

System.arraycopy( src, srcOffset, data, 0, dataSize );

record.setData( data );

nextRecord = dynamicRecordAllocator.nextUsedRecordOrNew( recordsToUseFirst );

record.setNextBlock( nextRecord.getId() );

srcOffset += dataSize;

}

else

{

byte data[] = new byte[src.length - srcOffset];

System.arraycopy( src, srcOffset, data, 0, data.length );

record.setData( data );

nextRecord = null;

record.setNextBlock( Record.NO_NEXT_BLOCK.intValue() );

}

recordList.add( record );

assert !record.isLight();

assert record.getData() != null;

}

while ( nextRecord != null );

return recordList;

}

3.5.3   ShortArray 类型属性值的保存过程

ShortArray.encode( keyId, value, block, PropertyType.getPayloadSize() ), 它是在 kernel/impl/nioneo/store/ShortArray.java 中实现的,下面是其代码片段。

</pre>
<div>
public static boolean encode( int keyId, Object array, PropertyBlock target, int payloadSizeInBytes )

{

/*

*  If the array is huge, we don't have to check anything else.

*  So do the length check first.

*/

int arrayLength = Array.getLength( array );

if ( arrayLength > 63 )/*because we only use 6 bits for length*/

{

return false;

}

ShortArray type = typeOf( array );

if ( type == null )

{

return false;

}

int requiredBits = type.calculateRequiredBitsForArray( array, arrayLength );

if ( !willFit( requiredBits, arrayLength, payloadSizeInBytes ) )

{

// Too big array

return false;

}

final int numberOfBytes = calculateNumberOfBlocksUsed( arrayLength, requiredBits ) * 8;

if ( Bits.requiredLongs( numberOfBytes ) > PropertyType.getPayloadSizeLongs() )

{

return false;

}

Bits result = Bits.bits( numberOfBytes );

// [][][    ,bbbb][bbll,llll][yyyy,tttt][kkkk,kkkk][kkkk,kkkk][kkkk,kkkk]

writeHeader( keyId, type, arrayLength, requiredBits, result );

type.writeAll( array, arrayLength, requiredBits, result );

target.setValueBlocks( result.getLongs() );

return true;

}

private static void writeHeader( int keyId, ShortArray type, int arrayLength, int requiredBits, Bits result )

{

result.put( keyId, 24 );

result.put( PropertyType.SHORT_ARRAY.intValue(), 4 );

result.put( type.type.intValue(), 4 );

result.put( arrayLength, 6 );

result.put( requiredBits, 6 );

}

3.5.4   PropertyKeyTokenStore的文件存储格式

neo4j_文件存储格式_PropertyIndexStore--20140410

类PropertyTypeTokenStore对应的存储文件名是neostore.propertystore.db.index,其对应的存储格式如上图所示: 是一个长度为 RECORD_SIZE=9Bytes 的 record 数组和和一个字符串“PropertyIndexStore v0.A.2”(文件类型描述TYPE_DESCRIPTOR和 neo4j 的 ALL_STORES_VERSION构成)。访问时,可以通过 token_id 作为数组的下标进行访问。

record 是由 in_use(1 Byte) ,prop_count(4 Bytes), name_id(4 Bytes)构成。

发表评论