You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pulsar.apache.org by "thetumbled (via GitHub)" <gi...@apache.org> on 2024/11/15 07:53:02 UTC
[PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
thetumbled opened a new pull request, #23601:
URL: https://github.com/apache/pulsar/pull/23601
PIP: 393
### Motivation
<!-- Explain here the context, and why you're making that change. What is the problem you're trying to solve. -->
### Modifications
<!-- Describe the modifications you've done. -->
### Verifying this change
- [ ] Make sure that the change passes the CI checks.
*(Please pick either of the following options)*
This change is a trivial rework / code cleanup without any test coverage.
*(or)*
This change is already covered by existing tests, such as *(please describe tests)*.
*(or)*
This change added tests and can be verified as follows:
*(example:)*
- *Added integration tests for end-to-end deployment with large payloads (10MB)*
- *Extended integration test for recovery after broker failure*
### Does this pull request potentially affect one of the following parts:
<!-- DO NOT REMOVE THIS SECTION. CHECK THE PROPER BOX ONLY. -->
*If the box was checked, please highlight the changes*
- [ ] Dependencies (add or upgrade a dependency)
- [ ] The public API
- [ ] The schema
- [ ] The default values of configurations
- [ ] The threading model
- [ ] The binary protocol
- [ ] The REST endpoints
- [ ] The admin CLI options
- [ ] The metrics
- [ ] Anything that affects deployment
### Documentation
<!-- DO NOT REMOVE THIS SECTION. CHECK THE PROPER BOX ONLY. -->
- [ ] `doc` <!-- Your PR contains doc changes. -->
- [ ] `doc-required` <!-- Your PR changes impact docs and you will update later -->
- [ ] `doc-not-needed` <!-- Your PR changes do not impact docs -->
- [ ] `doc-complete` <!-- Docs have been already added -->
### Matching PR in forked repository
PR in forked repository:
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1865537532
##########
pip/pip-393.md:
##########
@@ -0,0 +1,226 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. When user calls `negativeAcknowledge` method,
+`NegativeAcksTracker` in `ConsumerImpl` will add an entry into the map `NegativeAcksTracker.nackedMessages`,
+mapping the message ID to the redelivery time. When the redelivery time comes, `NegativeAcksTracker` will
+send a redelivery request to the broker to redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
Review Comment:
What is "1w/s"?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1844717605
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I agree that the user doesn't need to know this, but there are technical limitations. The complete entry with all messages in the batch will get redelivered.
It is ok that the complete entry with all messages in the batch will get redelivered. We should enable batch index ack when using negative ack to filter duplicate messages.
It is unacceptable that the whole messages of one batch restrict to be redellivered at the same time. As consumer can negative different messages with different redelivery time. **Batch should be transparent to user.**
> I disagree. It doesn't make sense since each time the complete batch will get redelivered. The Pulsar client will filter out the already acknowledged messages from being processed again, however this filtering most likely has race conditions at least with message listeners.
There is guarantee for at-least-one semanticis, not exactly-once semantics. We can enable batch index ack to de-dup message, which has became the default configuration.
> btw. If the nacks don't need to be de-duplicated, there wouldn't be any need to have a map data structure. You could simply add entries to a priority queue (or an optimized hashed wheel type of datastructure) each time a message is nacked.
We can't just store the entries in client memory within a priority queue because there will be a great number of entries, no memory can retain that level of object. This is the reason why we need negative ack, we only retain a message id with tens of bytes for each message.
BTW, we use negative ack feature as the consumer side's `delayed queue`. `delayed queue` feature in pulsar is implemented in producer side, while in a lot use cases the delayed time is determined at consumer side, not producer side.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2500017267
@thetumbled The title of any PR containing PIP documentation should include `[pip]` to distinguish it from other types of PRs. I made that change to the title.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1865537000
##########
pip/pip-393.md:
##########
@@ -0,0 +1,226 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. When user calls `negativeAcknowledge` method,
+`NegativeAcksTracker` in `ConsumerImpl` will add an entry into the map `NegativeAcksTracker.nackedMessages`,
+mapping the message ID to the redelivery time. When the redelivery time comes, `NegativeAcksTracker` will
+send a redelivery request to the broker to redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
Review Comment:
Use "MB" instead of "Mb" if you are referring to megabytes instead of megabits.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2499980088
> I add the space complexity analysis of the new data structure, please review it again, thanks. @lhotari @nodece @BewareMyPower @poorbarcode @codelipenghui @dao-jun
Great analysis @thetumbled . Please move the analysis from the PR description to the PIP document itself.
One small detail (which doesn't impact the analysis or solution): "Entry id is stored in a Roaring64Bitmap, for simplicity we can replace it with RoaringBitmap, as the max entry id is 49999, which is smaller than 65535."
Isn't the value `65535` irrelevant since RoaringBitmap supports storing 4294967296 (2 * Integer.MAX_VALUE) integers, explained in https://github.com/RoaringBitmap/RoaringBitmap/blob/cca90c986d5c0096bbeabb5f968833bf12c28c0e/roaringbitmap/src/main/java/org/roaringbitmap/RoaringBitmap.java#L46-L49 . Roaring64Bitmap can store up to 9223372036854775807 long integers (2 * Long.MAX_VALUE).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2478166382
List some experiment data:
```
static long trimLowerBit(long timestamp, int bits) {
return timestamp & (-1L << bits);
}
public static void main(String[] args) throws IOException {
ConcurrentLongLongPairHashMap map1 = ConcurrentLongLongPairHashMap.newBuilder()
.autoShrink(true)
.concurrencyLevel(16)
.build();
// timestamp -> ledgerId -> entryId, no need to batch index, if different messages have
// different timestamp, there will be multiple entries in the map
// AVL Tree -> LongOpenHashMap -> Roaring64Bitmap
// there are many timestamp, a few ledgerId, many entryId
Long2ObjectSortedMap<Long2ObjectMap<Roaring64Bitmap>> map2 = new Long2ObjectAVLTreeMap<>();
long numMessages = 1000000, numLedgers=100;
long numEntries = numMessages/numLedgers;
long ledgerId, entryId, partitionIndex, timestamp=System.currentTimeMillis();
for(long i=0; i<numLedgers; i++) {
ledgerId = 10000+i;
for(long j=0; j<numEntries; j++) {
entryId = 10000+j;
partitionIndex = 0;
// 1ms per message
timestamp++;
map1.put(ledgerId, entryId, partitionIndex, timestamp);
timestamp = trimLowerBit(timestamp, 8);
if (map2.containsKey(timestamp)) {
Long2ObjectMap<Roaring64Bitmap> ledgerMap = map2.get(timestamp);
if (ledgerMap.containsKey(ledgerId)) {
ledgerMap.get(ledgerId).add(entryId);
} else {
Roaring64Bitmap entrySet = new Roaring64Bitmap();
entrySet.add(entryId);
ledgerMap.put(ledgerId, entrySet);
}
} else {
Long2ObjectMap<Roaring64Bitmap> ledgerMap = new Long2ObjectOpenHashMap<>();
Roaring64Bitmap entrySet = new Roaring64Bitmap();
entrySet.add(entryId);
ledgerMap.put(ledgerId, entrySet);
map2.put(timestamp, ledgerMap);
}
}
}
try {
Thread.sleep(10000000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
```

--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2500080763
> > I add the space complexity analysis of the new data structure, please review it again, thanks. @lhotari @nodece @BewareMyPower @poorbarcode @codelipenghui @dao-jun
>
> Great analysis @thetumbled . Please move the analysis from the PR description to the PIP document itself.
>
> One small detail (which doesn't impact the analysis or solution): "Entry id is stored in a Roaring64Bitmap, for simplicity we can replace it with RoaringBitmap, as the max entry id is 49999, which is smaller than 65535." Isn't the value `65535` irrelevant since RoaringBitmap supports storing 4294967296 (2 * Integer.MAX_VALUE) integers, explained in https://github.com/RoaringBitmap/RoaringBitmap/blob/cca90c986d5c0096bbeabb5f968833bf12c28c0e/roaringbitmap/src/main/java/org/roaringbitmap/RoaringBitmap.java#L46-L49 . Roaring64Bitmap can store up to 9223372036854775807 long integers (2 * Long.MAX_VALUE).
You are right, not 65535, but 4294967296 (2 * Integer.MAX_VALUE).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843605276
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I'd try to avoid using a map completely.
I don't know why should we avoid using map? The test result is good, i think it is good enough.
>> multiple negative ack for messages in the same entry(batch) will interfere with each other.
> The only reason why a nack would need to be updated seems to be related to batch messages?
Since a full batch will always be redelivered, I wonder what the correct and expected behavior even is from the user's point of view?
There's a possibility to de-duplicate the nacks for batch messages with a Long2ObjectMap<Roaring64Bitmap> to keep state of current positions that are already scheduled to be delivered. If another redelivery is requested for the same position, it could be simply ignored. Would that be sufficient?
If that's not sufficient, I think it would be necessary to introduce a feature in NegativeAcksTracker to send nacks for batch message only after all batch message indices have been acknowledged or nacked. It seems that it would make more sense.
For implementing this efficiently in the client, I think that BatchMessageIdImpl could be improved to avoid the need to use org.apache.pulsar.client.impl.MessageIdAdvUtils#discardBatch. Instead of creating new instances for the entry's message id, each BatchMessageIdImpl could hold a reference to a single BatchEntryMessageIdImpl (or whatever it's called) that would also hold the BitSet that is currently shared in BatchMessageIdImpl instances. When there's a shared instance for the message id for the entry of the batch messages, it could be used directly as a key in a map without causing more memory use. This change would reduce memory usage since the .discardBatch is used to create instances that are used in other trackers in the client at the moment.
When a message id could be directly used as a key in a map, there would be any need for the current hacks that we just do to get better space efficiency.
No, user actually don't need to know different messages come from the same batch. They need to be able assign different redelivery time for the different messages in the same batch.
For example, one batch contains msg1, msg2, msg3, msg4. Consumer can nack msg1 with delay 10s, nack msg2 with 20s, nack msg3 with 30s, nack msg4 with 20s. At such situation, we need to update the entry correponding to the timestamp for 20s, which is not the head of the queue, or the tail of the queue.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843452264
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
We need to key by timestamp. If you use `PriorityQueue<Long2ObjectMap<Roaring64Bitmap>>`, we need to wrap `timestamp` and `Long2ObjectMap<Roaring64Bitmap>` into a object, which consume space.
`Long2ObjectSortedMap` is better than `PriorityQueue`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1865535600
##########
pip/pip-393.md:
##########
@@ -0,0 +1,226 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. When user calls `negativeAcknowledge` method,
+`NegativeAcksTracker` in `ConsumerImpl` will add an entry into the map `NegativeAcksTracker.nackedMessages`,
+mapping the message ID to the redelivery time. When the redelivery time comes, `NegativeAcksTracker` will
+send a redelivery request to the broker to redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
Review Comment:
what unit is `w` in "100w entry"? How about "1kw" entry?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1844717605
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I agree that the user doesn't need to know this, but there are technical limitations. The complete entry with all messages in the batch will get redelivered.
It is ok that the complete entry with all messages in the batch will get redelivered. We should enable batch index ack when using negative ack to filter duplicate messages.
It is unacceptable that the whole messages of one batch restrict to be redellivered at the same time. As consumer can negative different messages with different redelivery time. **Batch should be transparent to user.**
> I disagree. It doesn't make sense since each time the complete batch will get redelivered. The Pulsar client will filter out the already acknowledged messages from being processed again, however this filtering most likely has race conditions at least with message listeners.
There is guarantee for at-least-one semanticis, not exactly-once semantics. If we can enable batch index ack to de-dup message, which has became the default configuration.
> btw. If the nacks don't need to be de-duplicated, there wouldn't be any need to have a map data structure. You could simply add entries to a priority queue (or an optimized hashed wheel type of datastructure) each time a message is nacked.
We can't just store the entries in client memory within a priority queue because there will a greate number of entries. This is the reason why we need negative ack, we just retain a message id with tens of bytes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843452264
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
If you use `PriorityQueue<Long2ObjectMap<Roaring64Bitmap>>`, there are several problem:
- we can only access the first element and the last element of the queue, but **we need to update element that is at the middle of the queue.**
- we need to wrap `timestamp` and `Long2ObjectMap<Roaring64Bitmap>` into a object, which consume space.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843605276
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I'd try to avoid using a map completely.
I don't know why should we avoid using map? The test result is good, i think it is good enough.
>> multiple negative ack for messages in the same entry(batch) will interfere with each other.
> The only reason why a nack would need to be updated seems to be related to batch messages?
Since a full batch will always be redelivered, I wonder what the correct and expected behavior even is from the user's point of view?
There's a possibility to de-duplicate the nacks for batch messages with a Long2ObjectMap<Roaring64Bitmap> to keep state of current positions that are already scheduled to be delivered. If another redelivery is requested for the same position, it could be simply ignored. Would that be sufficient?
If that's not sufficient, I think it would be necessary to introduce a feature in NegativeAcksTracker to send nacks for batch message only after all batch message indices have been acknowledged or nacked. It seems that it would make more sense.
For implementing this efficiently in the client, I think that BatchMessageIdImpl could be improved to avoid the need to use org.apache.pulsar.client.impl.MessageIdAdvUtils#discardBatch. Instead of creating new instances for the entry's message id, each BatchMessageIdImpl could hold a reference to a single BatchEntryMessageIdImpl (or whatever it's called) that would also hold the BitSet that is currently shared in BatchMessageIdImpl instances. When there's a shared instance for the message id for the entry of the batch messages, it could be used directly as a key in a map without causing more memory use. This change would reduce memory usage since the .discardBatch is used to create instances that are used in other trackers in the client at the moment.
When a message id could be directly used as a key in a map, there would be any need for the current hacks that we just do to get better space efficiency.
No, user actually don't need to know different messages come from the same batch. They need to be able assign different redelivery time for the different messages in the same batch.
For example, one batch contains msg1, msg2, msg3, msg4. Consumer can nack msg1 with delay 10s, nack msg2 with 20s, nack msg3 with 30s, nack msg4 with 20s. At such situation, we need to update the entry correponding to the timestamp for 20s, which is not the head of the queue, or the tail of the queue.
And we don't need to de-duplicate the nacks from messages in the same batch, as they are not-related. Consumer don't know different messages are from the same batch, batch is just a way to improve the performance.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843404562
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
A map datastructure isn't needed as we have discussed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2500199621
> The PIP-393 document should include the high level plan of avoiding to increase the size of the Pulsar client by the size of fastutil jar file. The fastutil jar file is very large, 23MB. We use only a few classes of fastutil. There's fastutil-core library which is smaller, about ≅6MB. However, that is also relatively large and using fastutil-core will introduce another problem on the broker side since there's already fastutil jar which also includes fastutil-core jar classes. It's necessary to design a proper shading solution as part of this PIP design and implementation. More details in the thread [#23600 (comment)](https://github.com/apache/pulsar/pull/23600#discussion_r1858069707)
Thanks for review, i add it in high level design.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2524618533
release labels shouldn't be added to PIP document PRs since we only maintain PIP documents in the master branch. release labels are used for cherry-picking.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2499619578
I add the space complexity analysis of the new data structure, please review it again, thanks. @lhotari @nodece @BewareMyPower @poorbarcode @codelipenghui
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1844717605
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I agree that the user doesn't need to know this, but there are technical limitations. The complete entry with all messages in the batch will get redelivered.
It is ok that the complete entry with all messages in the batch will get redelivered. We should enable batch index ack when using negative ack to filter duplicate messages.
It is unacceptable that the whole messages of one batch restrict to be redellivered at the same time. As consumer can negative different messages with different redelivery time. **Batch should be transparent to user.**
> I disagree. It doesn't make sense since each time the complete batch will get redelivered. The Pulsar client will filter out the already acknowledged messages from being processed again, however this filtering most likely has race conditions at least with message listeners.
There is guarantee for at-least-one semanticis, not exactly-once semantics. We can enable batch index ack to de-dup message, which has became the default configuration.
> btw. If the nacks don't need to be de-duplicated, there wouldn't be any need to have a map data structure. You could simply add entries to a priority queue (or an optimized hashed wheel type of datastructure) each time a message is nacked.
We can't just store the entries in client memory within a priority queue because there will a greate number of entries, no memory can retain that level of object. This is the reason why we need negative ack, we only retain a message id with tens of bytes for each message.
BTW, we use negative ack feature as the consumer side's `delayed queue`. `delayed queue` feature in pulsar is implement in producer side, while a lot use case the delayed time is determined at consumer side, not producer side.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843605276
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I'd try to avoid using a map completely.
I don't know why should we avoid using map? The test result is good, i think it is good enough.
>> multiple negative ack for messages in the same entry(batch) will interfere with each other.
> The only reason why a nack would need to be updated seems to be related to batch messages?
Since a full batch will always be redelivered, I wonder what the correct and expected behavior even is from the user's point of view?
There's a possibility to de-duplicate the nacks for batch messages with a Long2ObjectMap<Roaring64Bitmap> to keep state of current positions that are already scheduled to be delivered. If another redelivery is requested for the same position, it could be simply ignored. Would that be sufficient?
If that's not sufficient, I think it would be necessary to introduce a feature in NegativeAcksTracker to send nacks for batch message only after all batch message indices have been acknowledged or nacked. It seems that it would make more sense.
For implementing this efficiently in the client, I think that BatchMessageIdImpl could be improved to avoid the need to use org.apache.pulsar.client.impl.MessageIdAdvUtils#discardBatch. Instead of creating new instances for the entry's message id, each BatchMessageIdImpl could hold a reference to a single BatchEntryMessageIdImpl (or whatever it's called) that would also hold the BitSet that is currently shared in BatchMessageIdImpl instances. When there's a shared instance for the message id for the entry of the batch messages, it could be used directly as a key in a map without causing more memory use. This change would reduce memory usage since the .discardBatch is used to create instances that are used in other trackers in the client at the moment.
When a message id could be directly used as a key in a map, there would be any need for the current hacks that we just do to get better space efficiency.
No, user actually don't need to know different messages come from the same batch. They need to be able assign different redelivery time for the different messages in the same batch.
For example, one batch contains msg1, msg2, msg3, msg4. Consumer can nack msg1 with delay 10s, nack msg2 with 20s, nack msg3 with 30s, nack msg4 with 20s. At such situation, we need to update the entry correponding to the timestamp for 20s, which is not the head of the queue, or the tail of the queue.
And we don't need to de-duplicate the nacks from messages in the same batch, as they are not-related. Consumer don't know different messages are from the same batch, batch is a way to improve the performance.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1865740757
##########
pip/pip-393.md:
##########
@@ -0,0 +1,226 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. When user calls `negativeAcknowledge` method,
+`NegativeAcksTracker` in `ConsumerImpl` will add an entry into the map `NegativeAcksTracker.nackedMessages`,
+mapping the message ID to the redelivery time. When the redelivery time comes, `NegativeAcksTracker` will
+send a redelivery request to the broker to redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
Review Comment:
Sorry for using this abbreviation, `w` is `10k`, fixed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1844717605
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> I agree that the user doesn't need to know this, but there are technical limitations. The complete entry with all messages in the batch will get redelivered.
It is ok that the complete entry with all messages in the batch will get redelivered. We should enable batch index ack when using negative ack to filter duplicate messages.
It is unacceptable that the whole messages of one batch restrict to be redellivered at the same time. As consumer can negative different messages with different redelivery time. **Batch should be transparent to user.**
> I disagree. It doesn't make sense since each time the complete batch will get redelivered. The Pulsar client will filter out the already acknowledged messages from being processed again, however this filtering most likely has race conditions at least with message listeners.
There is guarantee for at-least-one semanticis, not exactly-once semantics. We can enable batch index ack to de-dup message, which has became the default configuration.
> btw. If the nacks don't need to be de-duplicated, there wouldn't be any need to have a map data structure. You could simply add entries to a priority queue (or an optimized hashed wheel type of datastructure) each time a message is nacked.
We can't just store the entries in client memory within a priority queue because there will a greate number of entries, no memory can retain that level of object. This is the reason why we need negative ack, we only retain a message id with tens of bytes for each message.
BTW, we use negative ack feature as the consumer side's `delayed queue`. `delayed queue` feature in pulsar is implemented in producer side, while in a lot use cases the delayed time is determined at consumer side, not producer side.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843662068
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> No, user actually don't need to know different messages come from the same batch. They need to be able assign different redelivery time for the different messages in the same batch.
I agree that the user doesn't need to know this, but there are technical limitations. The complete entry with all messages in the batch will get redelivered.
> For example, one batch contains msg1, msg2, msg3, msg4. Consumer can nack msg1 with delay 10s, nack msg2 with 20s, nack msg3 with 30s, nack msg4 with 20s. At such situation, we need to update the entry correponding to the timestamp for 20s, which is not the head of the queue, or the tail of the queue.
>
> And we don't need to de-duplicate the nacks from messages in the same batch, as they are not-related. Consumer don't know different messages are from the same batch, batch is just a way to improve the performance.
I disagree. It doesn't make sense since each time the complete batch will get redelivered. The Pulsar client will filter out the already acknowledged messages from being processed again, however this filtering most likely has race conditions at least with message listeners.
btw. If the nacks don't need to be de-duplicated, there wouldn't be any need to have a map data structure. You could simply add entries to a priority queue (or an optimized hashed wheel type of datastructure) each time a message is nacked.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][client] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari commented on code in PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#discussion_r1843557510
##########
pip/pip-393.md:
##########
@@ -0,0 +1,138 @@
+
+# PIP-393: Improve performance of Negative Acknowledgement
+
+# Background knowledge
+
+Negative Acknowledgement is a feature in Pulsar that allows consumers to trigger the redelivery
+of a message after some time when they fail to process it. The redelivery delay is determined by
+the `negativeAckRedeliveryDelay` configuration.
+
+When user calls `negativeAcknowledge` method, `NegativeAcksTracker` in `ConsumerImpl` will add an entry
+into the map `NegativeAcksTracker.nackedMessages`, mapping the message ID to the redelivery time.
+When the redelivery time comes, `NegativeAcksTracker` will send a redelivery request to the broker to
+redeliver the message.
+
+# Motivation
+
+There are many issues with the current implementation of Negative Acknowledgement in Pulsar:
+- the memory occupation is high.
+- the code execution efficiency is low.
+- the redelivery time is not accurate.
+- multiple negative ack for messages in the same entry(batch) will interfere with each other.
+All of these problem is severe and need to be solved.
+
+## Memory occupation is high
+After the improvement of https://github.com/apache/pulsar/pull/23582, we have reduce half more memory occupation
+of `NegativeAcksTracker` by replacing `HashMap` with `ConcurrentLongLongPairHashMap`. With 100w entry, the memory
+occupation decrease from 178Mb to 64Mb. With 1kw entry, the memory occupation decrease from 1132Mb to 512Mb.
+The average memory occupation of each entry decrease from 1132MB/10000000=118byte to 512MB/10000000=53byte.
+
+But it is not enough. Assuming that we negative ack message 1w/s, assigning 1h redelivery delay for each message,
+the memory occupation of `NegativeAcksTracker` will be `3600*10000*53/1024/1024/1024=1.77GB`, if the delay is 5h,
+the required memory is `3600*10000*53/1024/1024/1024*5=8.88GB`, which increase too fast.
+
+## Code execution efficiency is low
+Currently, each time the timer task is triggered, it will iterate all the entries in `NegativeAcksTracker.nackedMessages`,
+which is unnecessary. We can sort entries by timestamp and only iterate the entries that need to be redelivered.
+
+## Redelivery time is not accurate
+Currently, the redelivery time is controlled by the `timerIntervalNanos`, which is 1/3 of the `negativeAckRedeliveryDelay`.
+That means, if the `negativeAckRedeliveryDelay` is 1h, the redelivery time will be 20min, which is unacceptable.
+
+## Multiple negative ack for messages in the same entry(batch) will interfere with each other
+Currently, `NegativeAcksTracker#nackedMessages` map `(ledgerId, entryId)` to `timestamp`, which means multiple nacks from messages
+in the same batch share single one timestamp.
+If we let msg1 redelivered 10s later, then let msg2 redelivered 20s later, these two messages are delivered 20s later together.
+msg1 will not be redelivered 10s later as the timestamp recorded in `NegativeAcksTracker#nackedMessages` is overrode by the second
+nack call.
+
+
+# Goals
+
+Refactor the `NegativeAcksTracker` to solve the above problems.
+
+To avoid interation of all entries in `NegativeAcksTracker.nackedMessages`, we use a sorted map to store the entries.
Review Comment:
> If you use `PriorityQueue<Long2ObjectMap<Roaring64Bitmap>>`, there are several problem:
>
> * we can only access the first element and the last element of the queue, but **we need to update element that is at the middle of the queue.**
> * we need to wrap `timestamp` and `Long2ObjectMap<Roaring64Bitmap>` into a object, which consume space.
I'd try to avoid using a map completely.
For scheduling, it would be possible to optimize the scheduling datastructure without the need to use a priority queue. This is possible since the scheduling is intended to group the nacks together with a certain resolution. I'd have a separate datastructure for that purpose. Something similar to Netty's HashedWheelTimer/HashedWheelBucket, but specialized for this use case.
> multiple negative ack for messages in the same entry(batch) will interfere with each other.
The only reason why a nack would need to be updated seems to be related to batch messages?
Since a full batch will always be redelivered, I wonder what the correct and expected behavior even is from the user's point of view?
There's a possibility to de-duplicate the nacks for batch messages with a `Long2ObjectMap<Roaring64Bitmap>` to keep state of current positions that are already scheduled to be delivered. If another redelivery is requested for the same position, it could be simply ignored. Would that be sufficient?
If that's not sufficient, I think it would be necessary to introduce a feature in NegativeAcksTracker to send nacks for batch message only after all batch message indices have been acknowledged or nacked. It seems that it would make more sense.
For implementing this efficiently in the client, I think that BatchMessageIdImpl could be improved to avoid the need to use `org.apache.pulsar.client.impl.MessageIdAdvUtils#discardBatch`. Instead of creating new instances for the entry's message id, each `BatchMessageIdImpl` could hold a reference to a single BatchEntryMessageIdImpl (or whatever it's called) that would also hold the `BitSet` that is currently shared in `BatchMessageIdImpl` instances. When there's a shared instance for the message id for the entry of the batch messages, it could be used directly as a key in a map without causing more memory use. This change would reduce memory usage since the `.discardBatch` is used to create instances that are used in other trackers in the client at the moment.
When a message id could be directly used as a key in a map, there would be any need for the current hacks that we just do to get better space efficiency.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "lhotari (via GitHub)" <gi...@apache.org>.
lhotari merged PR #23601:
URL: https://github.com/apache/pulsar/pull/23601
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [improve][pip] PIP-393: Improve performance of Negative Acknowledgement [pulsar]
Posted by "thetumbled (via GitHub)" <gi...@apache.org>.
thetumbled commented on PR #23601:
URL: https://github.com/apache/pulsar/pull/23601#issuecomment-2510843781
The vote is completed, please review this pr again, thanks. @lhotari @nodece @eolivelli
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pulsar.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org