[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban commented on JGRP-1396: -------------------------------- We could now not have retransmission timeouts per seqno or seqno range, but for the entire bitmap. Perhaps we can decrease the interval when we have many missing messages, and increase it when we only have a few ? Or we could partition the bitmap into N parts: the first parts are sent more frequently the the last parts, as the elements of the bitmap are in order of reception: older messages are towards the head, more recent messages towards the tail of the bitmap... -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban updated JGRP-1396: --------------------------- Summary: Merge NakReceiverWindow and Retransmitter (was: Merge NakreceiverWindow and Retransmitter) Fix Version/s: 3.1 (was: 3.2) -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban updated JGRP-1396: --------------------------- Summary: NAKACK2: merge NakReceiverWindow and Retransmitter (was: Merge NakReceiverWindow and Retransmitter) -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban commented on JGRP-1396: -------------------------------- Since the RingBuffer's low seqno is only advanced on a stable() message, we need to make sure that adding a message to the buffer doesn't block forever (the sender *has* to block and cannot simply discard the message when the buffer is full, as it might need to retransmit it !). For example, if we have STABLE initiate a stability round after 10MB have been received, and the ring buffer has a capacity of 10'000, then the following could happen: - A sender sends 10'000 messages of 100 bytes / message and blocks - STABLE has received 1MB worth of data, but doesn't trigger a stability round yet because it waits for 10MB --> The sender blocks until STABLE runs its periodical stability round (every 50 secs by default) ! SOLUTION: - When the ring buffer of a sender P exceeds a certain (configurable) threshold (say 75% by default), then we run the following protocol: - P multicasts its highest delivered (HD) seqno - Every member of the current view responds with the P's HD, as seen by them - When P has collected all answers, it computes the minimum HD (MHD) for P from all responses and sends a STABILITY message - Every member now calls stable(MHD) for P and therefore advances HD --> The goal is for a sender never to block --> This additional protocol round is only needed for the above scenario. In most cases, the STABLE protocol should advance the low seqno of the ring buffer before the capacity is exceeded ! -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban edited comment on JGRP-1396 at 1/2/12 9:45 AM: -------------------------------------------------------- Here's another problem: we want to advance 'low' when removing a message (and nulling it). This happens at the receivers when discard_delivered_msgs is true. But there is a problem with the following scenario (threads T1 and T2): - HD=9 - T1 calls add(10). 10 already exists - T2 calls remove() with nullify=true - T1 reads HD, value is 9, continues (would terminate if HD was 10) - T2 checks that element at index HD+1 is not null - T2 gets element at index HD+1 - T2 increments HD to 10 and nulls the element at index 10 - T1 does a CAS(null, 10) and succeeds because T2 just nulled the element ==> We now deliver the message at index 10 TWICE (or multiple times) ! SOLUTION: - Interleave the reads and writes of T1 and T2 such that this outcome is impossible: - remove(): #1 write HD #2 null element #3 write LOW - add(seqno) [with nullify=true]: #1 read HD (return if seqno <= HD) #2 read element (return if element != null) #3 read HD (again!) (return if seqno <= HD) #4 CAS(null, element): if true: pass message up, else: discard There is no sequence of add() and remove() with the above solution that ends up with an incorrect delivery ! was (Author: belaban): Here's another problem: we want to advance 'low' when removing a message (and nulling it). This happens at the receivers when discard_delivered_msgs is true. But there is a problem with the following scenario (threads T1 and T2): - HD=9 - T1 calls add(10). 10 already exists - T2 calls remove() with nullify=true - T1 reads HD, value is 9, continues (would terminate if HD was 10) - T2 checks that element at index HD+1 is not null - T2 gets element at index HD+1 - T2 increments HD to 10 and nulls the element at index 10 - T1 does a CAS(null, 10) and succeeds because T2 just nulled the element ==> We now deliver the message at index 10 TWICE (or multiple times) ! SOLUTION: - Interleave the reads and writes of T1 and T2 such that this outcome is impossible: - remove(): #1 write HD #2 null element - add(seqno) [with nullify=true]: #1 read HD (return if seqno <= HD) #2 read element (return if element != null) #3 read HD (again!) (return if seqno <= HD) #4 CAS(null, element): if true: pass message up, else: discard There is no sequence of add() and remove() with the above solution that ends up with an incorrect delivery ! -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban commented on JGRP-1396: -------------------------------- Regarding the locked version of RingBuffer: there are still 2 big downsides to it: #1 An add() will block if the capacity is full. I don't like blocking, and even if we run a stable protocol for the sender, it still complicates the code and the sender can still block, even if it's only for a short duration. #2 Every RingBuffer has a fixed size buffer which is either too big (if we send few messages) or too small (if we always exceed its capacity). A cluster of 1000 using RingBuffer in NAKACK2, with an xmit_buf_size of 1'000'000 leads to 1 GB of total heap needed for all RingBuffers ! I think this pretty much kills RingBuffer for me, at least for the time being, and I think I'll go back to NakReceiverWindow using a RetransmitTable (which dynamically grows and shrinks, without the overhead of ConcurrentHashMap)... However, we can still achieve the goal of this JIRA, by trashing Retransmitter (and its complexity), and only using 1 retransmitter task for all of the NakReceiverWindows ! -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban commented on JGRP-1396: -------------------------------- OK, I think the ultimate solution is now: #1 Extend RetransmitTable to keep track of low, hd and hr. Remove() or removeMany() can also advance low if nullify=true #2 Use RetransmitTable in NAKACK directly, rather than NakReceiverWindow, trash the latter (ditto for UNICAST2) #3 Create *one* single retransmit task, periodically scanning the RetransmiTables for gaps and triggering retransmission if needed -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira

[ https://issues.jboss.org/browse/JGRP-1396?page=com.atlassian.jira.plugin.... ] Bela Ban commented on JGRP-1396: -------------------------------- What was done is the following: - Created Table as a copy of RetransmitTable, but with a lock, and LOW, HD and HR - In NAKACK2: replaced NakreceiverWindow with Table<Message> - In NAKACK2: created only 1 retransmitter task, which periodically scans all tables and triggers retransmission -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira