diff options
| -rw-r--r-- | main.go | 3 | ||||
| -rw-r--r-- | merkle.go | 75 | ||||
| -rw-r--r-- | merkle_test.go | 32 |
3 files changed, 80 insertions, 30 deletions
@@ -11,6 +11,7 @@ func main() { height := flag.Int64("height", 0, "number of nodes is 2 ** height - 1") fname := flag.String("db", "test.db", "filename for the database") mtype := flag.String("mtype", "bfs", "type of Merkle tree (bfs or post)") + p := flag.Bool("p", false, "parallel build") prof := flag.String("prof", "prof.prof", "filename for profile information") flag.Parse() @@ -22,7 +23,7 @@ func main() { defer pprof.StopCPUProfile() m := NewMerkle(*mtype, *height, *fname) - m.Build() + m.Build(*p) /* root := make([]byte, hashSize) m.Read(root, 0) @@ -1,8 +1,10 @@ package main import ( + "bytes" "encoding/binary" "os" + "sync" "golang.org/x/crypto/sha3" ) @@ -10,7 +12,7 @@ import ( var hashSize = int64(sha3.New256().Size()) type Merkle interface { - Build() []byte + Build(parallel bool) []byte Put(id int64, data []byte) Read(buf []byte, id int64) Size() int64 @@ -56,8 +58,16 @@ func (m *BFSMerkle) Read(buf []byte, id int64) { m.ReadAt(buf, id*hashSize) } +func (m *BFSMerkle) Build(parallel bool) []byte { + if parallel { + return m.parallelbuild() + } else { + return m.build() + } +} + // disk access is sequential and mostly backward -func (m *BFSMerkle) Build() []byte { +func (m *BFSMerkle) build() []byte { size := m.Size() h := sha3.New256() hsize := int64(h.Size()) @@ -82,6 +92,53 @@ func (m *BFSMerkle) Build() []byte { return buf } +func (m *BFSMerkle) parallelbuild() []byte { + size := m.Size() + hsize := hashSize + var left int64 + var wg sync.WaitGroup + p := 100 + + i := 0 + for id := size / 2; id <= size; id++ { + wg.Add(1) + go func(id int64) { + defer wg.Done() + var buf bytes.Buffer + binary.Write(&buf, binary.LittleEndian, id) + hash := sha3.Sum256(buf.Bytes()) + m.WriteAt(hash[:], id*hsize) + }(id) + if i%p == 0 { + wg.Wait() + } + i++ + } + + for height := m.height - 1; height >= 1; height-- { + left = 1 << uint64(height-1) + i := 0 + for id := left - 1; id < 2*left-1; id++ { + wg.Add(1) + go func(id int64) { + defer wg.Done() + buf := make([]byte, 2*hsize) + m.ReadAt(buf, (id*2+1)*hsize) + m.ReadAt(buf[hsize:], (id*2+2)*hsize) + hash := sha3.Sum256(buf) + m.WriteAt(hash[:], id*hsize) + }(id) + if i%p == 0 { + wg.Wait() + } + i++ + } + } + buf := make([]byte, hsize) + m.ReadAt(buf, 0) + return buf +} + func (m *BFSMerkle) Proof(id int64) [][]byte { proof := make([][]byte, m.height) proof[0] = make([]byte, hashSize) @@ -124,7 +181,9 @@ func (m *BFSMerkle) BatchProofs(ids []int64) [][][]byte { for i := range proofs { proofs[i][height] = make([]byte, hashSize) id = tids[i] - if id&1 == 0 { + if i > 0 && id == tids[i-1] { + proofs[i][height] = proofs[i-1][height] + } else if id&1 == 0 { m.ReadAt(proofs[i][height], (id-1)*hashSize) } else { m.ReadAt(proofs[i][height], (id+1)*hashSize) @@ -167,7 +226,7 @@ func (m *PostMerkle) Read(buf []byte, id int64) { // Iterative post-order depth-first construction of the Merkle tree // disk access is optimal and forward -func (m *PostMerkle) Build() []byte { +func (m *PostMerkle) Build(parallel bool) []byte { size := m.Size() h := sha3.New256() hsize := int64(h.Size()) @@ -235,3 +294,11 @@ func (m *PostMerkle) Proof(id int64) [][]byte { m.ReadAt(proof[0], cur*hashSize) return proof } + +func (m *PostMerkle) Proofs(ids []int64) [][][]byte { + proofs := make([][][]byte, len(ids)) + for i, id := range ids { + proofs[i] = m.Proof(id) + } + return proofs +} diff --git a/merkle_test.go b/merkle_test.go index adc8861..c10d17c 100644 --- a/merkle_test.go +++ b/merkle_test.go @@ -41,38 +41,20 @@ func TestMerkle(t *testing.T) { } } -func TestBenchmarkBFSMerkle(t *testing.T) { +var proofs [][][]byte + +func TestProofsBFSMerkle(t *testing.T) { m := NewBFSMerkle(25, "/mnt/data/bfs.db") - var proof [][]byte + root := make([]byte, hashSize) + m.Read(root, 0) start := time.Now() - for i := 0; i < N; i++ { - proof = m.Proof(ids[i]) - if len(proof) != int(m.height) { - fmt.Println("error") - } - } + proofs = m.Proofs(ids) elapsed := time.Since(start) fmt.Println(elapsed, elapsed.Nanoseconds()/N) } -func TestBenchmarkPostMerkle(t *testing.T) { +func TestProofsPostMerkle(t *testing.T) { m := NewPostMerkle(25, "/mnt/data/post.db") - var proof [][]byte - start := time.Now() - for i := 0; i < N; i++ { - proof = m.Proof(ids[i]) - if len(proof) != int(m.height) { - fmt.Println("error") - } - } - elapsed := time.Since(start) - fmt.Println(elapsed, elapsed.Nanoseconds()/N) -} - -var proofs [][][]byte - -func TestProofsBFSMerkle(t *testing.T) { - m := NewBFSMerkle(25, "/mnt/data/bfs.db") root := make([]byte, hashSize) m.Read(root, 0) start := time.Now() |