Danh sách thân thiện với STM dưới dạng nhật ký thay đổi

Question

Tôi cần lời khuyên về cấu trúc dữ liệu để sử dụng làm nhật ký thay đổi nguyên tử.

Tôi đang cố triển khai thuật toán sau. Có một luồng đến thay đổi cập nhật bản đồ trong bộ nhớ. Trong giả Haskell giống như nó là

update :: DataSet -> SomeListOf Change -> Change -> STM (DataSet, SomeListOf Change) 
    update dataSet existingChanges newChange = do 
     ... 
     return (dataSet, existingChanges ++ [newChange]) 

nơi DataSet là một bản đồ (hiện nay nó là bản đồ từ gói stm-container, https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Map.html). Toàn bộ "cập nhật" được gọi từ số lượng chủ đề tùy ý. Một số thay đổi có thể bị từ chối do ngữ nghĩa của miền, tôi sử dụng throwSTM để loại bỏ hiệu ứng của giao dịch. Trong trường hợp cam kết thành công, "newChange" được thêm vào danh sách.

Tồn tại chủ đề riêng biệt mà gọi hàm sau:

flush :: STM (DataSet, SomeListOf Change) -> IO() 

chức năng này được cho là để có những ảnh chụp hiện tại của DataSet kèm theo danh sách các thay đổi (nó có một cặp thống nhất) và tuôn ra nó vào hệ thống tệp, tức là

flush data = do 
     (dataSet, changes) <- atomically $ readTVar data_ 
     -- write them both to FS 
     -- ... 
     atomically $ writeTVar data_ (dataSet, []) 

Tôi cần lời khuyên về cấu trúc dữ liệu để sử dụng cho "Thay đổi SomeListOf". Tôi không muốn sử dụng [Thay đổi] vì nó "quá trật tự" và tôi e rằng sẽ có quá nhiều xung đột, điều này sẽ buộc toàn bộ giao dịch phải thử lại. Hãy sửa tôi, nếu tôi sai ở đây.

Tôi không thể sử dụng Set (https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Set.html) vì tôi vẫn cần phải giữ lại một số đơn đặt hàng, ví dụ: thứ tự giao dịch cam kết. Tôi có thể sử dụng TChan cho nó và nó trông giống như một kết hợp tốt (chính xác thứ tự các giao dịch cam kết), nhưng tôi không biết làm thế nào để thực hiện các chức năng "tuôn ra" để nó sẽ cung cấp cho xem nhất quán của toàn bộ nhật ký thay đổi với nhau với DataSet.

Triển khai hiện tại là ở đây https://github.com/lolepezy/rpki-pub-server/blob/add-storage/src/RRDP/Repo.hs, trong các hàm applyActionsToState và rrdpSyncThread, tương ứng. Nó sử dụng TChan và dường như làm điều đó một cách sai lầm.

Cảm ơn bạn trước.

Cập nhật: Một câu trả lời hợp lý có vẻ là như thế

type SomeListOf c = TChan [c] 

    update :: DataSet -> TChan [Change] -> Change -> STM DataSet 
    update dataSet existingChanges newChange = do 
     ... 
     writeTChan changeChan $ reverse (newChange : existingChanges) 
     return dataSet 

    flush data_ = do 
     (dataSet, changes) <- atomically $ (,) <$> readTVar data_ <*> readTChan changeChan 
     -- write them both to FS 
     -- ... 

Nhưng tôi vẫn không chắc chắn cho dù đó là một giải pháp gọn gàng để vượt qua toàn bộ danh sách như một yếu tố của kênh.

Answer 1

Tôi có thể chỉ cần đi với danh sách và xem cách hoạt động hiệu quả. Cho rằng, bạn nên xem xét rằng cả hai, gắn vào cuối của một danh sách và đảo ngược nó là O (n) hoạt động, vì vậy bạn nên cố gắng tránh điều này. Có thể bạn chỉ có thể thêm các thay đổi sắp tới như thế này:

update dataSet existingChanges newChange = do 
    -- ... 
    return (dataSet, newChange : existingChanges) 

Ngoài ra, ví dụ về tuôn ra của bạn có vấn đề là đọc và cập nhật trạng thái không phải là nguyên tử. Bạn phải thực hiện điều này bằng cách sử dụng atomically cuộc gọi duy nhất như vậy:

flush data = do 
    (dataSet, changes) <- atomically $ do 
    result <- readTVar data_ 
    writeTVar data_ (dataSet, []) 
    return result 

    -- write them both to FS 
    -- ... 

Sau đó, bạn có thể chỉ cần viết chúng ra theo thứ tự ngược (vì bây giờ changes chứa các yếu tố từ mới đến cũ) hoặc ngược lại ở đây một lúc nếu điều quan trọng là viết chúng ra lâu đời nhất mới nhất.Nếu đó là điều quan trọng tôi có thể đi với một số cấu trúc dữ liệu cho phép truy cập phần tử O (1) như một vector cũ tốt.

Khi sử dụng vectơ có kích thước cố định, bạn sẽ phải xử lý vấn đề có thể trở thành "đầy đủ" có nghĩa là người viết của bạn sẽ phải chờ flush để thực hiện công việc trước khi thêm thay đổi mới. Đó là lý do tại sao cá nhân tôi đi cho danh sách đơn giản đầu tiên và xem nếu nó là đủ hoặc nơi nó cần phải được cải thiện.

PS: A dequeue cũng có thể phù hợp với vấn đề của bạn, nhưng việc cố định kích thước sẽ giúp bạn giải quyết vấn đề mà nhà văn của bạn có khả năng tạo ra nhiều thay đổi hơn người đọc của bạn có thể tuôn ra. Các dequeue có thể phát triển vô hạn, nhưng bạn RAM của bạn có lẽ không phải là. Và vectơ có chi phí khá thấp.

Answer 2

Tôi đã thực hiện một số điều tra (rất đơn giản) https://github.com/lolepezy/rpki-pub-server/tree/add-storage/test/changeLog bắt chước chính xác loại tải mà tôi cho là sẽ có. Tôi đã sử dụng cùng một STMContainers.Map cho tập dữ liệu và danh sách thông thường cho nhật ký thay đổi. Để theo dõi số lần thử lại giao dịch, tôi đã sử dụng Debug.Trace.trace, có nghĩa là số dòng được in theo dấu vết. Và số lượng duy nhất dòng được in theo dấu vết cho tôi số lượng giao dịch được cam kết.

Kết quả ở đây (https://github.com/lolepezy/rpki-pub-server/blob/add-storage/test/changeLog/numbers.txt). Cột đầu tiên là số lượng chủ đề, cột thứ hai là số lượng các tập hợp thay đổi được tạo trong tổng số. Cột thứ ba là số lần theo dõi cuộc gọi cho trường hợp không có nhật ký thay đổi và lần cuối cùng là số lần theo dõi cuộc gọi bằng nhật ký thay đổi.

Rõ ràng hầu hết nhật ký thay đổi thời gian đều bổ sung thêm một số lần thử lại, nhưng nó không đáng kể lắm. Vì vậy, tôi đoán, thật công bằng khi nói rằng bất kỳ cấu trúc dữ liệu nào cũng đủ tốt, bởi vì hầu hết công việc liên quan đến việc cập nhật bản đồ và hầu hết các lần thử lại đang diễn ra vì nó.