2

ReentrantReadWriteLock is perfect for read-write scenario based on timestamp programmatically at the time of reception. 

PUT(KEY=1,VALUE=1)
PUT(KEY=1,VALUE=2)
GET(KEY=1)
PUT(KEY=1,VALUE=1)
...

Java ReentrantReadWriteLock will automatically sync all of them in order based on timestamp offered by Java itself. However, how I need to use external timestamp which is offered along with each request.

PUT(KEY=1,VALUE=1,TIMESTAMP=13000000000000)
PUT(KEY=1,VALUE=2,TIMESTAMP=13500000000000)
GET(KEY=1,TIMESTAMP=14000000000000)
PUT(KEY=1,VALUE=1,TIMESTAMP=15000000000000)
...

How to design ReadWriteLock ordered by external timestamp?

4

1 回答 1

0

Short answer:

Synchronize the channel through which you receive the timestamped data or use an ordered concurrent data structure like ConcurrentSkipListMap on the receiving end. Meanwhile question whether you need to maintain this ordering at all.

P.S. ReentrantReadWriteLock doesn't use comparable entities like timestamps to establish ordering, and its algorithm for fair scheduling doesn't include reordering of entries that you can reuse. ReentrantReadWriteLock uses CLH-based lock queue through AbstractQueuedSynchronizer.

Long answer:

While what you want to do may very well be something that you can't avoid, it's always good to question whether you really need various flavors of precision and consistency in concurrent and/or distributed systems.

Why are you concerned with this problem?

It sounds like you want to preserve fairness by using the data ordering from another layer in your system. Do you need these two layers to be separate, maybe because one of them is out of your control, or because they need to stay semantically separated? If that's the case, you can ask yourself a couple more questions here.

Is it absolutely necessary to have this ordering maintained for every request?

Is this ordering a crucial part of your business logic? Is it actually established by a component in the upper layer that you care about?

  1. If it is based on the time of arrival of some requests through a network outside of your control, like the Internet, chances are that you don't really care about this ordering, and relaxing your consistency requirements will probably result in higher throughput. It's not rare to see that unfairly displaced requests in a highly concurrent, unfair environment are served faster than requests in a fair environment that has problems utilizing its resources.
  2. If it is based on a single, super-fast timestamp issuer that establishes a total order over all of the requests, you may be able to modify your system, so that the timestamp issuer becomes the single producer that serves the requests to the second layer of your system through a Disruptor or an ArrayBlockingQueue.

Would you actually receive out of order requests?

You may be solving a problem that you'll never actually face, or that you will face somewhere far in the future, and in the meantime your time could be better spent somewhere else.

If that's not the case and you actually expect to receive out of order (in your external timestamp order) requests, then the communication channel between your layers is one of the components that introduce "disorder" in your system. This may be so because someone deliberately wanted to trade consistency for throughput, or it may be because that channel doesn't fit in the needs of your system without additional work.

Consider whether it's easier to enforce strict consistency in it, or it's easier to keep it as is and order the requests after they have been received.

  • We already touched on the former with the approach illustrated for the SingleProducerTimestampIssuer™ - it may also be unfeasible if you don't have control over the channel.
  • For the latter, you can try using an ordered concurrent data structure. A ConcurrentSkipListMap mapping timestamps to requests may be a good solution. If you are not afraid of trying to apply an idea from a paper, you may want to take a look at Concurrent Programming Without Locks and Fast Concurrent Data-Structures Through Explicit Timestamping
于 2016-03-17T16:11:41.240 回答