Dgraph - A high performance graph database written in pure Go

1SFEJDBUF 0CKFDUͰදݱ w 4VCKFDUࢧ఺ͱͳΔ/PEF w 1SFEJDBUFؔ܎Λද͢&EHF w 0CKFDUऴ఺ͱͳΔ/PEF %HSBQIͱ͸ <a> <is> <person> . <is> <person> . <a> <named> <Alice> . <named> <Bob> . <a> <friend> . RDF ٖࣅίʔυʹ͓͚ΔϑϨϯυϦϨʔγϣϯ

©2018 Wantedly, Inc. 3%'5SJQMF Dgraphͱ͸ <a> <is> <person> .

<is> <person> . <a> <named> <Alice> . <named> <Bob> . <a> <friend> . RDF ٖࣅίʔυʹ͓͚ΔϑϨϯυϦϨʔγϣϯ C Bob b a Alice friend named ==

©2018 Wantedly, Inc. 3%'5SJQMF w QFSTPO͕ͳ͍ w 0CKFDU4VCKFDU͸&OUJUZͱ"UUSJCVUF͕͋Δ w

&OUJUZ6TFSͳͲͷ֓೦Λද͢ w "UUSJCVUF஋Λද͢ w ຊ࣭తʹ͸ϞσϦϯάʹ͸ؔ܎͕ͳ͍ w OBNFEQSFEJDBUF͕͋ΔͳΒͦΕ͸QFSTPO w ·ΔͰ%VDL5ZQJOH Dgraphͱ͸ C Bob b a Alice friend named

©2018 Wantedly, Inc. %HSBQIͷσʔλߏ଄

©2018 Wantedly, Inc. άϥϑ͸̎ͭͷσʔλߏ଄ʹΑͬͯදݱ͞Ε͍ͯΔ w 1PTUJOH w 1PTUJOH-JTU %HSBQIͷσʔλߏ଄

©2018 Wantedly, Inc. 1PTUJOH w %HSBQIͷσʔλͷ࠷খ୯Ґ w 1SFEJDBUFͱͦΕʹඥͮ͘  4VCKFDUͱ0CKFDUΛ಺แ͢Δ w

WBMVF@UZQF͕6*% w 4VCKFDU͸&OUJUZͰ͋Δ w ͦΕҎ֎͸"UUSJCVUF w WBMVFʹ͸࣮σʔλ͕ೖΔ %HSBQIͷσʔλߏ଄ message Posting { fixed64 uid = 1; bytes value = 2; enum ValType { DEFAULT = 0; BINARY = 1; INT = 2; FLOAT = 3; BOOL = 4; DATETIME = 5; GEO = 6; UID = 7; PASSWORD = 8; STRING = 9; } ValType val_type = 3; ... ... enum PostingType { REF=0; VALUE=1; VALUE_LANG=2; } PostingType posting_type = 4; bytes lang_tag = 5; string label = 6; repeated api.Facet facets = 9; uint32 op = 12; uint64 start_ts = 13; uint64 commit_ts = 14; } Protobuf ʹΑΔ Posting ͷఆٛ

©2018 Wantedly, Inc. 1PTUJOH-JTU w 1SFEJDBUFͱ4VCKFDUͷϖΞʹඥͮ͘1PTUJOHΛͻͱ·ͱΊʹͨ͠΋ͷ w ͻͱ·ͱΊʹ͢Δ͜ͱͰɺ͋ΔϢʔβͷ༑ୡҰཡ  ΛҰճͷ୳ࡧͰऔಘͰ͖Δ w

,74ͷLFZʹ1SFEJDBUFͱ4VCKFDUؚ͕·ΕΔ w ͦͷҝ1PTUJOHʹ͸ࣗ෼͕ԿऀͰ͋Δ͔Λ  දݱ͢ΔGJFME͕ͳ͍ %HSBQIͷσʔλߏ଄ message PostingList { repeated Posting postings = 1; bytes checksum = 2; uint64 commit = 3; bytes uids = 4; } Protobuf ʹΑΔ Posting ͷఆٛ (Predicate,Subject) -> PostingList KVS ΁ͷετΞํ๏

©2018 Wantedly, Inc. #BEHFS w %HSBQIͷ։ൃνʔϜ͕࡞੒ͨ͠(PͰॻ͔Εͨ,74 w ϋΠύϑΥʔϚϯε w 3BOEPN3FBE͸'BDFCPPL੡ͷ,74Ͱ͋Δ3PDLT%#ͷഒ

w 44%΁ͷ࠷దԽ w "$*%5SBOTBDUJPOͷαϙʔτ DdgraphͷσʔλετϨʔδ

©2018 Wantedly, Inc. Կނ#BEHFSΛ࡞ͬͨͷ͔ w ΋ͱ΋ͱ͸3PDLT%#Λ࢖͍ͬͯͨ w ͔͠͠$HPΛ͔ͭ͏σϝϦοτ͕େ͖͗ͨ͢ w (PͷΤίγεςϜʹ৐Εͳ͍

w QQSPGSBDFEFUFDUPS w QUISFBE@DSFBUFͰόάΛҾ͖ى͜͠ɺύϑΥʔϚϯε͕௿Լ͢Δ w (Pͷࠒ w ($͕ޮ͔ͳ͍ͷͰ$GSFF Λ๨ΕΔͱϝϞϦϦʔΫΛҾ͖ى͜͢ DdgraphͷσʔλετϨʔδ

©2018 Wantedly, Inc. Կނ#BEHFSΛ࡞ͬͨͷ͔ w (PͰॻ͔Ε͍ͯΔ#PMU%#͸Ͳ͏ͩͬͨͷ͔ w #PMU%#͸3FBE8SJUFڞʹάϩʔόϧۭؒʹ͋ΔTZOD38.VUFYͷϩοΫΛͱΔ w ฒྻॲཧ͕ग़དྷͳ͍

w 1PTUJOH-JTUͷมߋʹେ͖ͳӨڹΛ༩͑ͨ DdgraphͷσʔλετϨʔδ

©2018 Wantedly, Inc. #BEHFSͷ࢓૊Έ

ॻ͖ࠐΉͱ͖ʹ.FN5BCMFʹσʔλ͕ೖΒͳ͍৔߹͸ϑΝΠϧʹϑϥογϡ γʔΫͷྔΛݮΒͨ͢ΊʹɺϑΝΠϧ͕ଟ͘ͳ͖ͬͯͨΒϑΝΠϧΛϚʔδͤ͞Δ w $PNQBDUJPO Storage architecture of Badger

Badger L W Alice 10 Bob 20 Level 1 L W Carol 30 Level 0 (Mem Table)

Badger L W Alice 10 Bob 20 Level 1 L W Carol 30 muni 30 Level 0 (Mem Table)

Badger L W Alice 10 Bob 20 Level 1 L W Level 0 (Mem Table) L W Carol 10 muni 20

(Alice, 10) when merge Storage architecture of Badger L W Alice 10 Bob 20 Level 1 L W Alice 20 Level 0 (Mem Table) L W Carol 10 muni 20

Badger L W Alice 10 Bob 20 Level 1 L W Alice 20 Level 0 (Mem Table) L W Carol 10 muni 20

Badger L W Alice 10 Bob 20 Level 1 L W Alice 20 mike 50 Level 0 (Mem Table) L W Carol 10 muni 20

Badger L W Alice 20 mike 50 Level 1 L W Level 0 (Mem Table) L W Carol 10 muni 20 Bob 20 Level 2

w ಡΈࠐΉͱ͖͸௿Ϩϕϧ͔Βॱʹߦ͏ͷͰɺஞ࣍σʔλΛߋ৽͢Δඞཁ͕ͳ͍ w ϑΝΠϧͷ਺͚ͩγʔΫ͢Ε͹Α͍ w ϑΝΠϧʹ͸Ͳͷ,FZؚ͕·Ε͍ͯΔͷ͔֬ೝ͢ΔͨΊͷ#MPPN'JMUFS͕͋Δ w #MPPN'JMUFS͕GBMTFΛฦͨ͠৔߹͸ͦͷϑΝΠϧʹ͸,FZ͸ඞͣଘࡏ͠ͳ͍ Storage architecture of Badger

©2018 Wantedly, Inc. "$*%5SBOTBDUJPO w ࣮૷͸.VMUJ7FSTJPO$PODVSSFODZ$POUSPM w 3FBEͨ͠ͱ͖ɺߦʹUJNFTUBNQΛ෇༩͢Δ w ผͷτϥϯβΫγϣϯͰಉ͡ߦʹະίϛοτͷมߋ͕૸ͬͨ

w มߋ͸ϝϞϦʹରͯ͠ߦͳΘΕɺଞͷτϥϯβΫγϣϯ͔Β͸ݟ͑ͳ͍ w ίϛοτͯ͠ߦͷ࣮σʔλͷUJNFTUBNQΛߋ৽ w τϥϯβΫγϣϯ಺ͰҰճ3FBEͨ͠ߦΛ΋͏Ұ౓ࢀর w طʹUJNFTUBNQ͕෇༩͞Ε͍ͯΔͷͰલͷ஋Λฦ͢ ACID Transaction of Badger

Dgraph - A high performance graph database writ...

Dgraph - A high performance graph database written in pure Go

More Decks by Yuichi Saito

Other Decks in Technology

Featured

Transcript