Skip to content

Latest commit

 

History

History
213 lines (198 loc) · 8.24 KB

q010.md

File metadata and controls

213 lines (198 loc) · 8.24 KB

实现阻塞读且并发安全的map

GO里面MAP如何实现key不存在 get操作等待 直到key存在或者超时，保证并发安全，且需要实现以下接口：

type sp interface {
    Out(key string, val interface{})  //存入key /val，如果该key读取的goroutine挂起，则唤醒。此方法不会阻塞，时刻都可以立即执行并返回
    Rd(key string, timeout time.Duration) interface{}  //读取一个key，如果key不存在阻塞，等待key存在或者超时
}

解析：

看到阻塞协程第一个想到的就是channel，题目中要求并发安全，那么必须用锁，还要实现多个goroutine读的时候如果值不存在则阻塞，直到写入值，那么每个键值需要有一个阻塞goroutine 的 channel。

实现如下：

// You can edit this code!
// Click here and start typing.
package main

import (
	"fmt"
	"sync"
	"time"
)

type MapElement struct {
	Value      interface{}
	ChanRead   chan struct{}
	ChanClosed bool
	Mutex      sync.RWMutex
}

type BlockReadMap struct {
	Map   map[string]*MapElement
	Mutex sync.RWMutex
}

func (brMap *BlockReadMap) Out(key string, value interface{}) {
	meVal, ok := brMap.Map[key]
	if !ok {
		// map level mutex for element add
		brMap.Mutex.Lock()
		meVal = &MapElement{}
		meVal.ChanRead = make(chan struct{}, 0)
		brMap.Map[key] = meVal
		brMap.Mutex.Unlock()
	}
	// element level mutex for update value only
	meVal.Mutex.Lock()
	meVal.Value = value
	if !meVal.ChanClosed {
		// meVal.ChanRead <- struct{}{}
		close(meVal.ChanRead)
		meVal.ChanClosed = true
	}
	meVal.Mutex.Unlock()
	fmt.Println("write ", key, value, " success!")
}

func (brMap *BlockReadMap) Rd(key string) (value interface{}) {
	meVal, ok := brMap.Map[key]
	if !ok {
		brMap.Mutex.Lock()
		meVal = &MapElement{}
		meVal.ChanRead = make(chan struct{}, 0)
		brMap.Map[key] = meVal
		brMap.Mutex.Unlock()
	}
	<-meVal.ChanRead
	meVal.Mutex.RLock()
	defer meVal.Mutex.RUnlock()
	value = meVal.Value
	return value
}

func main() {
	const timeFormat = "2006-01-02T15:04:05.000000000Z07:00"
	fmt.Println(time.Now().Format(timeFormat), "Start...")
	var brMap = BlockReadMap{}
	brMap.Map = map[string]*MapElement{}
	var key = "1"
	var val = "abc"
	for i := 0; i < 10; i++ {
		go func() {
			var t = time.Now()
			fmt.Println(t.Format(timeFormat), "RD Start goroutin ", i, ", key: ", key)
			var vRD = brMap.Rd(key)
			t = time.Now()
			fmt.Println(t.Format(timeFormat), "RD End goroutin ", i, ", key: ", key, ", Val: ", vRD)
		}()
	}
	time.Sleep(3000000001 * time.Nanosecond)
	// fmt.Println("RD 10 goroutins started!")
	var j = 0
	go func() {
		fmt.Println(time.Now().Format(timeFormat), "Write Start goroutin ", j, ", key: ", key)
		brMap.Out(key, val)
		fmt.Println(time.Now().Format(timeFormat), "Write End goroutin ", j, ", key: ", key)
	}()
	time.Sleep(3 * time.Second)
	fmt.Println("Hello, 世界", brMap.Map)
	fmt.Println("2nd round read")
	for i := 0; i < 10; i++ {
		go func() {
			var t = time.Now()
			fmt.Println(t.Format(timeFormat), "RD Start goroutin ", i, ", key: ", key)
			var vRD = brMap.Rd(key)
			t = time.Now()
			fmt.Println(t.Format(timeFormat), "RD End goroutin ", i, ", key: ", key, ", Val: ", vRD)
		}()
	}
	time.Sleep(3000000001 * time.Nanosecond)
	go func() {
		fmt.Println(time.Now().Format(timeFormat), "Write Start goroutin ", j, ", key: ", key)
		brMap.Out(key, "bcd")
		fmt.Println(time.Now().Format(timeFormat), "Write End goroutin ", j, ", key: ", key)
	}()
	time.Sleep(3 * time.Second)
	fmt.Println("Hello, 世界", brMap.Map)
	fmt.Println("3rd round read")
	for i := 0; i < 10; i++ {
		go func() {
			var t = time.Now()
			fmt.Println(t.Format(timeFormat), "RD Start goroutin ", i, ", key: ", key)
			var vRD = brMap.Rd(key)
			t = time.Now()
			fmt.Println(t.Format(timeFormat), "RD End goroutin ", i, ", key: ", key, ", Val: ", vRD)
		}()
	}
	time.Sleep(3000000001 * time.Nanosecond)

}

StdOut:

2009-11-10T23:00:00.000000000Z Start...
2009-11-10T23:00:00.000000000Z RD Start goroutin  4 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  9 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  5 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  6 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  7 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  8 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  0 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  2 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  3 , key:  1
2009-11-10T23:00:00.000000000Z RD Start goroutin  1 , key:  1
2009-11-10T23:00:03.000000001Z Write Start goroutin  0 , key:  1
write  1 abc  success!
2009-11-10T23:00:03.000000001Z Write End goroutin  0 , key:  1
2009-11-10T23:00:03.000000001Z RD End goroutin  4 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  1 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  3 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  2 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  6 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  8 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  5 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  7 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  9 , key:  1 , Val:  abc
2009-11-10T23:00:03.000000001Z RD End goroutin  0 , key:  1 , Val:  abc
Hello, 世界 map[1:0xc0000a2000]
2nd round read
2009-11-10T23:00:06.000000001Z RD Start goroutin  9 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  9 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  1 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  1 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  3 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  3 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  5 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  5 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  8 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  8 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  4 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  4 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  6 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  6 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  0 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  0 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  7 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  7 , key:  1 , Val:  abc
2009-11-10T23:00:06.000000001Z RD Start goroutin  2 , key:  1
2009-11-10T23:00:06.000000001Z RD End goroutin  2 , key:  1 , Val:  abc
2009-11-10T23:00:09.000000002Z Write Start goroutin  0 , key:  1
write  1 bcd  success!
2009-11-10T23:00:09.000000002Z Write End goroutin  0 , key:  1
Hello, 世界 map[1:0xc0000a2000]
3rd round read
2009-11-10T23:00:12.000000002Z RD Start goroutin  0 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  0 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  1 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  1 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  2 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  2 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  5 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  5 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  7 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  7 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  8 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  8 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  6 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  6 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  3 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  3 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  9 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  9 , key:  1 , Val:  bcd
2009-11-10T23:00:12.000000002Z RD Start goroutin  4 , key:  1
2009-11-10T23:00:12.000000002Z RD End goroutin  4 , key:  1 , Val:  bcd

Program exited.