Golang并发有序映射(ConcurrentOrderedMap)的实现与探讨

ConcurrentOrderedMap 的实现确实解决了Go语言标准库中 sync.Map 无法保持插入顺序的问题。下面是一个基于读写锁和双向链表的实现示例，它提供了线程安全的键值存储并维护插入顺序：

package main

import (
	"container/list"
	"sync"
)

type ConcurrentOrderedMap struct {
	mu    sync.RWMutex
	items map[interface{}]*list.Element
	order *list.List
}

type kvPair struct {
	key   interface{}
	value interface{}
}

func NewConcurrentOrderedMap() *ConcurrentOrderedMap {
	return &ConcurrentOrderedMap{
		items: make(map[interface{}]*list.Element),
		order: list.New(),
	}
}

func (m *ConcurrentOrderedMap) Set(key, value interface{}) {
	m.mu.Lock()
	defer m.mu.Unlock()

	if elem, exists := m.items[key]; exists {
		elem.Value.(*kvPair).value = value
		return
	}

	elem := m.order.PushBack(&kvPair{key: key, value: value})
	m.items[key] = elem
}

func (m *ConcurrentOrderedMap) Get(key interface{}) (interface{}, bool) {
	m.mu.RLock()
	defer m.mu.RUnlock()

	if elem, exists := m.items[key]; exists {
		return elem.Value.(*kvPair).value, true
	}
	return nil, false
}

func (m *ConcurrentOrderedMap) Delete(key interface{}) {
	m.mu.Lock()
	defer m.mu.Unlock()

	if elem, exists := m.items[key]; exists {
		m.order.Remove(elem)
		delete(m.items, key)
	}
}

func (m *ConcurrentOrderedMap) Range(f func(key, value interface{}) bool) {
	m.mu.RLock()
	defer m.mu.RUnlock()

	for elem := m.order.Front(); elem != nil; elem = elem.Next() {
		pair := elem.Value.(*kvPair)
		if !f(pair.key, pair.value) {
			break
		}
	}
}

func (m *ConcurrentOrderedMap) Len() int {
	m.mu.RLock()
	defer m.mu.RUnlock()
	return len(m.items)
}

使用示例：

func main() {
	m := NewConcurrentOrderedMap()

	// 并发写入
	var wg sync.WaitGroup
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(idx int) {
			defer wg.Done()
			m.Set(fmt.Sprintf("key%d", idx), idx*10)
		}(i)
	}
	wg.Wait()

	// 按插入顺序迭代
	m.Range(func(key, value interface{}) bool {
		fmt.Printf("Key: %v, Value: %v\n", key, value)
		return true
	})

	// 并发读取
	for i := 0; i < 5; i++ {
		wg.Add(1)
		go func(idx int) {
			defer wg.Done()
			if val, ok := m.Get(fmt.Sprintf("key%d", idx)); ok {
				fmt.Printf("Read: key%d = %v\n", idx, val)
			}
		}(i)
	}
	wg.Wait()
}

这个实现的特点：

1. 使用 sync.RWMutex 实现读写分离，提高并发读取性能
2. 通过 container/list 维护插入顺序的双向链表
3. 使用哈希表实现O(1)时间复杂度的查找
4. Range 方法保证按插入顺序迭代

对于更高性能的场景，可以考虑使用分段锁（sharded locking）来减少锁竞争：

type ShardedConcurrentOrderedMap struct {
	shards []*ConcurrentOrderedMap
	count  uint32
}

func NewShardedConcurrentOrderedMap(shardCount int) *ShardedConcurrentOrderedMap {
	shards := make([]*ConcurrentOrderedMap, shardCount)
	for i := range shards {
		shards[i] = NewConcurrentOrderedMap()
	}
	return &ShardedConcurrentOrderedMap{
		shards: shards,
		count:  uint32(shardCount),
	}
}

func (m *ShardedConcurrentOrderedMap) getShard(key interface{}) *ConcurrentOrderedMap {
	hash := fnv.New32a()
	fmt.Fprintf(hash, "%v", key)
	return m.shards[hash.Sum32()%m.count]
}

这种分段实现可以将锁竞争分散到不同的分片上，特别适合高并发写入场景。